[패스트캠퍼스][환급 챌린지]Chapter 2. 딥러닝을 위한 자료 구조 02-03 연결 리스트

02-03 연결 리스트

def) 연결 리스트 (Linked List): 각 노드가 한 줄로 연결되어 있는 자료구조
지난 시간에 배열을 설명하면서 곁다리로 언급했던 연결 리스트에 대해 좀 더 자세히 알아보겠습니다. 각 노드는 (데이터, 포인터)의 한 쌍으로 묶여 있으며, 이러한 각 노드가 한 줄로 연결되어 있는 것이 연결 리스트입니다.
여기서 포인터는 다음 노드의 메모리 주소를 가리키는 역할을 합니다. 각 노드의 포인터가 다음 혹은 이전 노드를 가리키는 것을 연결성이라고 합니다.
연결 리스트를 이용하면 앞으로 배울 스택, 큐 등 다양한 자료구조를 구현할 수 있습니다. 다만, 우리가 데이터 사이언스와 ML 분야에서 주로 사용하는 파이썬은 연결 리스트를 활용하는 자료구조인 리스트(list)를 자체적으로 제공합니다. 따라서 우리가 연결 리스트를 실제로 구현해야 할 필요는 없지만, 최소한 그 원리를 알고 있는 것이 앞으로 프로그래밍에 있어서 중요할 겁니다.

연결 리스트 vs. 배열

배열에 대해서 다시 짚고 넘어가보죠. 특정 위치의 데이터를 삭제할 때, 배열에서는 일반적으로 $O\left(N\right)$의 시간이 소요됩니다. 하지만, 연결 리스트를 이용하면 단순히 특정 위치의 데이터의 연결만 끊어주면 되기 때문에, 삭제할 위치를 정확히 알고 있는 경우에 한해 $O\left(1\right)$이 소요됩니다.

뒤에 붙이기 연산

연결 리스트에서는 배열의 크기와 무관하게 새로운 원소를 뒤에 붙이는(append) 연산을 할 수 있습니다. 이 때도 마지막 노드의 다음 위치에 포인터로 연결해주기만 하면 됩니다.

파이썬에서 연결 리스트 구현하기

앞에서 말했듯이 굳이 파이썬에서 연결 리스트를 구현할 필요는 없지만, 그 작동 원리를 알기 위해 코드로 직접 구현해보면 좋을 것 같습니다. 아래 예제 코드는 본 수업에서 제공된 코드입니다. 아직 파이썬이나 코딩 전반에 대해 익숙하지 않으신 분들은 이해가 어려우실 수 있으니 이해 바랍니다....

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    # Insert node at the tail
    def append(self, data):
        # If the head is empty
        if self.head == None:
            self.head = Node(data)
            return
        # Append a new node at the tail
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)

    # Print each nodes
    def show(self):
        cur = self.head
        while cur is not None:
            print(cur.data, end=" ")
            cur = cur.next

    # Find out the node of a certain index
    def search(self, index):
        node = self.head
        for _ in range(index):
            node = node.next
        return node

    def insert(self, index, data):
        new = Node(data)

        if index==0:
            new.next = self.head
            self.head = new
            return

        node = self.search(index-1)
        next = node.next
        node.next = new
        new.next = next

    def remove(self, index):
        if index==0:
            self.head = self.head.next
            return

        front = self.search(index-1)
        front.next = front.next.next

Node와 LinkedList라는 두 클래스를 정의하여 설명한 예제입니다. Node는 현재 데이터의 노드를 나타내고, LinkedList는 노드에 대한 각종 연산을 지원하는 메서드를 탑재하고 있습니다.
이를 이용해 풀이를 해보면, linked_list라는 변수에 LinkedList() 클래스의 객체를 하나 생성해줍니다. data_list는 이 예제에서 사용한 리스트의 각 원소들의 값입니다.

linked_list = LinkedList()
data_list = [3, 5, 9, 8, 5, 6, 1, 7]

for data in data_list:
    linked_list.append(data)

print("Print all nodes:", end=" ")
linked_list.show()

linked_list.insert(4, 4)
print("\nPrint all nodes:", end=" ")
linked_list.show()

linked_list.remove(7)
print("\nPrint all nodes:", end=" ")
linked_list.show()

linked_list.insert(7, 2)
print("\nPrint all nodes:", end=" ")
linked_list.show()

 

20일차 후기

손으로 직접 코딩한 걸 따라 타이핑해보면서 학습하시기를 적극 권장합니다! 눈으로 보기만 해서는 오히려 안 하느니만 못한 학습 결과가 나올 수 있습니다. 머리로는 아는데 손으로 구현하면 잘 안 되는 건 자연스러우니까 계속 반복해서 이런 예제 코드들을 직접 타이핑해보시기를 권합니다.

그렇다고 진짜 무지성으로 보고 따라서 치기만 하진 마시고...

http://bit.ly/3Y34pE0

패스트캠퍼스 [직장인 실무교육]

* 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.