TIL-067 | 연결 리스트(Linked List)

Lee, Chankyu·2022년 1월 14일

TIL algorithm

자료구조&알고리즘

목록 보기

6/12

🌈 연결 리스트(Linked List)

연결 리스트 란?

연결 리스트는 노드들로 이어진 리스트를 의미한다.
노드는 데이터를 저장하는 부분과, 다음 노드를 가르키는 부분으로 구성되어있다.
연결 리스트는 처음과 끝을 가르키는 포인터들을 이용해 리스트를 관리하고, 끝 노드는 null값을 가지고 있다.
제일 앞에 있는 노드는 헤드(head), 제일 끝 노드는 테일(tail)이라고 부른다. 아무 데이터가 없는 노드는 더미노드 라고 부른다.
linked list에서 가장 중요한 것은 연결이 무엇인가를 파악하는 것이다.
연결되는 방향에 따라 단일 연결 리스트(Single Linked List), 이중 연결 리스트(Double Linked List), 원형 연결 리스트(Circular Linked List)의 종류가 있다.
python 의 경우 list 기본 자료형에 linked list 기능이 함께 포함되어 있다.

연결 리스트의 장점

연결 리스트의 길이를 동적으로 조절 가능하다.
데이터의 삽입과 삭제가 쉽다.

연결 리스트의 단점

임의의 노드에 바로 접근할 수 없다.
다음 노드의 위치를 저장하기 위한 추가 공간이 필요하다.
Cache locality를 활용해 근접 데이터를 사전에 캐시에 저장하기가 어렵다.
연결 리스트를 거꾸로 탐색하기가 어렵다

👉 데이터가 자주 추가되거나 가변적으로 자주 변하게 될 프로그램이라면 링크드리스트를 쓰는 것이 효율적이고, 주로 데이터의 변경이나 탐색을 위한 것이라면 배열을 쓰는 것이 좋다.

단일 연결 리스트의 구현

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

class Linkedlist:
    # 초기화 메소드
    def __init__(self):
        dummy = Node("dummy")
        self.head = dummy
        self.tail = dummy

        self.current = None
        self.before = None

        self.num_of_data = 0

    # append 메소드 (insert - 맨 뒤에 노드 추가, tail과 node의 next, 데이터 개수 변경)
    def append(self, data):
        new_node = Node(data)
        self.tail.next = new_node
        self.tail = new_node

        self.num_of_data += 1

    # delete 메소드 (delete - current 노드 삭제, 인접 노드의 current, next 변경, 데이터 개수 변경)
    def delete(self):
        delete_data = self.current.data

        if self.current is self.tail:
            self.tail = self.before

        self.before.next = self.current.next
        self.current = self.before # 중요 : current가 next가 아닌 before로 변경된다.
        #

        self.num_of_data -= 1

        return delete_data

    # first 메소드 (search - 맨 앞의 노드 검색, before, current 변경)
    def first(self):
        if self.num_of_data == 0: # 데이터가 없는 경우 첫번째 노드도 없기 때문에 None 리턴
            return None

        self.before = self.head
        self.current = self.head.next

        return self.current.data

    # next 메소드 (search - current 노드의 다음 노드 검색, 이전에 first 메소드가 한번은 실행되어야 함)
    def next(self):
        if self.current.next == None:
            return None

        self.before = self.current
        self.current = self.current.next

        return self.current.data

    # size 메소드
    def size(self):
        return self.num_of_data

if __name__ == '__main__':
    linkedlist = Linkedlist()
    linkedlist.append(1)
    linkedlist.append(2)
    linkedlist.append(3)
    linkedlist.append(4)
    linkedlist.append(5)
    linkedlist.append(6)
    linkedlist.append(7)

print(linkedlist.first())       # 1
print(linkedlist.next())        # 2
print(linkedlist.size())        # 7
print(linkedlist.delete())      # 2
print(linkedlist.size())        # 6
print(linkedlist.current.data)  # 1
print(linkedlist.tail.data)     # 7
print(linkedlist.first())       # 1
print(linkedlist.next())        # 3
print(linkedlist.next())        # 4
print(linkedlist.next())        # 5

이중 연결 리스트(Double Linked List)

단순 연결 리스트는 선행 노드에 접근하기가 어렵다. 그래서 이를 개선하기 위해 원형 연결 리스트를 구성했지만, 원형 연결 리스트에서도 현재 노드의 선행 노드에 접근하기 위해서는 전체 리스트를 한바퀴 순회해야 하는 문제가 생긴다.
이러한 문제점들을 보완하기 위해 이중 연결 리스트(Doubly Linked List)가 있다.
이중 연결 리스트는 각 노드가 선행 노드와 후속 노드에 대한 링크를 가지는 리스트이다.
노드의 왼쪽 링크(left link)와 오른쪽 링크(right link)가 각각 다른 노드의 오른쪽 링크와 왼쪽 링크를 연결짓고 있으며 헤드도 노드로 이루어져 있다.