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

링크드 리스트

링크드 리스트는 데이터를 순서대로 저장해준다.

계속해서 새로운 요소를 추가할 수 있다. 배열과는 다르게 각 요소는 사실상 독립적인 레퍼런스에 위치해있다.

각 요소를 노드라고 하고, data 속성과 next 속성을 보유한다. next에는 다음 노드에 대한 레퍼런스가 들어있다.

따라서 실제 메모리에 각 노드들이 여기저기에 흩어져있어도 next속성을 통해 이어진 것처럼 활용할 수 있다.

링크드 리스트의 구성

따로 linked list클래스를 만들어서 활용한다. 그렇지만 이 linked list 클래스는 모든 노드를 멤버로 보유하지 않는다. 첫 노드 혹은 마지막 노드만을 보유하고 있다면 그에 연결된 나머지 노드들은 그를 통해 접근이 가능하기 때문이다. 따라서 linked list 클래스는 주로 첫 노드인 head노드와 마지막 노드인 tail노드만을 멤버로서 보유한다. (참고로 tail 노드는 next값을 보유하지 않는다.)

링크드 리스트의 접근

리스트와 마찬가지로 일정 위치의 노드를 불러올 수 있다. 다만, 배열은 한번에 원하는 인덱스의 주소에 접근하여 데이터를 불러왔지만, 링크드 리스트는 자료 구조의 특성상 그럴 수 없다. 반복자를 활용해 인덱스의 수(n)만큼 next 노드를 읽어서 접근한다.

시간복잡도는 최악의 경우 링크드 리스트의 길이만큼 next로 넘어가야 하므로, O(n)이다.

링크드 리스트의 탐색

iterator 변수를 활용하여, 더 이상 연결된 노드가 없을 때까지 (tail노드에 이를 때까지 혹은 주어진 데이터와 일치하는 노드에 이를 때까지) 주어진 데이터와 iterator에 해당하는 노드의 데이터를 비교한다.

시간복잡도는 단순히 떠올렸을 때 O(n)임을 알 수 있다.

링크드 리스트 주의사항

링크드 리스트는 head와 tail을 잘 관리하는 것이 중요하다. 어떤 상황에서 head와 tail이 변할지 잘 떠올리고 그를 매번 바꿔줘야 한다. 제대로 바꿔주지 않으면 링크드 리스트가 꼬일 수 있기 때문이다. 예를 들어 제일 마지막에 노드가 추가되면 해당 노드가 tail 노드가 되고, 그에 따라 next값이 none이 되어야 한다.

또한 pop_left와 같은 연산을 할 때, 모든 노드가 없어진다면 반드시 이를 고려하여 tail노드도 None처리를 해주어야 한다. 그렇지 않고 Node의 tail값을 찾으면 tail은 여전히 해당 노드를 가르키고 있기 때문에None이 아닌 해당 노드에 대한 주소값이 출력된다.
(ex.<__main__.Node object at 0x7f3a57f3d1d0>)

참고로 링크드 리스트에 '유일한 노드가 있다'의 의미는 현재 head노드와 tail노드 모두 동일한 노드라는 뜻이다.

링크드 리스트의 head, tail 시간복잡도

링크드 리스트에서 '가장 앞에 접근 후 삭제', '가장 앞에 접근 후 삽입', '가장 뒤에 접근 후 삽입'은 모두 접근방식이 쉬워(self.head or self.tail로 바로 접근 가능) 시간복잡도가 O(1)이다.

하지만 가장 뒤에 접근 후 삭제는 가장 뒤 전의 노드(tail의 부모노드)에 접근해야만 하므로 시간복잡도가 O(n)이다.

---

지금까지 살펴본 것은 노드가 data, next값만 가지고 있는 '싱글리 링크드 리스트' 였지만, prev값도 함께 저장하는 '더블리 링크드 리스트' 도 있다. 거의 작동 방식은 유사하다. 싱글리와 마찬가지로 head와 tail을 잘 신경써주어야 한다.

cf. 싱글리 혹은 더블리 링크드 리스트에서 노드를 추가할 때는 항상 리스트가 비어있을 경우 등의 특수 상황을 잘 생각해야 한다. (삭제 연산 등에서는 하나만 남아있는 self.head == self.tail의 상황도 특별하다.)

더블리 링크드 리스트에서는 삭제 연산이 쉽다. 지정된 노드에 바로 접근하여 그와 인접한 next노드와 prev노드를 수정해주면 되기 때문이다. (물론 head나 tail과 같은 특수한 노드의 경우 적절한 조치를 취해주어야 한다.)

싱글리 링크드 리스트와는 다르게 더블리 링크드 리스트는 tail 노드 삭제를 원할 때도 바로 접근하여 삭제가 가능하다.
(linked_list.tail을 바로 삭제 연산자에 넣어주면 내부적으로 동작할 수 있기 때문이다.)

따라서 삭제를 많이 해야하는 상황이라면 더블리 링크드 리스트를 사용하는 것이 효율적일 수 있다.

---