자료구조 3주차 - 연결리스트

서울여대 이병걸 교수님의 자료구조 수업을 들은 뒤 복습용으로 작성한 글입니다.

교재: 파이썬과 함께하는 자료구조의 이해

---

연결리스트는 리스트로 구현된 자료구조로 단순연결리스트, 이중연결리스트(중복연결리스트), 원형연결리스트 세종류가 있다.

 

단순연결리스트란 동적 메모리 할당을 이용해 노드들을 한 방향으로 연결하여 리스트를 구현하는 자료구조로, 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만든다. 여기서 동적 메모리 할당이란 항목이 추가되면 리스트를 확장하고, 항목이 삭제되면 리스트를 축소시키며 새 메모리에 할당하는데 이를 동적 메모리 할당이라고 한다. 레퍼런스는 메모리 주소를 의미한다.

단순연결리스트에서 항목을 삽입하거나 삭제할 때 레퍼런스만 수정하면 되기 때문에 항목들의 이동이 필요없다. 하지만 항목 탐색 시 항상 첫 노드부터 원하는 노드까지 순차적으로 탐색해야한다. 이때 삽입, 삭제 연산은 O(1)시간이 소요되지만, 노드들 사이에 삽입을 하거나 노드와 노드 사이에 있는 노드를 삭제하는 경우 특정 노드의 레퍼런스가 주어지지 않았다면 순차적으로 탐색을 해야하기 때문에 O(N)시간이 걸릴 수 있다. 탐색연산의 경우 첫 노드부터 순차적으로 탐색을 해야하므로 O(N)시간이 소요된다.

이런 단순연결리스트는 스택, 큐, 해싱체이닝 등 다양한 곳에서 활용이 되며, 트리구조와 블록체인 또한 단순연결리스트를 응용한 것이다.

 

이중연결리스트는 각 노드가 두개의 레퍼런스를 가지고 각각 이전노드와 다음 노드를 가리키는 연결리스트이다. 단순연결리스트는 다음 노드의 레퍼런스만으로 연결이 되어 있어 삽입이나 삭제할 때 이전 노드를 가리키는 레퍼런스를 알아야 한다. 또한 역방향으로 노드를 탐색할 수 없다는 단점이 있다. 이를 해결한 것이 이중연결리스트인데 각 노드마다 추가로 1개의 레퍼런스가 저장되어야 한다는 단점이 있다.

이중연결리스트의 삽입, 삭제 연산은 단순연결리스트와 유사하게 O(1)시간이 소요된다. 탐색의 경우 단순연결리스트와 마찬가지로 O(N) 시간이 걸린다. 

이중연결리스트는 디큐(혹은 데크) 자료구조를 구현하는데 사용되며, 이항힙이나 피보나치힙과 같은 우선순위 큐를 구현하는데도 이중연결리스트가 부분적으로 사용된다.

 

마지막으로 원형연결리스트는 마지막 노드가 첫 노드와 연결되어 원형을 이룬 단순연결리스트이다. 원형연결리스트에서 마지막 노드는 첫 노드와 같으며, 마지막노드에서 첫 노드를 방문하는데 O(1)시간이 소요된다. 하지만 원형연결리스트는 단순연결리스트의 일종으로 역방향 탐색은 어려우며 무한루프가 발생할 수 있다.

원형연결리스트 또한 위의 이중연결, 단순연결 리스트와 같이 삭제, 삽입 연산은 O(1)시간이 소요되며, 탐색 연산의 경우 O(N)시간이 소요된다.

원형연결리스트는 CPU 시간을 분할하여 작업할당을 하는 운영체제에도 사용되며 이항힙, 피보나치힙과 같은 우선순위 큐를 구현하는데도 부분적으로 사용된다.