배열 / 리스트

[ 목차 ]

배열

- 배열(Array)은 동일한 데이터 타입의 요소(Element)들이 연속된 메모리 공간에 저장되는 자료구조이다. 배열은 고정된 크기를 가지며, 요소는 인덱스를 통해 접근할 수 있다.

배열의 특징

• 빠른 접근 속도 : 인덱스를 통해 O(1) 시간에 요소 접근 가능
• 고정크기 : 배열 생성 시 크기를 미리 지정해야 함.
• 효율적인 메모리 사용 : 연속된 메모리 공간을 사용하여 오버헤드가 적음.

배열의 장단점

• 장점 : 
  • 인덱스를 통한 빠른 읽기와 쓰기
  • 데이터가 연속된 메모리 공간에 저장되어 메모리 관리가 편함.
• 단점 : 
  • 삽입과 삭제가 비효율적 O(n), 특히 중간 요소의 경우
  • 크기 변경이 불가능하므로 동적 크기 지원이 어려움.

 

자바에서의 배열

- 자바에서 배열 선언하기

• int, char, double, Integer, String 등의 자료형으로 선언 가능하다.
• 배열을 선언하면 int형은 0, double형은 0.0으로 초기화된다.
• 기본 자료형의 배열은 선언과 동시에 배열 크기 만큼의 메모리가 할당되지만, 객체 배열은 객체의 주소가 들어갈 4/8byte의 메모리 공간만 할당되고 각 객체는 따로 생성하여 저장해야 한다. (객체 배열의 초기값은 null)

 

 

자바에서 배열 정렬하기

• 배열의 정렬을 하기 위해서는 Java.util.Arrays 클래스의 sort() 메서드를 사용하면 간편하게 배열을 정렬할 수 있다.
  • Arrays.sort(배열이름);
• 기본 오름차순 정렬의 경우는 sort method로 모든 타입에 대해 할 수 있으나 내림차순과 같이 reverse해야하는 경우는 Primitive type(int, char등)으로 만들어진 배열의 경우는 Wrapper class(Integer, String등)로 만들어줘야한다.
  • Arrays.sort(배열이름, Collections.reverseOrder());
• 배열의 일부분만 정렬하기 위해서는 parameter로 배열의 이름, 배열, 시작index, 끝 index를 대입해줘야한다.
  • Arrays.sort(배열이름, 시작 index, 끝 index);
• 객체 배열의 정렬은 compareTo함수를 override해줘야한다.

 

 

리스트

- 리스트(List)는 데이터를 노드(Node)로 저장하며, 각 노드는 데이터와 다음 노드를 가리키는 포인터(참조)를 포함한다. 배열과 달리 크기가 가변적이다.

리스트의 종류

1. 단일 연결 리스트 (Singly Linked List):
   • 각 노드가 다음 노드를 가리킴.
2. 원형 연결 리스트 (Circular Linked List):
   • 마지막 노드가 첫 번째 노드를 가리키는 구조 .
3. 이중 연결 리스트 (Doubly Linked List):
   • 각 노드가 이전 노드와 다음 노드를 가리킴.

리스트의 특징

• 동적 크기 : 필요에 따라 크기를 조정 가능 
• 삽입/삭제 용이 : 포인터만 조정하면 되므로 O(1) 또는 O(n) 시간 소요
• 연속된 메모리 공간이 필요없음 : 노드가 임의의 메모리 공간에 분산되어 저장

리스트의 장단점

• 장점 :
  • 삽입과 삭제가 빠름 (특히 리스트의 시작과 끝에서)
  • 동적이므로 크기가 정해져있지 않다.  
• 단점 : 
  • 인덱스 접근 불가 : O(n)의 순차 탐색이 필요
  • 추가적인 포인터 저장공간이 필요

 

자바에서의 리스트

- 자바는 컬렉션 프레임워크(Collection Framework)를 통해 리스트를 지원하며, 대표적인 구현체로 ArrayList와 LinkedList가 있다.

 

ArrayList

• Array와 같이 ArrayList도 index로 객체를 관리한다.
• 크기를 동적으로 늘릴 수 있다. (저장 용량을 넘으면 배열 크기가 1.5배가 된다.)
• ArrayList는 Array와 다르게 특정 index의 객체를 제거하면 뒤에 위치한 객체들이 앞으로 한칸씩 이동한다. (빈 공간을 두지 않는다.)
• 원소의 이동/추가/삭제 등이 많은 작업을 한다면 ArrayList보다 LinkedList를 사용하는게 효과적이다. 반면에 검색이 많은 경우는 ArrayList를 사용한다.
• Array는 primitive type과 object를 모두 담을 수 있으나 arrayList는 object element만 담을 수 있다.

 

 

LinkedList

