[선형 자료구조] 링크드 리스트

링크드 리스트란?

 

데이터를 순차적으로 저장하는 선형 자료구조 중 하나이다.

링크드 리스트의 요소는 노드(node) 형태로 존재하는데, node 안에는 데이터와 다음 노드의 메모리 위치를 가리키는 포인터로 이루어져 있다.

 

주요 특징

연속적이지 않은 메모리 주소

 

링크드 리스트의 요소인 노드는 다시 두가지 부분으로 구성된다.

- 데이터(Data): 노드가 저장하는 실제 데이터

- 다음 노드(next node): 다음 노드의 메모리 위치를 참조하는 포인터

 

이렇게 구성 된 이유는 일반 배열의 경우 연속된 메모리 주소를 가지기 때문에, 삽입과 삭제시 O(n)의 시간복잡도를 가지게 된다.

하지만 링크드 리스트의 경우 삽입/삭제시에도 가리키는 다음 주소만을 추가/수정해주면 되기 때문에 삽입/삭제 자체만으로는 O(1)의 시간복잡도를 가지게 된다.

 

종류

단일 링크드 리스트

각 노드가 다음 노드에 대한 참조만을 가지는 가장 단순한 형태

 

이중 링크드 리스트

각 노드가 이전 노드와 다음 노드에 대한 참조를 모두 가지는 양방향 탐색이 가능한 형태

 

원형 링크드 리스트

마지막 노드가 다시 첫번째 노드를 가리키는 형태 

 

시간 복잡도

임의 접근: O(n)

링크드 리스트는 연속되지 않기 때문에 인덱스가 존재하지 않는다.

이러한 특징때문에 특정 인덱스에 있는 요소에 접근하기 위해서 첫 번째 노드부터 차례로 순회해야 한다.

 

첫 번째 마지막 위치에 삽입/삭제: O(1)

일반적으로 링크드 리스트는 시작점인 Head와 종료지점인 Tail을 구성하고 있다.

구현에 따라 Tail이 생략되기도 하지만 보통의 경우 Head, Tail을 통해 바로 접근이 가능하기 때문에 O(1)의 시간복잡도를 가진다.

 

임의의 위치에 삽입/삭제: O(n) + O(1)

삽입/삭제의 위치를 알고 있다면 O(1)을 가지지만, 탐색이 더해진다면 삽입/삭제를 위해 접근할때 노드를 차례로 순회하기 때문에 O(n)의 시간복잡도를 가진다.

 

배열 vs 링크드 리스트

배열이 효율적인 상황

1. 임의 접근이 잦은 경우

즉 읽기 작업이 많고 삽입 삭제가 적은 경우 배열의 사용이 더 효율적일 것이다.

 

2. 크기가 고정된 데이터를 다룰 때

배열의 경우 초기화 시점에 필요한 요소의 개수 만큼 capacity를 설정한다.

이 후 배열의 크기가 커지게 되면 그에 맞추어 capacity는 두 배씩 증가하여 새로운 연속된 메모리 공간을 만들게 된다.

이렇게 연속된 메모리 공간을 확보하기 위해서 코스트가 추가로 발생하기 때문에 크기가 고정된 데이터를 다룰 때 배열이 효율적이다.

 

링크드 리스트가 효율적인 상황

1. 삽입/삭제가 잦은 경우

위치를 알고 있다면 링크드 리스트의 삽입/삭제는 O(1)로 배열보다 효율적이다.

 

2. 크기가 동적인 데이터를 다룰 때

배열과 같이 연속된 메모리 공간을 필요로 하지 않기 때문에 더욱 효율적이다.