-
자료구조 핵심 원리 - 연결 리스트Algorithm 2022. 9. 23. 21:34
1. 연결리스트
동적 배열은 탐색 기능이 막강하며 배열 마지막에서 삽입 및 삭제 연산 속도가 빨라 프로그램을 처음 작성할 때 가장 먼저 사용을 고려하는 자료 구조입니다. 하지만 데이터를 배열 중간에 삽입하거나 삭제해야 할 때는 원소들을 옮겨야 하는 부담이 있지요. O(n) 정도면 성능이 훌륭하지 않나 하고 생각할 수도 있습니다. 그래도 중간에 삽입과 삭제가 자주 일어나는 상황에서 좀 더 나은 삽입 및 삭제 연산을 제공하는 자료 구조가 있다면 배열보다 그것을 선택하는 것이 나을 수 있습니다. 연결 리스트(linked list)는 이런 고민에서 만들어진 자료 구조입니다.
연결 리스트는 그 자체만으로는 동적 배열에 비해 쓰임새가 적은 편입니다. 삽입과 삭제가 빈번한 경우에 사용을 고민해 볼 수 있겠지요. 연결 리스트를 사용한 예로는 OS에서 힙 메모리를 할당 및 해제할 때 이중 연결 리스트로 구현한 경우가 있습니다. 연결 리스트가 중요한 이유는 다른 자료 구조를 구현하는 토대가 되기 때문입니다.
1.1 연결 리스트 이해하기
메모리상에 선형으로 나열된 배열과 달리 연결 리스트는 요소들이 참조로 이어져 있습니다. 각 요소는 노드라는 틀에 담겨 있는데, 노드는 데이터를 담는 부분과 다음 노드를 가리키는 참조로 구성되어 있습니다.
data는 실제 저장하려는 데이터고, link는 다음 노드를 가리킵니다. 이렇게 참조로 데이터와 데이터를 연결(link)해 두었기 때문에 연결 리스트라고 합니다. 연결 리스트는 참조가 하나 있느냐 둘이 있느냐에 따라 단순 연결 리스트(single linked list)와 이중 연결 리스트(double linked list)로 나눕니다. 단순 연결 리스트는 다음 노드를 가리키는 참조 하나만 가지고 있는 반면, 이중 연결 리스트는 앞 노드를 가리키는 참조와 뒤 노드를 가리키는 참조를 모두 가지고 있습니다.
단순 연결 리스트를 다룬 예제로 연결 리스트가 가지는 삽입·삭제·탐색 연산의 특징을 알아보겠습니다.
위의 그림은 요소 세 개를 가진 연결 리스트에 새로운 노드를 삽입하는 첫 번째 과정입니다. 노드 1과 2 사이에 4를 삽입하려고 합니다. 동적 배열이었다면 2와 3 모두 옮기는 연산을 한 후 4를 삽입해야 하지만 연결 리스트는 다릅니다. 그림과 같이 4의 link는 2를 가리키게 하고, 1의 link는 4를 가리키게 하면 됩니다.
예제에서는 1 다음의 데이터가 두 개라서 연산 횟수의 차이를 느낄 수 없을지도 모릅니다. 하지만 1 이후의 데이터 개수가 10만 개였다면 동적 배열은 이동 연산이 10만 번 필요하고, 연결 리스트는 여전히 참조 할당 연산이 단 두 번만 필요합니다. 삭제도 빅오는 O(1)입니다.
노드 4를 삭제할 때는 그저 노드 1의 link가 2를 가리키게 하면 됩니다. 그러면 함수를 실행한 후 노드 4는 따로 처리하지 않아도 메모리에서 사라지는데, 이는 파이썬이 언어 차원에서 대신 지워 주기 때문입니다. 이렇게 언어 차원에서 메모리를 관리해 주는 것을 가비지 컬렉션이라고 하는데, 파이썬의 경우 레퍼런스 카운트로 가비지 컬렉션을 지원합니다. 레퍼런스 카운팅은 어떤 객체를 가리키는 객체 개수가 0이 될 때 해당 객체를 지우는 것을 의미합니다. 노드 4를 보면, 노드 1이 2를 가리키면 자신을 가리키고 있는 어떤 노드도 없기 때문에 가비지 컬렉션으로 삭제됩니다.
마지막으로 연결 리스트의 탐색을 살펴보겠습니다. 연결 리스트는 인덱싱과 같은 연산을 구현할 수 없기 때문에 어떤 요소를 찾으려면 리스트의 처음부터 끝까지 하나씩 방문하면서 해당 요소를 찾아야 합니다.
먼저 cur 변수를 두어 리스트의 첫 노드를 가리키게 합니다. 그리고 찾고자 하는 값 4와 노드 값을 비교합니다. 첫 번째 노드 값은 1이므로 4가 아닙니다. 그럼 link를 통해 다음 노드로 이동해서 다시 비교합니다. 이 과정을 4를 찾을 때까지 진행합니다. 최악의 경우 리스트 마지막까지 비교해야겠지요. 데이터 개수가 n개라면 n번 비교해야 합니다. 그래서 빅오는 O(n)입니다.
1.2 동적 배열과 연결 리스트
다음은 동적 배열과 연결 리스트의 차이를 정리한 표입니다.
1. 삽입 및 삭제
동적 배열은 배열의 마지막에 데이터를 추가하거나 삭제하는 경우를 제외하고 O(n)의 성능을 가지는 반면, 연결 리스트는 단지 연산 상수 한 번만으로도 데이터를 추가하거나 삭제할 수 있습니다. 당연히 빅오는 O(1)입니다.
2. 탐색
동적 배열은 인덱싱이라는 단 한 번의 강력한 연산으로 해당 인덱스의 데이터에 접근할 수 있었습니다. 빅오는 O(1)이지요. 하지만 연결 리스트는 해당 요소의 데이터에 접근하기 위해 처음부터 모든 노드를 차례로 순회해야 했습니다. 빅오는 O(n)입니다.
이처럼 동적 배열과 연결 리스트의 특징은 정반대입니다.
1.3 더미 이중 연결 리스트
보통 연결 리스트라고 하면 더미 이중 연결 리스트(dummy double linked list)를 의미합니다. 연결 리스트의 ADT를 정의하고 구현해봅시다.
DoubleLinkedList
- Object : 순서 있는 원소의 유한 집합
- Operation
1. empty( ) -> Boolean: 비어 있으면 TRUE, 아니면 FALSE 반환
2. size( ) -> Integer : 요소 개수 반환
3. add_first(data) : data를 리스트의 맨 앞에 추가
4. add_last(data) : data를 리스트의 맨 마지막에 추가
5. insert_after(data, node) : data를 node 다음에 삽입
6. insert_before(data, node) : data를 node 이전에 삽입
7. search_forward(target) -> node : target을 리스트의 맨 처음부터 찾아 나가다 리스트에 있으면 노드 반환, 그렇지 않으면 None 반환
8. search_backward(target) -> node : target을 리스트의 맨 마지막부터 찾아 나가다 리스트에 있으면 노드 반환, 그렇지 않으면 None 반환
9. delete_first( ) : 리스트의 첫 번째 요소 삭제
10. delete_last( ) : 리스트의 마지막 요소 삭제
11. delete_node(node) : node 삭제# double_linked_list.py class Node: def __init__(self, data=None): self.__data == data self.__prev == None self.__next == None # 소멸자 : 객체가 사라지기 전 반드시 호출됩니다. # 삭제 연산 때 삭제되는 것을 확인하고자 작성했습니다. def __del__(self): print(f"data of {self.data} is deleted") @property def data(self): return self.data @data.setter def data(self, data): self.__data = data @property def prev(self): return self.__prev @prev.setter def prev(self, p): self.__prev = p @property def next(self): return self.__next @next.setter def next(self, n): self.__next = n위의 코드는 더미 이중 연결 리스트에서 데이터를 저장할 노드를 구현한 것입니다. 노드 클래스의 생성자를 보면 데이터를 저장할 __data, 이전 노드를 참조할 __prev, 다음 노드를 참조할 __next가 멤버입니다. 프로퍼티를 이용하여 캡슐화했습니다.
이제 DoubleLinkedList 클래스를 만들어 보겠습니다. 먼저 인스턴스 멤버를 고민해 봅니다. 더미 리스트이므로 더미를 가지고 있어야 하겠지요. 리스트의 맨 앞에 더미 노드를 하나 만들고 이를 head라는 인스턴스 멤버로 가리키게 합니다. 리스트의 맨 마지막에도 더미 노드를 하나 만들고 이를 tail이라는 인스턴스 멤버로 가리키게 합니다. 그리고 이 둘을 연결해서 초기화합니다. 마지막으로 리스트에 데이터가 몇 개 있는지 저장하고자 d_size라는 인스턴스 멤버를 둡니다.
# double_linked_list.py class DoubleLinkedList: def __init__(self): # 리스트의 맨 처음과 마지막은 실제 데이터를 저장하지 않는 노드입니다. 이를 더미노드라고 합니다. # 초기화 self.head = Node() self.tail = Node() # head와 tail 연결 self.head.next = self.tail self.tail.prev = self.head # 데이터 개수를 저장할 변수 self.d_size = 0위의 코드를 아래의 그림과 같이 표현했습니다. 중요한 점은 head와 tail이 가리키는 더미 노드에는 데이터가 저장되어 있지 않다는 것입니다.
이제 ADT에 정의된 연산을 구현해 보겠습니다.
(tips)
add_first() 메서드와 add_last(), insert_after(), insert_before() 메서드는 로직이 비슷합니다.
add_first 함수는 맨 앞의 더미 노드와 첫 번째 노드 사이에 새로운 노드를 삽입합니다. 
head가 가리키는 더미 노드 다음에 이 새로운 노드를 삽입해야 합니다. 새로운 노드의 prev와 next를 연결합니다. 
새로운 노드의 prev와 next를 각각 더미 노드와 첫 번째 데이터 노드에 연결해 줍니다. 
head의 next와 첫 번째 데이터 노드의 prev가 새로운 노드를 가리키게 합니다. (순서대로 연결해야 에러가 나지 않습니다.) # double_linked_list.py def add_first(self, data): new_node=Node(data) new_node.next=self.head.next new_node.prev=self.head self.head.next.prev=new_node self.head.next=new_node self.d_size+=1 def add_last(self, data): new_node=Node(data) new_node.prev=self.tail.prev new_node.next=self.tail self.tail.prev.next=new_node self.tail.prev=new_node self.d_size+=1 def insert_after(self, data, node): new_node=Node(data) new_node.next=node.next new_node.prev=node node.next.prev=new_node node.next=new_node self.d_size+=1 def insert_before(self, data, node): new_node=Node(data) new_node.prev=node.prev new_node.next=node node.prev.next=new_node node.prev=new_node self.d_size+=1 def search_forward(self, target): cur=self.head.next while cur is not self.tail: if cur.data==target: return cur cur=cur.next return None def search_backward(self, target): cur=self.tail.prev while cur is not self.head: if cur.data==target: return cur cur=cur.prev return None def delete_first(self): if self.empty(): return self.head.next=self.head.next.next self.head.next.prev=self.head self.d_size-=1 def delete_last(self): if self.empty(): return self.tail.prev=self.tail.prev.prev self.tail.prev.next=self.tail self.d_size-=1 def delete_node(self, node): node.prev.next=node.next node.next.prev=node.prev self.d_size-=1'Algorithm' 카테고리의 다른 글
자료구조 핵심 원리 - 그래프 (0) 2022.09.24 자료구조 핵심 원리 - 스택과 큐 (0) 2022.09.23 자료구조 핵심 원리 - 동적 배열 (1) 2022.09.23 자료구조 핵심 원리 - 재귀 함수 (0) 2022.09.22 자료구조 - 그래프 (0) 2022.02.24