[03-6] 연결 리스트(Linked List) - 이중 연결 리스트(Doubly Linked List)

1. 개요 & 알고리즘

단순 연결 리스트와 달리 이중 연결 리스트는 다음 노드를 가리키는 링크와 이전 노드를 가리키는 링크 두 가지를 가져서 바로 이전 노드에 접근할 수 있다는 차이점이 있습니다. ("C로 배우는 알고리즘"^[각주:1])

2. 동작 코드

지금까지는 Class에서 Node에 대한 정보를 return하지 않고, Class 내부적으로만 처리하도록 하였으나, 이번에는 Node 정보를 Class 외부에서 입력 받거나 출력할 수 있도록 진행합니다.

Doubly Linked List는 링크로 next 이외에 prev를 갖게 됩니다.

class Node:
    def __init__(self, key=-1):
        self.key = key
        self.prev = None
        self.next = None

최초 Class 생성시, head와 tail 노드를 생성하고, 각각이 prev와 next로 가리키도록 합니다.

# Class for doubly linked list
class LinkedList:
    def __init__(self):
        self.head = Node(-1)
        self.tail = Node(-1)
        self.head.next = self.tail
        self.head.prev = self.head
        self.tail.next = self.tail
        self.tail.prev = self.head

List에 포함된 노드 t 앞에 key 값을 갖는 새로운 노드를 삽입하는 함수는 다음과 같습니다.

# Insert new node ahead of tNode
def insert_dnode_ptr(self, key, tNode):
    if tNode == self.head:
        return None
    iNode = Node(key)
    tNode.prev.next = iNode
    iNode.prev = tNode.prev
    tNode.prev = iNode
    iNode.next = tNode

특정 노드 t를 지우는 함수는 다음과 같습니다.

def delete_dnode_ptr(self, tNode):
    # Can't remove head and tail
    if tNode == self.head or tNode == self.tail:
        return 0
    tNode.prev.next = tNode.next
    tNode.next.prev = tNode.prev

    return tNode

특정 Key 값을 갖는 노드를 찾는 함수는 다음과 같습니다. Key 값을 갖는 노드를 찾지 못하면 "False"를 return 합니다.

def find_node(self, key):
    s = self.head.next
    while s.key != key and s != self.tail:
        s = s.next
    if s == self.tail:
        return False
    else:
        return s

3. 실행 코드

Doubly Linked List 관련 실행 코드는 다음과 같습니다. ("C로 배우는 알고리즘" 리스트 3-6 : LINKED2.C에 대응)

#main() function
if __name__ == "__main__":
    list = LinkedList()
    list.ordered_insert(10)
    list.ordered_insert(5)
    list.ordered_insert(8)
    list.ordered_insert(3)
    list.ordered_insert(1)
    list.ordered_insert(7)
    list.ordered_insert(8)

    print("Initial linked list is")
    list.print_all()

    print()
    findNumber = 4
    if list.find_node(findNumber) != False:
        print("Finding %d is successful" % findNumber)
    else:
        print("Finding %d is unsuccessful" % findNumber)

    print()
    findNumber = 5
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful" % findNumber)
    else:
        print("Finding %d is unsuccessful" % findNumber)

    print()
    print("Inserting 7 before 5")
    list.insert_dnode_ptr(7, t)
    list.print_all()

    print()
    findNumber = 3
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful and Deleting" % findNumber)
        list.delete_dnode_ptr(t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    findNumber = 10
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful" % findNumber)
        print("Inserting 2 before %d" % findNumber)
        list.insert_dnode_ptr(2, t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    findNumber = 2
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful and Deleting" % findNumber)
        list.delete_dnode_ptr(t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    findNumber = 1
    t = list.find_node(findNumber)
    if t != False:
        print("Finding %d is successful and Deleting" % findNumber)
        list.delete_dnode_ptr(t)
    else:
        print("Finding %d is unsuccessful" % findNumber)
    list.print_all()

    print()
    print("Inserting 15 at last")
    list.insert_dnode_ptr(15, list.head.next)
    list.print_all()

    print()
    print("Delete all node")
    list.delete_all()
    list.print_all()

4. Tips

1. Python의 class는 특별히 public, private, protected등의 keyword를 제공하지 않으며, 일반적으로 class내에 선언된 변수들은 외부에서 access가 가능합니다^[각주:2]. 앞으로는 이를 그대로 사용하기로 합니다.

2. C 언어와 비슷하게 print()에 format을 지정해서 출력할 수 있습니다.^[각주:3]

3. Python에서 문자열의 비교는  equal을 사용해서 그냥 비교하면 됩니다.

5. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_6.py

1. http://www.yes24.com/24/goods/18003 [본문으로]
2. http://ehpub.co.kr/30-python%EC%97%90%EC%84%9C%EC%9D%98-%EC%BA%A1%EC%8A%90%ED%99%94-%EC%A0%95%EB%B3%B4-%EC%9D%80%EB%8B%89%EC%9D%84-%EC%9C%84%ED%95%9C-%EC%A0%91%EA%B7%BC-%EC%A7%80%EC%A0%95/ [본문으로]
3. https://www.python-course.eu/python3_formatted_output.php [본문으로]