[자료구조] 연결 리스트(Linked List) 정리

1. 연결 리스트(Linked List)란?

연결 리스트(Linked list)는 데이터를 저장하는 선형 자료구조로써, 각 구성 요소가 노드(Node)로 구성되어 있으며 하나의 노드(Node)에는 데이터가 저장된 부분과 다음 노드를 가리키는 포인터(Pointer)로 구성되어 있습니다.

또한 연결 리스트의 시작지점을 가리키는 'Head'와 연결 리스트의 끝을 가리키는 Tail로 구성되어 있습니다.

2. 연결 리스트(Linked list)의  종류

연결 리스트의 종류는 크게 (1)Singly Linked List, (2)Doubly Linked List, (3)Circular Linked List가 있습니다. 이번 포스트에서는 Singly Linked List와 Doubly Linked List에 대해서만 다뤄보고자 합니다.

 

3. 단일 연결 리스트(Singly Linked List)

Singly Linked List(단일 연결 리스트)는 위 그림처럼 단방향으로 연결되어 있다는 점이 특징입니다. 즉, 하나의 노드를 보면 다음으로 연결된 노드가 무엇인지는 알 수 있지만, 어디서부터 연결되었는지에 대한 정보는 없습니다. 그렇기 때문에 시작 지점을 가리키는 Head Pointer가 꼭 필요합니다. 반대로 Tail은 노드가 가리키는게 아무것도 없는 경우가 Tail이기 때문에 단일 열결 리스트에서 Tail은 반드시 구현해야 하는 사항은 아닙니다.

 

Singly Linked List를 Python으로 구현하기 전에, 구현해야 하는 기능을 생각해보면 다음과 같습니다.

 

1. 노드를 구현하기 : 연결 리스트의 구성 요소인 노드(Node)를 구현해야 합니다. Node에는 데이터를 저장하는 부분과, 다음 노드를 가리키는 정보가 포함되어야 합니다.

2. 연결 리스트 구현하기 - 삽입 연산 구현하기 : 데이터가 새로 들어오는 경우, 새로운 데이터를 Head 부분에 추가하는 경우, Tail 부분에 추가하는 경우, 그리고 노드 중간에 추가하는 경우를 생각해서 구현해야 합니다.

3. 연결 리스트 구현하기 - 삭제 연산 구현하기 : Head를 삭제하는 경우, Tail을 삭제하는 경우, 그리고 중간에 있는 노드를 삭제하는 경우를 생각해서 구현해야 합니다.

4. 탐색 구현하기 : 원하는 자료가 연결 리스트에 있는지 탐색하는 기능을 추가합니다. 연결 리스트의 특성 상, Head를 이용해서 탐색해야 합니다.

 

3.1. Python을 이용한 Singly Linked List 구현 - Node 구현하기

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

 

Node의 구성은 데이터와 포인터로 구성되어 있으므로, 이 부분을 구현하였습니다.

3.2. Python을 이용한 Singly Linked List 구현

Singly Linked List의 삽입과 삭제 연산을 구현하기 전에, 몇가지 간단한 함수를 구현하였습니다.

- is_empty(self) : is_empty 함수는 Singly Linked List에 저장된 데이터가 있는지 없는지를 알려주는 함수입니다. 1개 이상의 원소가 있다면 True, 없다면 False를 return 합니다.

- search(self,data) : search 함수는 찾고자 하는 data를 입력받게 되면, 해당 data가 포함된 node가 있는지를 찾는 함수입니다. 만약, 찾고자 하는 data를 포함한 node가 있다면 True, 없다면 False를 return 합니다.

- display(self) : display 함수는 현재 Singly Linked List에 포함된 노드의 연결 관계를 보여줍니다. 연결 관계를 보기 좋게 표현하기 위해 시작 지점(start)과 끝 지점(end)을 표현하였으며, 연결 순서를 표현하기 위해 '->' 기호를 사용하였습니다.

예시는 다음과 같습니다.

An example of display function

class SinglyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None
        
    def is_empty(self):
        if self.head:
            return False
        else:
            return True
            
    def search(self,data):
        start = self.head
        while start:
            node_data = start.data
            if data == node_data:
                return start
            start = start.pointer
        else:
            return False
            
    def display(self):
        start = self.head
        print('start ->',end ='')
        while start:
            print(' ',start.data,' ',end = '->')
            start = start.pointer
        else:
            print(' end')

 

다음으로는 삽입 연산을 구현하였으며, 크게 3종류로 구성하였습니다.

 

