[03-4] 연결 리스트(Linked List) - 단순 연결 리스트(Simple Linked List)

1. 사전 지식

"C로 배우는 알고리즘"^[각주:1]에 설명된 Linked List에 대한 주요 내용은 다음과 같습니다.

1. Linked List는 Node와 Link로 구성됨

2. Linked List는 Link의 개수와 연결 상태에 따라 "단순 연결 리스트", "환형 연결 리스트", "이중 연결 리스트", "이중 환형 연결 리스트"등이 있음

2. Simple Linked List

• Simple Linked List는 "정보를 저장하는 Node"와 "바로 다음 Node를 가리키는 Link" 하나로 구성됩니다.
• Linked List의 최대 장점은 재배열(rearrangement)이 쉽다는 것입니다.
• 관리를 위해서 Head Node와 Tail Node를 가집니다.

Python 배열은 그 자체로 append()나 remove()등을 제공합니다만, Python으로 Linked List를 구현한 웹문서들^[각주:2],^[각주:3],^[각주:4],^[각주:5]을 찾을 수 있었습니다. 이들 코드를 모두 참조하여 C로 배우는 알고리즘"에 있는 내용을 구현하였습니다.

Integer type의 key를 처리하는 class 구현을 목표로 하며, 구태여 Node 자체가 class 외부로 return되지는 않도록 설계합니다. 따라서 "C로 배우는 알고리즘"에 있는 insert_after(), delete_next(), find_node(), insert_node(), delete_all()는 구현하지 않고, delete_node(), ordered_insert(), print_list() 일부만 구현하는 것으로 합니다.

2. 동작 코드

Node는 class로 구현합니다. Node 생성시 Key 값이 입력되지 않으면 '-1'을 사용하도록 하였습니다. Key는 예제 목적상 integer를 입력 받는 것을 가정합니다.

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

Global로 head와 tail을 선언해서 작성해도 되겠지만, class 내에서 처리할 수 있도록 LinkedList라는 class를 작성했습니다. "C로 배우는 알고리즘"에 있듯이 head는 tail을, tail을 tail을 next로 지정하였습니다.

key 입력에 따라 정렬한 상태로 입력할 수 있도록 ordered_insert() 함수와 해당 key 값의 node를 지우고, 모든 node들을 print하는 함수를 작성하였습니다.

class LinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.next = self.tail

    def ordered_insert(self, key):
        newNode = Node(key)
        p = self.head
        s = p.next
        while s.key <= key and s != self.tail:
            p = p.next
            s = p.next
        p.next = newNode
        newNode.next = s

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

    def print_node(self):
        p = self.head
        p = p.next
        print("Start", end=" ")
        while p != self.tail:
            print(p.key, "->", end=" ")
            p = p.next
        print("End")

3. 실행 코드

Simple Linked List 함수들의 실행 코드는 아래와 같습니다. ("C로 배우는 알고리즘" 리스트 3-4 : LINKED1.C에 대응)

ordered_insert() 함수로 임의의 integer type의 key값을 갖는 node들을 생성한 후 print합니다. 그리고 하나의 node를 그리고 다시 print합니다.

#main() function
if __name__ == "__main__":
    list = LinkedList()
    list.ordered_insert(7)
    list.ordered_insert(8)
    list.ordered_insert(1)
    list.ordered_insert(9)
    list.print_node()

    list.delete_node(7)
    list.print_node()

5. 코드

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

1. http://www.yes24.com/24/goods/18003 [본문으로]
2. https://wayhome25.github.io/cs/2017/04/17/cs-19/ [본문으로]
3. http://onestep.tistory.com/33 [본문으로]
4. http://sjce.tistory.com/8 [본문으로]
5. http://doorbw.tistory.com/117 [본문으로]