[자료구조] 연결리스트

연결 리스트

연결리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조다.

각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.

맨 첫번째 노드를 Head라고 한다.

각 노드에 알파벳으로 써놓은 부분이 데이터 영역(=노드의 값)이며 동그라미 부분이 포인터 영역으로 다음 노드를 가리키는 역할을 한다.

특징

• 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.
• 탐색은 O(n)이 소요된다.
• 요소를 추가하거나 제거할 때는 O(1)이 소요된다.
• Singly Linked List, Doubly Linked List, Circular Linked List가 존재한다.

 

연결 리스트에서의 요소 삭제

1. 삭제할 요소를 선택

2. 삭제할 요소의 이전 요소가 가리키는 포인터를 삭제할 요소의 다음 요소에 연결한다

3. 삭제할 요소를 완전히 삭제. 배열과는 다르게 이 로직을 수행하는데 상수시간(=O(1))소요

 

연결 리스스트에서의 요소 추가

1. 추가할 요소의 포인터가 끼워넣을 부분의 다음 요소를 가리키도록 한다.

2. 끼워넣을 부분의 이전 요소의 포인터를 추가할 요소를 가리키도록 한다. 삭제 로직과 마찬가지로 추가 로직도 상수시간(=O(n))소요

 

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

가장 단순한 연결리스트. Head(첫번째 요소)에서 Tail(마지막 요소)까지 단방향으로 이어지는 연결리스트다.

헤드포인터: 헤드를 가리킴. 출발점.

Tail의 포인터 영역은 Null로 되어있음.

Singly Linked List 요소 찾기 (탐색)

ex) 위 연결 리스트에서 '4'를 찾는다면?

  1. 헤드 포인터에서 다음 요소인 Head를 찾는다.

  2. Head에 가서 데이터가 4인지 확인하고 아니면 다음 요소로 넘어간다.

  3. 다음 요소의 데이터도 4가 아니므로 그 다음 요소로 넘어간다.

  4. 이번 요소는 4이므로 탐색을 종료한다.

 >> O(n)시간 소요

 

Singly Linked List 요소 추가

ex) 위 연결리스트에서 데이터 값이 2인 요소와 4인 요소 사이에 데이터 값이 3인 요소를 추가한다면?

  1. 추가할 요소의 포인터 영역이 4인 요소를 가리키게 만든다.

  2. 2인 요소의 포인터가 추가할 요소를 가리키게 만든다.

 >> O(1)시간 소요 

단, O(1)이 소요되는 것은 단순히 '추가'하는 것만 생각했을 때의 소요시간. 즉, 끼워넣을 위치를 찾고 추가한다면 탐색이 더해져서 O(n)이 늘어남. 따라서 연결 리스트를 사용할 때는 추가를 위한 탐색을 하지 않도록 주의해야 한다.

 

Singly Linked List 요소 삭제

ex) 위 연결리스트에서 데이터 값이 2인 요소를 삭제한다면?

  1. 삭제할 요소의 이전 요소가 삭제할 요소의 다음 요소를 가리키도록 수정

  2. 메모리상에서 요소를 완전하게 삭제

>> O(1)시간 소요

 

 

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

포인터가 두개 존재하여 다음과 이전을 가르킬 수 있어 양방향으로 이어지는 구조인 연결 리스트다.

Head는 첫번째 요소이므로 이전 노드를 가리키는 포인터는 Null이고, Tail은 마지막 요소이므로 다음 노드를 가리키는 포인터가 Null이다.

Doubly Linked List 요소 추가

ex) 위 연결리스트에서 데이터 값이 2인 요소와 4인 요소 사이에 데이터 값이 3인 요소를 추가한다면?

  1. 추가할 요소의 다음 요소를 가리키는 포인터가 4인 요소를 가리키게 만든다.

  2. 추가할 요소의 이전 요소(2)의 다음 포인터가 추가할 요소를 가리키도록 한다.

  3. 추가할 요소의 다음 요소(4)의 이전 포인터가 추가할 요소를 가리키도록 한다.

  4. 추가할 요소의 이전 포인터가 이전 요소(2)를 가리키도록 한다.

