연결 리스트: 코딩, 시연 (linked list)

CS50 2019 강의를 듣고 내용을 정리한 시리즈 글입니다.

---

학습목표

연결 리스트를 구현하고 사용할 수 있습니다.

핵심 단어

• 연결 리스트

강의 내용

1. 연결 리스트(linked list)

실제로 연결 리스트를 구현해보도록 하자.

참고: tutorialspoint.com

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class SLinkedList:
    def __init__(self):
        self.headval = None

    # linked list 출력
    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval

    # Head에 NewNode 추가
    def AtBegining(self,newdata):
        NewNode = Node(newdata)

        # NewNode -> first Node, NewNode를 Head 데이터로 변경
        NewNode.nextval = self.headval
        self.headval = NewNode

    # Tail에 NewNode 추가
    def AtEnd(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        laste = self.headval
        while(laste.nextval):
            laste = laste.nextval
        laste.nextval=NewNode

    # 두 Node 사이에 NewNode 추가
    def Inbetween(self,middle_node,newdata):
        if middle_node is None:
            print("The mentioned node is absent")
            return

        NewNode = Node(newdata)
        NewNode.nextval = middle_node.nextval
        middle_node.nextval = NewNode

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node -> second node
list.headval.nextval = e2

# Link second Node -> third node
e2.nextval = e3

# Head
list.AtBegining("Sun")
# Tail
list.AtEnd("Fri")
# Between
list.Inbetween(e3,"Thu")

#결과
list.listprint()
Sun
Mon
Tue
Wed
Thu
Fri

생각해보기

연결 리스트의 중간에 node를 추가하거나 삭제하는 코드는 어떻게 작성할 수 있을까요?

삽입, 삭제를 할 때 유의할 점은 추가 또는 삭제가 되는 전후구간의 연결 고리가 끊어지지않게 유지해야한다는 것이다.

예를 들면 A, C 노드사이에 B 노드를 추가하려고 한다면 먼저 B노드에 C노드의 주소값을 할당하고 A노드에 B노드의 주소값을 할당하는 방식이다.

반대로 A, B, C 사이에서 B 노드를 삭제하려면 A노드에 C노드의 주소값을 할당한 후 B노드의 데이터를 삭제하면 된다.

배열이 정렬되어 있지 않은 경우의 검색 소요 시간을 연결 리스트의 검색 시간과 비교해보세요.

연결리스트와 정렬되지 않은 배열의 검색소요시간은 O(N)으로 동일하다.