• ArrayList는 하나의 큰 배열을 사용하여 구현하였다면, LinkedList는 각각의 node를 연결하는 방식을 사용한다.
• LinkedList는 양뱡향 연결 리스트(Doubly Linked List)로 구현되어있다.
• 인덱스를 갖고 있지 않기 때문에 탐색을 할때는 순차접근만 가능하여 탐색 시간이 오래 걸린다.
• LinkedList는 ArrayList와는 달리 List 인터페이스를 구현한 AbstractList를 상속하지 않고 AbstractSequentialList를 상속한다.
• 데이터의 추가/삭제/변경이 많은 경우 좋은 성능을 낸다.

 

 

배열과 리스트의 차이점

특징	배열(Array)	리스트(List)
메모리 구조	연속된 메모리 블록	분산된 노드로 구성
크기	고정	동적
접근 속도	O(1) (인덱스 접근)	O(n)
삽입/삭제 속도	느림 (O(n), 중간에서 갑입/삭제 시)	빠름(O(1), 특정 위치에서는)
메모리의 효율성	높음	낮음(포인터 저장 공간 필요)

 

Array와 ArrayList의 비교

특징	배열(Array)	ArrayList
크기	고정	동적
성능	빠른 인덱스 접근 O(1)	삽입/삭제에서 더 효율적
메서드 제공 여부	기본 제공 없음 (System.arraycopy)	풍부한 메서드 제공 (add, remove, ... )
메모리 사용	더 적음	더 많음

 

 

ArrayList와 LinkedList의 비교

특징	ArrayList	LinkedList
기반 구조	배열 기반	노드 기반
삽입/삭제 성능	느림 (중간에 삽입/삭제 시 O(n))	빠름 (중간에 삽입/삭제 시 O(1))
랜덤 접근	빠름(O(1))	느림(O(n))
메모리 사용량	상대적으로 적음	추가 포인터 저장공간 필요

 

 

 

배열과 리스트의 선택 기준

배열과 리스트는 각각 특정 상황에 적합한 특성을 지니고 있다. 자바에서 배열과 리스트를 선택할 때, 다음과 같은 기준을 고려할 수 있다:

 

배열을 선택해야 하는 경우

1. 데이터 크기가 고정된 경우:
   • 예: 월별 매출 데이터를 저장하거나, 고정된 크기의 버퍼를 사용할 때.
2. 빠른 접근 속도가 중요한 경우:
   • 예: 정렬된 데이터에서 특정 인덱스의 값을 자주 조회해야 하는 상황.
3. 메모리를 효율적으로 사용해야 하는 경우:
   • 배열은 추가적인 포인터 저장 공간이 필요하지 않아 메모리 사용이 적습니다.

 

리스트를 선택해야 하는 경우

1. 데이터 크기가 가변적이고, 삽입/삭제 작업이 빈번한 경우:
   • 예: 대기열 관리 시스템이나 실시간 데이터 추가/삭제가 필요한 경우.
2. 동적 데이터 관리가 필요한 경우:
   • 예: 사용자의 입력 데이터를 순차적으로 처리할 때.
3. 삽입/삭제가 리스트의 중간에서 자주 발생하는 경우:
   • 연결 리스트(LinkedList)를 사용하는 것이 효율적입니다.

 

추가적인 비교 : 벡터(Vector)와 리스트(List)

- 벡터(Vector)는 동적 배열로, 배열의 단점을 보완한 자료 구조이다. 자바에서 제공하는 java.util.Vector 클래스이며, ArrayList와 유사한 배열 기반의 동적 자료구조이다. 벡터는 동기화(synchronized) 처리가 되어 멀티 스테드 환경에서 안전하게 사용할 수 있다.

 

벡터의 특징

• 기본적으로 동기화되어 멀티스레드 환경에서도 안전
• 배열처럼 인덱스를 통해 O(1) 시간 복잡도로 접근가능
• 크기가 자동으로 조정되는 동적 배열 구조.

- 단점 : 

• 동기화로 인해 단일 스레드 환경에서는 ArrayList보다 성능이 낮음
• 잘 사용되지 않음 (대부분의 경우 ArrayList가 더 적합)

- 벡터를 사용해야 하는 경우 : 멀티스레드 환경에서 데이터 저장이 필요한 경우 

 

 

 

마무리하며,

배열, 리스트, 그리고 벡터는 각각의 장점과 단점을 가지고 있으며, 적절한 사용 환경에서 효율적으로 활용할 수 있는 중요한 자료구조이다. 이번에 이 글을 작하면서 각 자료구조의 동작 원리와 특징을 깊이 이해할 수 있었다.

앞으로도 다른 자료구조와 비교하며 자료구조에 대한 학습을 확장해야겠다.

 

출처

https://velog.io/@enamu/%EB%B0%B0%EC%97%B4Array%EA%B3%BC-%EB%A6%AC%EC%8A%A4%ED%8A%B8List

배열(Array)과 리스트(List)

 

https://velog.io/@seongwon97/Java-Array%EC%99%80-List-%EB%B9%84%EA%B5%90

[Java] Array와 List 비교