링크드 리스트는 데이터와, 이어진 노드의 포인터를 통해 서로 연결된 형태의 자료구조를 말한다
링크드 리스트의 종류
싱글 링크드 리스트
다음(next) 노드에 대한 포인터 주소만 가진다
단방향으로만 탐색 가능하다
더블 링크드 리스트
이전(prev), 다음(next) 노드에 대한 포인터 주소를 모두 가진다
양방향으로 탐색이 가능하다
링크드 리스트의 특징
비연속적
포인터 기반으로 연결되어 있기 때문에, 요소들이 메모리 상에서 연속되어 있을 필요가 없다
서로 흩어져 있기 때문에, 임의 접근하는데 O(n)의 시간복잡도를 가진다
메모리 상에서 연속될 필요가 없기 때문에, 배열에서 했던 요소를 추가/삭제하기 위해 한 칸씩 이동시키는 작업이 필요없다
하지만 결국 임의의 위치에 추가/삭제 하려면 해당 위치로 접근하는데 O(n) 시간이 걸리기 때문에, 임의의 위치에 추가/삭제 연산은 O(n)의 시간복잡도를 가진다
하지만 특정 상황에서 유용한 경우가 있다. 시간 복잡도를 조금 더 세분화 해보자
링크드 리스트의 주요 연산과 시간 복잡도
읽기
노드들이 메모리 상에 연속적으로 저장되어 있지 않기 때문에, 임의 접근(random access) 위해 O(n) 시간복잡도를 가진다
삽입
맨 앞의 경우, 저장되어 있던 Head 노드에 O(1)으로 접근해, 대신 Head 역할을 하면 되기 때문에 O(1) 시간복잡도를 가진다
맨 뒤의 경우, (Tail 노드의 메모리 주소를 저장해 뒀다면), Tail 노드에 O(1)으로 접근해 Tail 노드의 next에 추가한 노드의 주소를 저장하면 되므로 O(1) 의 시간복잡도를 가진다
임의의 위치의 경우, 해당 위치의 노드에 접근하는데 O(n)이 걸리기 때문에 삽입 연산도 결국 O(n) 시간복잡도를 가지는 셈이다
배열과 비교해 맨 뒤 삽입 연산이 O(1)의 시간 복잡도를 가진다는 측면에서 장점이 있다
위치
시간 복잡도
맨 앞
O(1)
맨 뒤
O(1)
임의의 위치
O(n)
삭제
맨 앞의 경우, Head 노드에 O(1)으로 접근해, Head 노드의 next에 연결되어 있던 노드에게 Head 역할을 맡기면 되기 때문에 O(1) 시간복잡도를 가진다
맨 뒤의 경우, (Tail 노드의 메모리 주소를 저장해 뒀다면), Tail 노드에 O(1)으로 접근해 삭제할 것이다. 하지만 Tail 노드의 역할을 Tail 노드 앞에 있던 노드에게 맡겨야 하기 때문에, Tail 바로 앞에 있는 노드에 접근이 필요하다. 이 때, 싱글 링크드 리스트인 경우, prev 주소가 없기 때문에 결국 Head에서부터 끝까지 선형 탐색으로 접근해야 되서 O(n) 시간복잡도를 가지게 되고, 더블 링크드 리스트인 경우 prev 주소가 있기 때문에 O(1) 시간복잡도를 가진다
임의의 위치의 경우, 해당 위치의 노드에 접근하는데 이미 O(n)이 걸리기 때문에 결국 O(n) 시간복잡도를 가진다
위치
싱글 링크드 리스트
더블 링크드 리스트
맨 앞
O(1)
O(1)
맨 뒤
O(n)
O(1)
임의의 위치
O(n)
O(n)
(더블 링크드 리스트가 싱글과 비교해 맨 뒤 삭제를 O(1) 으로 할 수 있다는 장점이 있지만, 배열도 맨 뒤 삭제가 O(1)이기 때문에 스택을 구현할 때 배열을 사용한다)
(큐는 맨 앞 삭제, 맨 뒤 삽입이 중요한데, 이는 싱글과 더블 모두 가능하기 때문에, 결국 큐를 구현할 때는 싱글 링크드 리스트를 사용한다)
큐(Queue)
스택(Stack)과 큐(Queue)는 맨 앞/뒤 삽입/삭제 연산이 활발하다.
스택은 맨 뒤 삽입/삭제가 중요한데, 이는 배열로도 O(1)의 시간 복잡도를 얻을 수 있다
큐는 맨 뒤 삽입, 맨 앞 삭제가 중요한데 이 때는 링크드 리스트가 필요하다
큐 말고는?
이렇게 보면 링크드 리스트는 큐를 구현하기 위한 경우 말고는 크게 필요가 없어보인다
하지만 임의의 위치 삽입/삭제의 경우, 실제로 배열보다 링크드 리스트가 컴퓨팅 리소스에 부담이 적고, 소요 시간이 일정하다
(배열의 한 칸씩 이동하는 shift 과정이 링크드리스트의 임의의 위치로 먼저 이동하기 위해 발생하는 선형 탐색 과정보다 컴퓨팅 리소스 많이 소모)
![[Data Structure] Linked list: 링크드 리스트](/images/data-structure_logo.png){kind=logo}
