[CS][Data Structure] 연결 리스트 (Linked List)

Linked List란?

Linked List는 데이터 요소들이 선형적으로 연결된 자료구조입니다.
각 요소는 Node라고 부르고 노드는 데이터를 저장하는 공간과 이웃 노드를 가르키는 포인터로 구성됩니다.
각 요소들은 물리적 순서가 아닌 포인터를 통해 연결되어 있습니다.

Linked List 종류

1. 단일 연결 리스트 : 각 노드가 다음 노드를 가르키는 포인터를 가지고 있는 가장 기본적인 형태

2. 이중 연결 리스트 : 각 노드가 이전 노드와 다음 노드를 가르키는 포인터 2개를 가지고 있어 양방향으로 탐색할 수 있는 형태

3. 원형 연결 리스트 : 마지막 노드가 처음 노드를 가르키는 포인터를 가지고 있어 연결 리스트가 원형으로 구성되어 있는 형태

Linked List 장점

동적 크기

크기를 동적으로 조정할 수 있고, 노드를 할당하거나 해제할 수 있습니다.

데이터 삽입 및 삭제 효율성

포인터를 조작하여 수행하기 때문에 데이터의 삽입 및 삭제가 O(1)의 시간 복잡도를 가지며 빠르고 효율적입니다.
하지만 중간에 삽입 및 삭제를 할 경우에는 해당 노드까지 이동하는 시간이 필요하기 때문에 O(n)의 시간 복잡도가 추가될 수 있습니다. Java에서 구현된 LinkedList는 노드를 찾을 때 처음 및 끝에서 출발하기 때문에 O(n/2)는 보장되는 것으로 보입니다.

Linked List 단점

검색 속도

포인터를 따라가며 노드에 접근해야 하기 때문에 배열에 비해 검색 속도가 느린 O(n)의 시간 복잡도를 가집니다.

메모리 오버헤드

포인터 정보를 저장하기 위한 메모리 공간이 추가적으로 필요합니다.

Linked List 활용

데이터 삽입 및 삭제가 빈번하게 발생하는 경우

메모리 사용 조절이 필요한 경우