반응형
(Codes : https://github.com/J-Hoplin/Algorithm-with-Python/tree/master/4%20.%20Double%20Linked%20List)
1 . Doubly Linked List
앞에서 보았던 연결리스트는 단일 연결 리스트(Singly Linked List)였다. 연결리스트는 배열과 같이 물리적 메모리적 메모리가 아닌 링크라는 형식의 개념을 사용하기에 관리하기가 매우 쉬웠다. 하지만 단일 연결리스트의 한계가 있다. 바로 일방성이라는것이다. 한방향으로만 나아갈 수 있을뿐 그와 반대방향으로 링크를 시킬 수 없다는 단점이 존재한다.
앞으로 볼 이중 연결리스트는 단일 연결리스트와 달리 양방향성을 지니고 있다.
다음 사진을 보자. 임의의 링크는 자신의 다음 링크도 가리키지만 반대로 그 전의 링크도 가리키고 있는 모습을 볼 수 있다. 이중 연결리스트의 기본적인 코드 구조를 보면 다음과 같다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | class Node: def __init__(self,data,link = None,before = None): self.data = data self.link = link self.before = before def p_list(): global node_a node_a = Node("A") node_b = Node("B") node_d = Node("D") node_e = Node("E") node_a.link = node_b node_b.link = node_d node_b.before = node_a node_d.link = node_e node_d.before = node_b def print_all(): global node_a node = node_a while node: print(node.data) node = node.link if __name__=="__main__": print("Double Linked List's Nodes") p_list() print_all() | cs |
필자가 작성한 코드의 구조를 그려보면 다음과 같은 구조를 띄게 된다.
결론적으로 보면 앞의 단일 연결리스트와의 다른점이라면 Before이라는 멤버가 하나 추가되어 head와 tail부분을 제외하고는 그 외 노드들이 자신의 이전 노드를 가리키는것을 볼 수 있다.
2 . Doubly Linked List - Insertersection Algorithm
단일 연결리스트에서도 봤듯이 이중 연결리스트에서도 삽입과 삭제 알고리즘이 존재한다. 우선 삽입 알고리즘 부터 살펴보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | class Node: def __init__(self,data,link = None,before = None): self.data = data self.link = link self.before = before def p_list(): global node_a node_a = Node("A") node_b = Node("B") node_d = Node("D") node_e = Node("E") node_a.link = node_b node_b.link = node_d node_b.before = node_a node_d.link = node_e node_d.before = node_b def insert(data): global node_a new = Node(data) node_1 = node_a node_2 = node_a while node_2.data <= data: node_1 = node_2 node_2 = node_2.link node_2.before = new new.link = node_2 new.before = node_1 node_1.link = new def print_all(): global node_a node = node_a while node: print(node.data) node = node.link if __name__=="__main__": print("Double Linked List's Nodes") p_list() print_all() print("Double Linked List's Intersection Algorithm") insert("C") print_all() | cs |
우선 앞에서도 말했듯이 이중 연결리스트와 단일 연결리스트의 차이점은 일방향성과 양방향성이고, 그에 따라 이중 연결리스트는 before이라는 멤버를 추가하여 head와 tail 노드 외의 노드들은 자신의 다음과 이전 노드를 모두 가리킬 수 있는것이었다. 이중 연결리스트의 삽입 연결 리스트 역시 단일 연결리스트에서 before멤버만 추가해주면 되는것이다.
우선 연결리스트에 해당하는 부분의 코드를 살펴보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 | def insert(data): global node_a new = Node(data) node_1 = node_a node_2 = node_a while node_2.data <= data: node_1 = node_2 node_2 = node_2.link node_2.before = new new.link = node_2 new.before = node_1 node_1.link = new | cs |
우선 코드를 살펴보자. 정말 간단히 해석해 보면 data라는 인자로 값을 받고 해당 값에 대한 노드를 생성한다. 그 후 새로 삽입할 노드, Node(data)의 자리를 while문을 통해 각 노드의 data멤버에 대한 값을 비교하며 자리를 찾고, 해당 자리를 찾으면 삽입하려는 노드의 다음 노드가 되는 node_2의 before멤버에는 새로운 노드 new에 링크를, 삽입하려는 노드의 이전 노드에 해당하는 node_1의 link부분을 새로운 노드에 해당하는 new에 링크를 지정해주면 된다. 그 다음 동일하게 새로운 노드의 before멤버에는 node_1값을 link멤버에는 node_2에 대해 링크를 걸어주면 된다. 삽입 알고리즘을 하나씩 해석해보면 다음과 같다.
3 . Doubly Linke List - Delete Algorithm
단일연결리스트에서 했듯이 노드 삽입 알고리즘을 보았으니 이번에는 반대로 이중 연결 리스트에서 노드를 삭제하는 알고리즘도 다루어 보자.
원리는 앞에서 본 이중 연결리스트와 동일하다. 삭제해준 노드에 대해 해당 노드의 이전노드의 link멤버는 삭제되는 노드의 link멤버로 링크를 한 노드를 삭제되는 노드의 다음 노드에 대해서, before멤버에는 삭제되는 노드의 before멤버로 링크한 노드를 링크해주면 된다. 우선 코드를 살펴보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | class Node: def __init__(self,data,link = None, before = None): self.data = data self.link = link self.before = before def p_list(): global node_a global node_e node_a = Node("A") node_b = Node("B") node_d = Node("D") node_e = Node("E") node_a.link = node_b node_b.link = node_d node_b.before = node_a node_d.link = node_e node_d.before = node_b node_e.before = node_d def insert(data): global node_a new = Node(data) node_1 = node_a node_2 = node_a while node_2.data <= new.data: node_1 = node_2 node_2 = node_2.link node_1.link = new node_2.before = new new.link = node_2 new.before = node_1 def delete(dele): global node_a global node_e node_1 = node_a node_2 = node_1.link node_3 = node_2.link node_Tail = node_e if node_Tail.data == dele: node_e = node_e.before node_e.link = None del node_Tail if node_1.data == dele: node_a = node_2 del node_1 return while node_2: if node_2.data == dele: node_3 = node_2.link node_1.link = node_2.link node_3.before = node_2.before del node_2 break node_1 = node_2 node_2 = node_2.link def print_all(): global node_a node = node_a while node: print(node.data) node = node.link if __name__ == "__main__": print("Doubly Linked List Nodes") p_list() print_all() print("Doubly Linked List Intersection Nodes") insert("C") print_all() print("Doubly Linked List Delete Algorithm - 1") delete("E") print_all() print("Doubly Linked List Delete Algorithm - 2") delete("A") print_all() print("Doubly Linked List Delete Algorithm - 3") delete("C") print_all() | cs |
해당 코드는 위에서 보았던 삽입 알고리즘도 포함되어있다. 우선 출력문의 Doubly Linked List Delete Algorithm -1 부터 보자. 필자는 예시에서 등장하는 전체링크의 Tail에 해당하는 E노드와 Head에 해당하는 A를 그리고 그 사이 임의의 노드 C를 순서대로 제거하는것을 예시로 작성하였다. 필자가 이 세가지 경우를 나눠서 한 이유는 이 뒤의 글을 읽기전 삭제 알고리즘에 해당하는 코드를 직접 작성해보고 생각해 보는것을 추천한다.
우선 삭제 알고리즘에 해당하는 코드를 살펴보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | def delete(dele): global node_a global node_e node_1 = node_a node_2 = node_1.link node_3 = node_2.link node_Tail = node_e if node_Tail.data == dele: node_e = node_e.before node_e.link = None del node_Tail if node_1.data == dele: node_a = node_2 del node_1 return while node_2: if node_2.data == dele: node_3 = node_2.link node_1.link = node_2.link node_3.before = node_2.before del node_2 break node_1 = node_2 node_2 = node_2.link | cs |
우선 지금까지 스스로 코드를 작성해보았던 사람이라면 변화점중 하나가 보일것이다. 바로 Tail부분의 노드에 해당하는 node_e를 전역변수 처리를 하여 사용하였다는 것이다. 물론 node_e를 전역변수 처리할때는 delete함수에서만 전역변수 처리를 하는것이 아닌 처음 노드들을 선언하는 부분인 p_list()함수에서도 node_e에 대해 전역변수 처리를 해주어야 한다.(global node_e)
우선 우리가 앞에서 보았던 단일 연결리스트에서의 삭제 알고리즘을 살펴보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def delete(dele): global node_a pre = node_a next = node_a.link if pre.data == dele:#첫번쨰 노드가 삭제해야할 대상인 경우 node_a = next del pre return while next:#두번째 이상의 노드를 삭제해야할 경우 if next.data == dele: pre.link = next.link del next break pre = next next = next.link | cs |
단일 연결 리스트에서는 우선적으로 node_a를 선언하고 우선적으로 head 노드에 해당하는 데이터가 삭제하고자 하는 데이터일때의 삭제 알고리즘을 작성해준다. 여기서는 전역변수 처리를 해준 node_a에 대해 다음 노드를 가리키는 next를 대입해줌으로서 결론적으로 node_a객체가 node_a의 다음객체인 node_b를 가리키게 한다.
그 후 node_a에 해당하는 pre를 삭제하고 delete()함수를 종료한다. 그 밑의 while문에 대해서는 두번째 노드인 node_b부터 탐색을 시작해 삭제하고자 하는 부분을 찾으면 해당 노도의 이전 노드인 pre노드에 대해 link멤버를 삭제하고자 하는 노드의 link멤버의 값에 링크해준다. 그 후 삭제하고자 하는 노드에 해당하는 next 노드를 삭제하고 함수를 종료한다.
이번에는 반대로 이중 연결리스트의 코드를 살펴보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | def delete(dele): global node_a global node_e node_1 = node_a node_2 = node_1.link node_3 = node_2.link node_Tail = node_e if node_Tail.data == dele: node_e.before.link = None del node_Tail if node_1.data == dele: node_a = node_2 del node_1 return while node_2: if node_2.data == dele: node_3 = node_2.link node_1.link = node_2.link node_3.before = node_2.before del node_2 break node_1 = node_2 node_2 = node_2.link | cs |
우선 앞에서 보았던 단일 연결리스트와 달리 tail노드에 해당하는 node_e를 선언해 주었다. 또한 노드를 총 3개를 선언해 주었다. 이에 대해 의문점이 드는 사람도 있을것이다. 왜 노드를 3개를 선언하며 왜 tail노드인 node_e를 전역처리하여 선언하였는가에 대해 말이다. 우선 첫번째 if문부터 살펴보자. node_Tail, 즉, Tail노드에 해당하는 node_e를 담고있는 변수 node_Tail이 만약 삭제하고자 하는 데이터라면 우선적으로 node_e.before,즉 node_d가 결론적으로 가리키는 값이 사라지는 것이다. 이에 대해 링크를 끊어주기 위해 node_e의 이전 노드 node_d의 link 부분을 None값을 대입하여 가리키는 값이 없도록 만들어 준다.
그 다음 두번째 if문에 대해서는 위에서 보았던 단일 연결 리스트와 동일하게 삭제하고자 하는 노드가 첫번째 노드인 경우에 대한 조건문이다. 세번째로 while문을 보자. 위에서 단일 연결 리스트에서 보았던것과 동일하게 삭제할 노드에 대한 탐색을 하는것과 같다. 하지만 여기서 더 추가된게 있다. 이중 연결리스트는 계속 말했듯이 양방향성이다. 즉 삭제하고자 하는 노드가 있다면 자신의 이전 노드의 link멤버에 대한 링크 뿐만 아니라 자신의 다음 노드의 before멤버에 대한 링크 또한 신경 써주어야 한다.
while문 안의 if문을 보면 node_3에는 node_2.link, 즉 삭제되고자 하는 노드의 다음 노드를 대입해주고, node_3의 이전 노드를 가리키는 before멤버는 결론적으로 자신의 이전 노드인 node_2가 삭제되므로, node_2의 이전 노드인 node_1에 대해 링크가 되어야 한다. 코드에서는 node_1을 node_2.before를 통해 대입해 주었다.
또한 삭제되는 노드 node_2의 이전 노드인 node_1에 대해서는 node_1은 결론적으로 삭제되는 node_2의 다음 노드인 node_3에 대해 링크가 되어야 하므로 node_1의 link 멤버에 대해서는 node_3에 해당하는 node_2.link를 대입해 주었다. 그 후 node_2를 삭제해주고 해당 삭제문을 나가준다.
혹시라도 해당 코드에서 마지막 tail노드에 대해 삭제하는걸 굳이 따로 빼는거에 대해 의문을 가질 수 도 있기에 작성해본다. 만약 tail노드(예시에서는 node_e)를 삭제하는 첫번째 if문이 없이 그냥 while문 상에서 tail노드를 삭제하려 시도하면 오류가 발생할 수 밖에 없다. 우선적으로 tail노드는 해당 링크에서 가장 마지막 노드이므로 tail, head사이의 노드들에 대해서는 삭제하고자 하는 노드의 이전노드, 다음 노드가 존재하여 while문 안의 노드들의 before, link멤버에 대한 설정이 가능한것으로 성립한다. 하지만 만약 delete("E")로 작성한 상태에서 코드를 실행하면 None타입에 대해서는 before멤버의 값을 설정할 수 없다는 오류가 뜰것이다. 이에 대한 이유는 해당 부분에 의문점을 가지고 지금 이 부분을 읽고있는 당신이 생각해보았으면 좋겠다.
해당 코드의 필자의 결과값은 다음과 같다.
4 . 결론
그렇다면 결론적으로 이중 연결리스트의 장점은 무엇이 되는것일까? 단일 연결 리스트와 달리 이중 연결 리스트는 하나의 노드에는 링크가 두개가 존재한다. 그렇기 때문에 단일 연결 리스트처럼 일방적인 탐색이 아닌 양방향성으로 전체탐색이 가능하기 때문에 전반적인 탐색 시간이 단일 연결리스트에 비해 훨씬 짧아질 수 있다는 장점이 있는것이다.
반응형
'CS 지식 > Algorithm-이론 및 PS스킬 정리' 카테고리의 다른 글
| 파이썬 Extended Slices (0) | 2019.09.09 |
|---|---|
| O 표기법(Big - O Notation), 쎄타 표기법(Theta Notation), 오메가 표기법(Omega Notation) (0) | 2019.03.18 |
| 순서도(Flow Chart)에 대해 (0) | 2019.01.16 |
| Base Algorithm with Python #2 (0) | 2019.01.13 |
| Base Algorithm with Python #1 (0) | 2019.01.13 |
