[4] Linked_List, 연결리스트 (3)

👇🏻 오늘의 짤

모두의 망상짤

---

지금까지 연결리스트의 기본 형태에 대해 알아보았다. 

직전 포스트에서 이 말이 기억이 나는가?

 

"연결리스트는 이전을 가리킬 수 없고 다음만 가리킬 수 있다"

 

사실 이건 거짓말이다. 우리가 지금까지 배웠던 건 Single Linked List(단일 연결리스트)이다. 

베스킨라벤스에도 Single과 Double이 있듯이, Double Linked List(이중 연결리스트)가 존재한다.

그냥 넘어가면 서운할 것 같으니 한번 짚고 넘어가려고 한다.

 

단일 연결리스트에서는 노드를 찾을 때 node = head로부터 시작을 해 모든 노드를 탐색한 후 찾아야만 했다. 이에 반해 이중 연결리스트는 양방향으로 연결이 되어 있어 head, tail 두 노드에서부터 탐색이 가능하다. 양방향이 무슨 뜻인지는 아래 그림을 보면 알 수 있다.

 

 

단일 연결리스트에는 next만 있었다면 이중 연결리스트에는 이전(previous) 노드와 연결하는 prev도 있다. 

 

 

마찬가지로 head, tail이 존재하고 head의 prev 포인터는 NULL을, tail의 next 포인터는 NULL을 가리킨다.

이제 prev, next를 포함해 노드를 찍어내는 틀을 만들어보자.

 

코드 설명은 Linked List, 연결리스트 (1) 에 나와있는 것을 이해하면 충분히 이해할 수 있으니 생략하도록 하겠다. 혹시나 필요하면 댓글로 달아주도록!

 

# 노드 클래스
class Node:
    def __init__(self, data, prev = None, next = None):
        self.data = data
        self.prev = prev
        self.next = next

 

이중 연결리스트를 찍어내는 틀도 만들어 보자.

 

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

 

초기화 메소드 실행 시, head와 tail이 존재하지 않고 tail이 곧 head가 된다.

 

노드를 추가할 때, head 부터 tail을 찾을 필요 없이 tail의 다음 노드에 추가할 노드를 연결한 후 taild을 새 노드로 설정해 주면 된다. 

 

 def add(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            new_node = Node(data, prev = self.tail)
            self.tail.next = new_node
            self.tail = new_node

 

노드를 삽입(insert)할 때에는, 삽입할 새로운 노드의 바로 이전 노드를 아는 경우와 이후 노드를 아는 경우로 나누어 생각할 수 있다. 

 

# 노드 삽입 메소드 [삽입할 노드 직전 노드를 아는 경우]
    def insert_after(self, insert_data, insert_before_data):
        node = self.head

        while node.data != insert_before_data:
                node = node.next
                if node is None: 
                    return False
            
        insert_node_next = node.next
        insert_node = Node(insert_data, prev = node, next = insert_node_next)

        if node.next:
            node.next.prev = node
        else:
            self.tail = insert_node
        
        node.next = insert_node
    
    # 노드 삽입 메소드 [삽입할 노드 다음 노드를 아는 경우]
    def insert_before(self, insert_data, insert_after_data):
        node = self.tail

        while node.data != insert_after_data:
            node = node.prev
            if node is None: 
                return False

        insert_node_prev = node.prev
        insert_node = Node(insert_data, prev = insert_node_prev, next = node)

        if node.prev: 
            node.prev.next = insert_node
        else:
            self.head = insert_node
        
        node.prev = insert_node

 

이전 노드를 아는 경우는 head부터 탐색하면 되고 이후 노드를 아는 경우는 tail에서부터 탐색하면 된다. 이전 노드를 아는 경우(find_data 다음에 추가하는 경우)에는 이전 노드가 tail이었을 수도 있으므로 node.next로 확인을 한 후 예외처리를 해주면 되고 이후 노드를 아는 경우는 반대로 예외처리를 해주면 된다. 

 

노드 삭제하는 것은 이전과 동일하니 전체 코드와 출력 결과를 보여주는 것으로 넘어가도록 하겠다.

class Node:
    def __init__(self, data, prev = None, next = None):
        self.data = data
        self.prev = prev
        self.next = next
        
class Double_Linked_List:
    # 초기화 메소드
    def __init__(self):
        self.head = None
        self.tail = self.head

    # 노드 추가 메소드
    def add(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            new_node = Node(data, prev = self.tail)
            self.tail.next = new_node
            self.tail = new_node

        # 노드 삽입 메소드 [삽입할 노드 직전 노드를 아는 경우]
        def insert_after(self, insert_data, insert_before_data):
            node = self.head

            while node.data != insert_before_data:
                    node = node.next
                    if node is None: 
                        return False
                
            insert_node_next = node.next
            insert_node = Node(insert_data, prev = node, next = insert_node_next)

            if node.next:
                node.next.prev = node
            else:
                self.tail = insert_node
            
            node.next = insert_node
        
        # 노드 삽입 메소드 [삽입할 노드 다음 노드를 아는 경우]
        def insert_before(self, insert_data, insert_after_data):
            node = self.tail

            while node.data != insert_after_data:
                node = node.prev
                if node is None: 
                    return False

            insert_node_prev = node.prev
            insert_node = Node(insert_data, prev = insert_node_prev, next = node)

            if node.prev: 
                node.prev.next = insert_node
            else:
                self.head = insert_node
            
            node.prev = insert_node
    
    # 노드 삭제 메소드
    def delete(self, delete_data):
        if self.head.data == delete_data:
            temp = self.head
            self.head = self.head.next
            del temp
        else:    
            node = self.head
            while node.next:
                if node.next.data == delete_data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                else: 
                    node = node.next
            
    # 노드 출력 메소드
    def print_node(self):
        node = self.head
        while node:
            print(node.data, end=' ')
            node = node.next

DoubleLinkedList = Double_Linked_List()

for data in range(1,5):
    DoubleLinkedList.add(data * 10 + 8)

DoubleLinkedList.print_node()
# 출력 결과 : 18 28 38 48

DoubleLinkedList.insert_before(58, 38)
DoubleLinkedList.print_node()
# 출력 결과 : 18 28 58 38 48

DoubleLinkedList.insert_after(58, 38)
DoubleLinkedList.print_node()
# 출력 결과 : 18 28 58 38 58 48 

DoubleLinkedList.delete(58)
# 출력 결과 : 18 28 38 48
DoubleLinkedList.print_node()

 

드디어 연결리스트를 마무리하도록 하겠다.

 

✓ 연결리스트 특징
  장점 : 크기가 정해져 있지 않아 배열에 비해 데이터의 추가 및 삽입이 용이하고 메모리를 효율적으로 사용할 수 있다.
  단점 : 특정 위치의 데이터 검색에는 순회를 무조건 해야하기 때문에 탐색에 비효율적이다. 

✓ 배열과 연결리스트
  배열 👉🏻 탐색을 많이 할 때
  연결리스트 👉🏻 추가와 삭제를 많이할 때