- add_first(self) : add_first 함수는 Singly Linked List에서 Head가 가리키는 부분에 원소를 추가하는 함수입니다. 즉, 제일 첫 번째 부분에 원소를 추가합니다. 원소를 추가하면서 고려해야 하는 부분은 새롭게 삽입되는 노드의 pointer를 기존 Head가 가리키고 있는 노드로 설정해줘야 한다는 점 입니다. 또한 삽입 후에는 Head가 가리키는 노드는 새롭게 추가된 노드로 설정해야 합니다. 만약, Singly Linked List에 원소가 아무것도 없는 경우에는 Head와 Tail 모두를 새롭게 추가된 노드를 가리키게 합니다.

 

- add_last(self) : add_last 함수는 Singly Linked List에서 Tail이 가리키는 부분에 원소를 추가하는 함수입니다. 즉, 제일 마지막 부분에 원소를 추가합니다. 제일 마지막 부분에 원소를 추가하면서 고려해야 하는 부분은 기존에 Tail이 가리키고 있는 노드의 pointer를 새롭게 추가한 노드로 변경해 주어야 한다는 점 입니다. 또한 새롭게 추가된 노드는 제일 끝에 위치하게 되므로, Tail이 가리키는 노드는 새롭게 추가된 노드를 가리켜야 한다는 점 입니다. 추가로, 만약 tail이 없는 경우, Singly Linked List에는 데이터가 없다는 의미 이므로, add_first 함수를 실행합니다.

 

- add_data(self,node_data,new_data) : add_data 함수는 Singly Linked List에서 특정 데이터 다음에 추가시키는 함수입니다. 즉, 아래 그림처럼 1 -> 3 순서로 데이터가 입력된 Singly Linked List가 있을 때, 이 둘 사이에 2라는 데이터를 입력하는 경우 사용하는 함수입니다. 이런 경우, '어느 위치(node_data)에 어떤 데이터(new_data)를 입력하는지'에 대한 정보가 반드시 필요하므로, 해당 정보를 입력 받고 Head부터 순차적으로 입력 기준이 되는 노드를 탐색하면서, 해당 노드를 발견하게 되면 새롭게 입력한 노드를 pointer로 가리켜주어야 하며, 새롭게 입력한 노드에 대해서는 기존 노드가 가리키고 있던 노드를 가리켜 주어야 합니다.

 

위 내용을 Python code로 작성하면 다음과 같습니다.

class SinglyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None
        
    ...

    def add_first(self,data):
        node = Node(data)
        if self.head:
            node.pointer = self.head
        else:
            self.tail = node
        self.head = node

    def add_last(self,data):
        node = Node(data)
        if self.tail:
            self.tail.pointer = node
            self.tail = node
        else:
            self.add_first(data)

    def add_data(self,node_data,new_data):
        new_node = Node(new_data)
        start = self.head
        while start:
            target = start.data
            if target == node_data:
                new_node.pointer = start.pointer
                start.pointer = new_node
                break
            start = start.pointer
        else:
            return False

 

위 코드를 이용하여 삽입 연산을 수행하면 다음과 같습니다.

Example - INSERT

 

또한 0 다음으로 -1 을 추가하는 add_data 함수를 실행해보았습니다.

 

An example of add_data function

 

마지막으로, 삭제 연산을 구현해야 합니다. 삭제 연산은 삽입 연산과 마찬가지로 3종류로 구현하였습니다.

- remove_first(self) : remove_first 함수는 Head 포인터가 가리키는 첫 번째 노드를 삭제하는 함수입니다. 삭제 시 고려 해야 하는 부분은 Head 포인터가 가리키는 부분이 삭제되므로, Head 포인터가 가리키는 노드를 두 번째 노드로 바꿔주는 작업을 수행해야 합니다. 또한, Singly Linked List 안에 노드가 단 1개인 경우, Head와 Tail이 가리켜야 하는 노드가 없으므로 None으로 설정해야 하는 작업을 추가해야 합니다.

- remove_last(self) : remove_last 함수는 Tail 포인터가 가리키는 마지막 노드를 삭제하는 함수입니다. add_last(self) 함수와는 다르게, 마지막 노드에는 이전 노드가 어떤 노드인지에 대한 정보가 없기 때문에 Head 포인터를 이용해서 바로 이전의 노드가 무엇인지 찾아야 합니다. 따라서 반복문을 이용하여 마지막 바로 이전의 노드를 탐색하고, 해당 노드의 포인터를 None으로 설정합니다. 마지막으로 Tail의 포인터를 해당 노드로 바꿔줘야 합니다. 이전 remove_first와 마찬가지로, Singly Linked List에 노드가 단 1개인 경우는 remove_first 함수에서 했던 작업과 동일한 작업을 수행합니다.

- remove_data(self,data) : remove_data 함수는 Singly Linked List에 포함되어 있는 노드를 삭제하는 함수입니다. Head 포인터를 이용하여 입력받은 데이터와 같은 데이터를 찾게 되면, 해당 노드가 가리키고 있던 포인터는 이전 노드의 포인터로 바꿔주는 작업을 수행합니다. 만약 입력받은 데이터가 Singly Linked List에 없다면, 순회만 하고 아무 작업을 하지 않습니다.

 

class SinglyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None
        
    ...
        
    def remove_first(self):
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return
        old_node = self.head
        self.head = old_node.pointer

    def remove_last(self):
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return
        start = self.head
        while start.pointer != self.tail:
            start = start.pointer
        start.pointer = None
        self.tail = start

    def remove_data(self,data):
        start = self.head
        if self.head.data == data:
            remove_first()
            return
        elif self.tail.data == data:
            remove_last()
        else:
            while start.pointer:
                next_data = start.pointer.data
                if next_data == data:
                    start.pointer = start.pointer.pointer
                    break
                start = start.pointer
            else:
                return

 

위 코드를 이용하여 이전 상태에서 삭제를 진행해보겠습니다.

start ->  1  ->  2  ->  3  ->  0  ->  -1  ->  10  ->  20  ->  30  -> end

 

위 상태에서 remove_first, remove_last, remove_data(0)를 실행하면 다음과 같습니다.

 

정상적으로 작동이 됨을 확인 할 수 있습니다. 마지막으로, 원소가 한개도 없을 때 까지 remove_data를 실행해보면 다음과 같습니다.

 

마지막으로 Singly Linked List에 노드가 있는지 판단하는 is_empty 함수를 실행시켜 보았을 때 True를 출력하는 모습까지 확인 할 수 있습니다.

Singly Linked List의 구현을 마치면서, 구현한 전체 코드는 다음과 같습니다.

class SinglyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None
        
    def is_empty(self):
        if self.head:
            return False
        else:
            return True
            
    def search(self,data):
        start = self.head
        while start:
            node_data = start.data
            if data == node_data:
                return start
            start = start.pointer
        else:
            return False

    def add_first(self,data):
        node = Node(data)
        if self.head:
            node.pointer = self.head
        else:
            self.tail = node
        self.head = node

    def add_last(self,data):
        node = Node(data)
        if self.tail:
            self.tail.pointer = node
            self.tail = node
        else:
            self.add_first(data)

    def add_data(self,node_data,new_data):
        new_node = Node(new_data)
        start = self.head
        while start:
            target = start.data
            if target == node_data:
                new_node.pointer = start.pointer
                start.pointer = new_node
                break
            start = start.pointer
        else:
            return False

    def remove_first(self):
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return
        old_node = self.head
        self.head = old_node.pointer

    def remove_last(self):
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return
        start = self.head
        while start.pointer != self.tail:
            start = start.pointer
        start.pointer = None
        self.tail = start

    def remove_data(self,data):
        start = self.head
        if self.head.data == data:
            remove_first()
            return
        elif self.tail.data == data:
            remove_last()
        else:
            while start.pointer:
                next_data = start.pointer.data
                if next_data == data:
                    start.pointer = start.pointer.pointer
                    break
                start = start.pointer
            else:
                return
                
    def display(self):
        start = self.head
        print('start ->',end ='')
        while start:
            print(' ',start.data,' ',end = '->')
            start = start.pointer
        else:
            print(' end')

 

4. 이중 연결 리스트(Doubly Linked List)

이중 연결 리스트(Doubly Linked List)는 단일 연결 리스트(Singly Linked List)와 거의 비슷하지만, 이전 노드에 대한 정보가 담겨있는 포인터가 추가된다는 차이점이 있습니다. 그림으로 살펴보면 다음과 같습니다.

Doubly Linked List

그림에서 보면, 하나의 노드에서 포인터가 하나 추가되었으며, 추가된 포인터는 이전 노드를 가리키고 있습니다. 따라서 구현 시, Node 클래스에 포인터를 하나 추가시켜주어야 합니다.

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

 

다음으로 Doubly Linked List의 구현을 살펴보겠습니다. Singly Linked List의 코드를 거의 대부분 재사용하므로 자세한 설명은 생략하며, 삽입 및 삭제에서 바뀌는 부분만 살펴보겠습니다.

4.1 Python을 이용한 Doubly Linked List 구현

삽입 부분에서 바뀌는 부분은 prev_pointer에 대한 구현을 추가로 진행해야 합니다. add_first 와 add_last에서 추가된 노드에 대한 prev_pointer 정보를 추가하고, 기존에 있던 prev_node와 next_node에 대한 정보도 업데이트 해 줍니다. 또한, add_data 함수는 총 4개의 포인터(새롭게 추가된 노드의 포인터 2개 + 기존에 연결되어 있던 포인터 2개)에 대해 연결 관계를 업데이트 해 주어야 합니다.

class DoublyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None
        
    ...

    def add_first(self,data):
        node = Node(data)
        if self.head:
            node.next_pointer = self.head
            self.head.prev_pointer = node
        else:
            self.tail = node
        self.head = node

    def add_last(self,data):
        node = Node(data)
        if self.tail:
            node.prev_pointer = self.tail
            self.tail.next_pointer = node
            self.tail = node
        else:
            self.add_first(data)

    def add_data(self,node_data,new_data):
        new_node = Node(new_data)
        start = self.head
        while start:
            target = start.data
            if target == node_data:
                new_node.next_pointer = start.next_pointer
                new_node.prev_pointer = start
                start.next_pointer.prev_pointer = new_node
                start.next_pointer = new_node
                break
            start = start.pointer
        else:
            return False

 

위 코드를 이용하여 이전 Singly Linked List와 같은 예시로 실행해 보았습니다. 실행에 앞서, display함수도 살짝 변경하였습니다. 

...

    def display(self):
        start = self.head
        print('start ->',end ='')
        while start:
            print(' ',start.data,' ',end = '->')
            start = start.next_pointer
        else:
            print(' end')

        print('end <-',end ='')
        end = self.tail
        while end:
            print(' ',end.data,' ',end = '<-')
            end = end.prev_pointer
        else:
            print(' start')

 

각 포인터들의 연결관계가 잘 되었는지 확인하기 위해, Head 포인터부터 시작하는 부분에 더해 Tail 포인터부터 시작하는 부분을 추가하여 출력하도록 했습니다.

Example - INSERTION

 

다음으로는 삭제 연산 부분입니다. 삭제 연산도 삽입 연산과 마찬가지로 prev_pointer의 정보를 업데이트하는 부분을 추가하였습니다.

class DoublyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None
        
    ...
    
    def remove_first(self):
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return
        old_node = self.head
        self.head = old_node.next_pointer
        self.head.prev_pointer = None

    def remove_last(self):
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return
        old_node = self.tail
        self.tail = old_node.prev_pointer
        self.tail.next_pointer = None
        

    def remove_data(self,data):
        start = self.head
        if self.head.data == data:
            remove_first()
            return
        elif self.tail.data == data:
            remove_last()
        else:
            while start.next_pointer:
                node_data = start.data
                if node_data == data:
                    start.prev_pointer.next_pointer = start.next_pointer
                    start.next_pointer.prev_pointer = start.prev_pointer
                    break
                start = start.next_pointer
            else:
                return

 

위 코드를 이용하여 이전에 추가한 노드를 삭제해보겠습니다.

 

마지막으로 노드가 1개도 없을 때 까지 삭제도 해보았습니다.

 

Singly Linked List와 마찬가지로 정상적으로 삽입 및 삭제가 작동함을 확인할 수 있습니다.

마지막으로, Doubly Linked List를 구현한 전체 코드 입니다.

class DoublyLinkedList:

    def __init__(self):
        self.head = None
        self.tail = None
        
    def is_empty(self):
        if self.head:
            return False
        else:
            return True
            
    def search(self,data):
        start = self.head
        while start:
            node_data = start.data
            if data == node_data:
                return start
            start = start.next_pointer
        else:
            return False
            
    def display(self):
        start = self.head
        print('start ->',end ='')
        while start:
            print(' ',start.data,' ',end = '->')
            start = start.next_pointer
        else:
            print(' end')

        print('end <-',end ='')
        end = self.tail
        while end:
            print(' ',end.data,' ',end = '<-')
            end = end.prev_pointer
        else:
            print(' start')

    def add_first(self,data):
        node = Node(data)
        if self.head:
            node.next_pointer = self.head
            self.head.prev_pointer = node
        else:
            self.tail = node
        self.head = node

    def add_last(self,data):
        node = Node(data)
        if self.tail:
            node.prev_pointer = self.tail
            self.tail.next_pointer = node
            self.tail = node
        else:
            self.add_first(data)

    def add_data(self,node_data,new_data):
        new_node = Node(new_data)
        start = self.head
        while start:
            target = start.data
            if target == node_data:
                new_node.next_pointer = start.next_pointer
                new_node.prev_pointer = start
                start.next_pointer.prev_pointer = new_node
                start.next_pointer = new_node
                break
            start = start.pointer
        else:
            return False

    def remove_first(self):
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return
        old_node = self.head
        self.head = old_node.next_pointer
        self.head.prev_pointer = None

    def remove_last(self):
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return
        old_node = self.tail
        self.tail = old_node.prev_pointer
        self.tail.next_pointer = None
        

    def remove_data(self,data):
        start = self.head
        if self.head.data == data:
            remove_first()
            return
        elif self.tail.data == data:
            remove_last()
        else:
            while start.next_pointer:
                node_data = start.data
                if node_data == data:
                    start.prev_pointer.next_pointer = start.next_pointer
                    start.next_pointer.prev_pointer = start.prev_pointer
                    break
                start = start.next_pointer
            else:
                return