[자료구조] Array vs ArrayList vs LinkedList

배열(Array) : 요소들을 인덱스에 기반하여 연속적으로 저장하는 자료구조

ArrayList : 동적 크기를 가지는 배열로, 내부적으로 배열을 사용하여 구현되는 자료구조

LinkedList : 각 요소들을 노드로 구성하고, 노드들은 데이터와 다음 노드를 가리키는 포인터로 연결되는 자료구조

 

Array, ArrayList, LinkedList 비교

1. 크기 조정

• 배열 : 고정 크기로 선언되며, 크기를 변경할 수 없다.
• ArrayList, LinkedList : 동적으로 크기가 조정된다.

 

2. 타입 제한

• 배열 : 제네릭 타입 사용 불가능
• ArrayList, LinkedList : 제네릭 타입을 사용가능

 

배열에 제네릭 타입을 사용할 수 없는 이유는 배열은 컴파일 시점에서 자신의 요소 타입을 알고 있어야 하는데, 제네릭 타입은 컴파일 시점에서 타입 소거가 이루어지기 때문에 컴파일러가 실제로 어떤 타입의 객체들이 배열에 저장되는지 알 수 없기 때문이다. 즉, 배열의 요소 타입을 컴파일 시점에서 알 수 없기 때문에 타입의 안전성을 보장하기 위해 자바에서 제한하는 것이다.

 

3. 메모리 할당

• 배열, ArrayList : 요소들을 저장하기 위해 연속적인 메모리 공간이 필요하다.
• LinkedList : 각 노드는 독립적인 메모리 공간에 할당되고, 이로 인해 연속적인 메모리 공간을 요구하지 않는다. 

 

4. 접근 속도 

• 배열, ArrayList : 인덱스를 통해 접근이 가능하기 때문에 O(1) 즉, 상수 시간(Constant Time)에 접근이 가능하다.
• LinkedList : 순차적으로 접근해야 하기 때문에 O(n)의 시간이 걸린다.

 

5. 삽입과 삭제 

• 배열, ArrayList : 중간에 배열을 추가하거나 삭제하면 해당 index의 이후의 요소들을 뒤/앞으로 이동시켜야 하기 때문에 효율성이 떨어진다.
• LinkedList : 노드의 포인터가 가리키는 다음 노드만 변경하면 되기 때문에 삽입, 삭제시 효율적이다.