[Data Structure] Array vs LinkedList

배열 (Array)

: 배열은 동일한 타입의 요소들을 연속적인 메모리 공간에 저장하는 자료구조입니다. 배열은 고정된 크기를 가지며, 배열의 각 요소는 인덱스를 통해 직접 접근할 수 있습니다. 이러한 특성 때문에 배열에서의 요소 접근(검색)은 매우 빠르게 이루어집니다. O(1)의 시간복잡도를 가집니다. 그러나 배열은 크기가 고정되어 있어, 배열의 크기를 변경하려면 전체 배열을 새로운 크기의 배열로 복사하는 과정이 필요하며, 이는 비용이 많이 드는 작업입니다. 또한, 배열의 중간에 요소를 삽입하거나 삭제하는 경우, 해당 요소 이후의 모든 요소들을 이동시켜야 하므로 비효율적입니다.

 

 

연결 리스트 (Linked List)

: 연결 리스트는 요소들이 메모리상에서 연속적으로 위치하지 않고, 각 요소가 당므 요소의 주소를 가리키는 포인터를 통해 서로 연결되어 있는 자료구조입니다. 연결 리스트는 동적 크기를 가지며, 필요에 따라 요소를 추가하거나 삭제할 수 있습니다. 연결 리스트에서 요소를 삽입하거나 삭젷나느 작업은 O(1) 시간에 가능하지만, 특정 요소에 접근(검색)하는데는 처음부터 해당 요소까지 순차적으로 탐색해야 하므로 O(n)의 시간복잡도를 가집니다. 연결 리스트는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Double Linked List), 원형 연결 리스트(Circular Linked List) 등 다양한 변형이 있습니다.

 

 

차이점

1. 메모리 할당

• 배열: 고정된 크기의 연속적인 메모리를 할당받는다.
• 연결 리스트: 요소가 추가될 때마다 개별적으로 메모리를 할당받는다.

 

2. 접근 시간

• 배열: 인덱스를 통한 직접 접근이 가능하여 접근 시간이 O(1)이다.
• 연결 리스트: 순차 접근이 필요하여 O(n)이다.

 

3. 크기 변경

• 배열: 크기가 고정되어 있어 변경이 어렵다.
• 연결 리스트: 동적으로 크기가 변할 수 있다.

 

4. 삽입/삭제 연산

• 배열: 중간에 요소를 삽입하거나 삭제하는 경우 비효율적이다.
• 연결 리스트: 요소를 삽입하거나 삭제하는 경우 해당 노드의 포인터만 조정하면 되므로 효율적이다.