>> 단일 연결 리스트와 마찬가지로 요소 추가 로직에 O(1)시간이 소요된다.

 

Doubly Linked List 요소 삭제

ex) 위 연결리스트에서 데이터 값이 2인 요소를 삭제한다면?

  1. 삭제할 요소의 이전 요소(1)의 다음 포인터가 삭제할 요소의 다음 요소(4)를 가리키도록 한다.

  2. 삭제할 요소의 다음 요소(4)가 이전 노드로 삭제할 요소의 이전 요소(2)를 가리키도록 한다.

  3. 삭제할 요소를 메모리상에서 삭제

 >> 마찬가지로 O(1)시간 소요.

 

 

Circular Linked List (환형 연결 리스트)

Tail의 포인터가 Head를 가리키도록 한 연결 리스트. 메모리를 아껴쓸 수 있다. 원형 큐 등을 만들 때도 사용된다.

중간에서 탐색을 시작하더라도, 한 바퀴를 다 돌 수 있다.

 

 

파이썬으로 구현한 연결리스트

class Node:
    def __init__(self, value):  # 최초 생성시에는 다음 노드에 대한 정보가 없음. 아직 연결을 안했으므로
        self.value = value
        self.next = None
        
 
class SinglyLinkedList:  # 노드와 노드를 연결해주는 역할
    def __init__(self):
    	self.head = None
        self.tail = None
    
    def find(self, value):
    	curr_node = self.head
        while curr_node.value != value:
        	curr_node = curr_node.next
        return curr_node
    
    def append(self, new_value):  # 끝부분에 추가하는 append 로직
    	new_node = Node(new_value)
        if self.head is None:  # head가 없으면 아직 아무것도 없다는 뜻
        	self.head = new_node
            self.tail = new_node
        else:  # head가 이미 있으면 추가되는 node는 마지막 노드가 된다.
        	self.tail.next = new_node
            self.tail = new_node
    
    def insert(self, node: Node, new_value):  # 중간에 추가하는 insert 로직. node는 추가할 노드의 이전 노드를 말함
    	new_node = Node(new_value)
        new_node.next = node.next  # 추가할 노드의 포인터를 이전 노드의 포인터가 가르키던 다음 노드로 설정
        node.next = new_node  # 이전 노드의 포인터는 추가할 노드를 가리키도록 설정
    
    def remove(self, value):  # 값을 찾고, 삭제하는 로직. 따라서 O(n)시간(==선형시간) 소요
    	prev_node = self.head
        while prev_node.next.value != value:  # 이전 노드가 가르키는 노드의 값이 내가 삭제할 노드면 종료
        	prev_node = prev_node.next  # 다음 노드로 넘어감
        
        if prev_node.next is not None:  # 삭제할 노드가 Tail이 아니라면
        	prev_node.next = prev_node.next.next  # 삭제할 노드의 이전 노드가 가르키는 노드를 삭제할 노드의 다음 노드로 설정
            
    def display(self):
    	curr_node = self.head  # 첫번째 노드부터 탐색
        display_string = "["
        while curr_node is not None:
        	display_string += f"{curr_node.value}, "
            curr_node = curr_node.next
        
        display_string = display_string[0: len(display_string) - 2]  # 여기서 2를 뺀 이유는 맨 앞 '[' 와 맨 마지막 요소가 None이 들어가므로 이것까지 제외한 것
        display_string += "]"
        
        print(display_string)
        


linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(5)
linked_list.display()
 >> [1, 2, 3, 5]
 
print(linked_list.find(3))
 >> <__main__.Node object at 0x10538cd60>
 
linked_list.remove(3)
linked_list.display()
 >> [1, 2, 5]
 
linked_list.insert(linked_list.find(2), 10)
linked_list.display()
 >> [1, 2, 10, 5]