배열(Array) VS 배열 리스트(ArrayList) VS 연결 리스트(LinkedList)

📙 1. 배열

📌 1. 개념 및 특징

• 배열(Array)이란 같은 타입의 여러 변수를 하나의 묶음으로 다루는 것을 말한다.
• 배열을 구성하는 각각의 값을 배열 요소(Element), 배열에서의 위치를 가리키는 숫자를 인덱스(Index)라고 한다.
• 배열은 참조 객체이므로 배열을 가리키는 참조 변수는 스택 영영에 할당되며, 이 참조 변수가 가리키고 있는 주소값은 실제 힙 영역에 생성되는 배열의 주소값이다.
• 배열의 크기는 고정적이다.
• 메모리 공간이 연속적으로 구성된다.

📌 2. 장점

• 인덱스를 활용할 수 있기 때문에, 특정 위치에 있는 원소에 대한 접근의 시간복잡도가 O(1)이다.
• 인덱스를 활용할 수 있기 때문에, 특정 위치에 있는 원소에 대한 수정의 시간복잡도가 O(1)이다.

📌 3. 단점

• 크기가 고정적이기 때문에 더 많은 데이터를 저장하기 위해서는 더 큰 배열을 만들고 이전 배열의 데이터를 새로 만든 배열로 복사해야 한다. 이때, O(n)의 시간복잡도가 소요된다.
• 배열 중간에 있는 원소를 제거해야 하는 경우, 삭제하고자 하는 위치의 인덱스 뒤에 있는 원소부터 배열의 맨 끝에 있는 원소까지 앞으로 한 칸씩 이동해줘야 한다. 이때, O(n)의 시간복잡도가 소요된다.
• 배열 중간에 원소를 삽입해야 하는 경우에도 위와 동일하게 O(n)의 시간이 소요된다.

 

 

📙 2. 배열리스트(ArrayList)

📌 1. 개념 및 특징

• 배열리스트(ArrayList)란 내부적으로 배열(Array)을 이용하여 요소를 저장하는 자료구조이다.
• ArrayList 클래스는 내부적으로 Object [] 배열을 이용하여 요소를 저장한다.
• 크기가 고정되어 있는 배열과 달리 데이터 적재량에 따라 가변적으로 공간을 늘리거나 줄인다.
• List 인터페이스에서 정의한 다양한 메서드를 사용할 수 있다.
• 데이터는 연속적으로 리스트에 들어있어야 하므로 중간에 빈 공간이 있으면 안 된다.

📌 2. 장점

• 인덱스를 활용할 수 있기 때문에 특정 위치에 있는 원소에 대한 접근과 수정에 대해서 O(1)의 시간복잡도가 소요된다.
• 저장 공간의 크기가 가변적으로 변하기 때문에 따로 신경을 쓰지 않아도 된다.
• 배열 리스트의 중간에 빈 공간을 허용하지 않기 때문에 배열에 비해 메모리 공간의 낭비가 없다.

📌 3. 단점

• 메서드를 활용해서 간편하게 중간에 원소를 삽입/삭제할 수 있지만 시간복잡도는 여전히 O(n)이다.
• 또한, 저장 공간을 확장 및 복사하는 과정에서도 시간복잡도가 O(n)이다.

 

 

📙 3. 연결리스트(LinkedList)

📌 1. 개념 및 특징

• 배열리스트(ArrayList)가 내부적으로 배열을 이용하여 메서드로 조작이 가능하게 만든 컬렉션이라면, 연결리스트(LinkedList)는 노드(객체)끼리의 주소 포인터를 서로 가리키며 참조(링크)함으로써 이어지는 구조이다.
• 연결리스트의 종류로는 단방향 연결 리스트(Singly Linked List), 양방향 연결 리스트(Doubly Linked List), 양방향 원형 연결 리스트(Doubly Circular Linked List)가 있다.
• 자바에서 LinkedList 컬렉션 클래스는 양방향 연결 리스트로 만들어져 있다.
• 연결리스트 또한 저장 공간의 크기는 가변적이다.

📌 2. 장점

• 맨 앞에 원소를 삽입하는 경우 기존 원소들을 한 칸씩 이동해줄 필요가 없으므로 O(1)의 시간복잡도를 가진다.
• 양방향 연결 리스트의 경우 맨 뒤에 원소를 삽입할 때 O(1)의 시간복잡도를 가진다.
• 배열이나 배열 리스트와 달리 저장 공간에 새로운 원소가 삽입되거나 삭제될 때, 저장 공간을 확장하거나 축소하여 재할당해 줄 필요가 없다.

📌 3. 단점

• 인덱스를 활용할 수 없기 때문에 특정 위치에 있는 원소에 접근하기 위해서는 노드들을 따라가면서 탐색해야 한다. 그래서 O(n)의 시간복잡도를 가진다.
• 특정 위치에 있는 원소에 대한 수정도 위와 같은 이유로 O(n)의 시간복잡도를 가진다.
• 중간에 원소를 삽입하거나 삭제하는 경우에도 해당 위치를 찾아야 하기 때문에 O(n)의 시간복잡도를 가진다.

 

 

📙 4. 비교

	배열(Array)	배열 리스트(ArrayList)	연결 리스트(LinkedList)
저장 공간의 크기	고정적	가변적	가변적
메모리 공간의 연속성	O	O	X
특정 위치에 있는 원소에 대한 접근	O(1)	O(1)	O(n)
특정 원소를 탐색	O(n)	O(n)	O(n)
맨 앞에 원소 추가 / 삭제	O(n)	O(n)	O(1)
중간에 원소 추가 / 삭제	O(n)	O(n)	O(n)
맨 뒤에 원소 추가 / 삭제	O(n)	O(n)	O(1)

 

해당 글은
Inpa 님의 'JAVA 배열(Array) 완벽 다루기 가이드', '자바 ArrayList 구조 & 사용법 정리', '자바 LinkedList 구조 & 사용법 - 정복하기', 'ArrayList vs LinkedList 특징 & 성능 비교',
몽구 님의 '[Java] 배열(Array) vs. 배열리스트(ArrayList) vs. 연결리스트(LinkedList)'
를 참고하였습니다.