링크드 리스트는 파이썬의 리스트처럼 선형 자료 구조로서, 데이터를 순서대로 저장할 수 있고 계속해서 요소를 추가할 수 있다. 이는 데이터와 다음 노드에 대한 레퍼런스를 가진 노드를 사용해 구현하는데, 노드들은 메모리 공간 여기저기 흩어진 상태로 저장되지만 각 노드에는 다음 노드나 이전 노드에 대한 레퍼런스를 가지고 있어서 선형적으로 다음 노드를 탐색할 수 있는 특징이 있다.
싱글리 링크드 리스트 (Singly Linked List)
노드들이 다음 노드에 대한 레퍼런스만을 가진 링크드 리스트를 싱글리 링크드 리스트라고 한다. 다음 노드에 대한 레퍼런스를 가지고 있기 때문에 한 방향으로 탐색할 수 있는 특징이 있다.
노드(Node)
class Node:
"""노드 클래스"""
def __init__(self, data) -> None:
self.data = data # 노드가 저장하는 데이터
self.next = None # 다음 노드에 대한 레퍼런스
def __str__(self) -> str:
return str(self.data)
# 노드 인스턴스
node1 = Node(3)
node2 = Node(7)
node3 = Node(12)
# 노드 사이의 레퍼런스 설정
node1.next = node2
node2.next = node3
# 결과 출력
print(node1)
print(node1.next)
print(node1.next.next)3
7
12
class Node:
"""노드 클래스"""
def __init__(self, data) -> None:
self.data = data # 노드가 저장하는 데이터
self.next = None # 다음 노드에 대한 레퍼런스
def __str__(self) -> str:
return str(self.data)
먼저 정보를 담을 노드 클래스를 만들어 준다. 싱글리 링크드 리스트에서 노드는 데이터와 다음 노드에 대한 레퍼런스를 가지므로 self.data와 self.next로 각 노드 인스턴스의 속성을 부여한다. __str__ 매직 메소드는 노드 인스턴스를 print()로 출력했을 때 인스턴스가 가진 데이터를 출력하기 위해서 만들어 주었다.
# 노드 인스턴스
node1 = Node(3)
node2 = Node(7)
node3 = Node(12)
이제 각각 3, 7, 12 데이터를 가진 node1, node2, node3 인스턴스를 만들어 준다. 아직까지 각 노드들은 서로에 대한 레퍼런스 없이 메모리 여기저기 흩어져 있는 상태다.
# 노드 사이의 레퍼런스 설정
node1.next = node2
node2.next = node3
이제 node1의 다음 노드는 node2로, node2의 다음 노드는 node3로 서로 간의 레퍼런스를 설정해주면 이 노드들 간에 유의미한 관계가 생긴다.
# 결과 출력
print(node1)
print(node1.next)
print(node1.next.next)
예를 들어 이렇게 node1, node1의 다음 노드, node1의 다음 노드의 다음 노드를 출력할 수 있게 됐다.
싱글리 링크드 리스트 (Singly Linked List)
추가 연산 (append)
위에서 노드 클래스를 만들고 서로 간의 레퍼런스를 코드로 한 줄 한 줄 추가해 줬지만 너무 불편하다. 어차피 다음 추가될 노드는 node3가 가리키도록 하면 될테니 자동적으로 이러한 관계가 설정됐으면 좋겠다.
class Node:
"""노드 클래스"""
def __init__(self, data) -> None:
self.data = data # 노드가 저장하는 데이터
self.next = None # 다음 노드에 대한 레퍼런스
def __str__(self) -> str:
return str(self.data)
class SinglyLinkedList:
"""싱글리 링크드 리스트"""
def __init__(self) -> None:
self.head = None
self.tail = None
def append(self, data):
"""노드 추가"""
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
def print_all_nodes(self):
"""모든 노드 출력"""
iterator = self.head
while iterator is not None:
print(iterator.data)
iterator = iterator.next
# 링크드 리스트 인스턴스 생성
singly_linked_list = SinglyLinkedList()
# 노드 추가
singly_linked_list.append(3)
singly_linked_list.append(7)
singly_linked_list.append(12)
singly_linked_list.append(15)
singly_linked_list.append(32)
# 모든 노드 출력
singly_linked_list.print_all_nodes()3
7
12
15
32
def __init__(self) -> None:
self.head = None
self.tail = None링크드 리스트는 기본적으로 노드가 여러개 연결되어 있을 때 가장 앞과 끝의 정보를 가진다. 초기값으로는 아직 노드가 없기 때문에 둘다 None으로 만들어준다.
def append(self, data):
"""노드 추가"""
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
append메소드는 노드에 들어갈 data를 파라미터로 받는다. 이 data를 이용해 new_node라는 이름의 새로운 노드를 만들어 준다. 이제 두 가지 경우를 생각해야 한다. 링크드 리스트 안에 노드가 없을 경우, 즉 head가 아무런 값도 가리키지 않을 경우 head와 tail을 둘 다 새로운 노드를 가리키도록 한다.
이미 노드가 있을 경우, tail이 가리키고 있는 노드가 new_node를 가리키도록 하고 tail이 new_node를 가리키도록 하면 자연스럽게 링크드 리스트와 새로운 노드가 연결된다.
def print_all_nodes(self):
"""모든 노드 출력"""
iterator = self.head
while iterator is not None:
print(iterator.data, end=" ")
iterator = iterator.next
print("")
다음으로 링크드 리스트의 모든 노드를 출력하기 위해 알고 있는 정보인 head가 가리키고 있는 노드를 iterator 변수의 첫번째 값으로 설정한다. 이제 iterator값을 하나씩 출력하고 해당 노드가 가리키고 있는 레퍼런스를 통해 다음 노드를 연속적으로 출력하면 된다. tail이 가리키고 있는 노드의 next 속성은 None이기 때문에 마지막 노드를 출력하고 난 뒤 while문을 빠져나가게 된다.
접근 연산 (indexing)
class SinglyLinkedList:
"""싱글리 링크드 리스트"""
def indexing(self, index):
"""인덱스로 링크드 리스트 접근"""
iterator = self.head
for _ in range(index):
iterator = iterator.next
return iterator
리스트는 array[2], array[6] 등과 같이 인덱스를 이용해 바로 접근할 수 있는 반면에 링크드 리스트는 원하는 인덱스의 값에 바로 접근할 수 없다. 노드들은 연속적으로 저장된 데이터가 아니라 메모리 여기저기 흩어져 있는 값이기 때문이다. 해당 인덱스에 접근하기 위해서는 우리가 알고 있는 정보인 링크드 리스트의 head부터 하나씩 찾아나가야 한다.
따라서 링크드 리스트에서 접근 연산의 시간복잡도는 O(n)이다.
탐색 연산 (search)
class SinglyLinkedList:
"""싱글리 링크드 리스트"""
def search(self, data):
"""링크드 리스트 내에서 data와 매치되는 노드 리턴"""
iterator = self.head
while iterator is not None:
if iterator.data == data:
return iterator
iterator = iterator.next
return None
링크드 리스트 안에 해당하는 데이터가 있으면 해당 노드를 리턴하고, 없다면 None을 리턴하는 탐색 연산이다. 이 경우에도 가장 마지막까지 탐색했는데도 없을 경우가 최악의 경우이므로 O(n)의 시간복잡도를 가진다.
삽입 연산 (insert_after)
class SinglyLinkedList:
"""싱글리 링크드 리스트"""
def insert_after(self, previous_node, data):
"""링크드 리스트 내의 해당 노드 뒤에 새로운 노드 삽입"""
new_node = Node(data)
if previous_node == self.tail:
# 기준 노드가 마지막 노드일 경우
self.tail.next = new_node
self.tail = new_node
else:
new_node.next = previous_node.next
previous_node.next = new_node
# 링크드 리스트 인스턴스 생성
singly_linked_list = SinglyLinkedList()
# 노드 추가
singly_linked_list.append(3)
singly_linked_list.append(7)
singly_linked_list.append(12)
singly_linked_list.append(15)
singly_linked_list.append(32)
# 인덱스를 통해 접근
singly_linked_list.print_all_nodes()
test_node = singly_linked_list.indexing(2)
singly_linked_list.insert_after(test_node, 100)
singly_linked_list.print_all_nodes()
임의의 노드 다음에 새로운 노드를 삽입하는 연산이다.
임의의 노드가 마지막 노드일 경우와 중간에 있을 경우를 나눠서 생각해야 한다. 마지막 노드일 경우 임의의 노드의 next 속성이 new_node를 가리키도록 하고, new_node가 링크드 리스트의 새로운 tail이 되면 된다. 중간에 있을 경우 순서가 조금 중요한데 먼저 new_node의 next가 가리키는 노드가 원래 previous_node가 가리키던 next를 가리키면 된다. 그리고 previous_node의 next는 new_node를 가리키면 링크드 리스트 사이에 새로운 노드가 쏙 들어간다.
삽입 연산 자체는 그냥 노드 간의 관계를 끊고 연결하기 때문에 O(1)이지만, 삽입할 노드를 탐색하거나 접근하는 데 O(n)의 시간이 걸리므로 사실상 O(n)의 시간 복잡도를 가진다.
맨앞 삽입 연산 (prepend)
append나 insert_after 메소드를 사용하면 링크드 리스트의 맨 앞에는 삽입이 불가능하다. 이를 해결하기 위해 prepend 메소드를 만들어보자.
class SinglyLinkedList:
"""싱글리 링크드 리스트"""
def prepend(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head = new_node
기존과 같이 data를 가진 노드를 새로 만든다. 만약 노드가 없다면 head와 tail가 new_node를 가리키게 해주고, 노드가 있다면 new_node.next가 head를 가리키고 있던 노드를 가리키게 한 뒤, head가 new_node를 가리키면 new_node가 맨앞에 위치하게 된다.
head를 통해 맨 앞 노드에 바로 접근해 삽입할 수 있으므로 O(1)의 시간 복잡도를 가진다.
삭제 연산 (delete_after)
싱글리 링크드 리스트에서는 해당 노드에 대한 삭제가 아니라 그 다음 노드에 대한 삭제만 가능하다. 노드가 담고 있는 정보를 생각해보면 임의의 B 노드는 다음 노드인 C 노드에 대한 레퍼런스만 가지고 있기 때문에 B 노드 앞의 ? 노드와 C노드를 직접 연결시켜 B노드를 삭제해주려고 해도 ? 노드에 대한 정보를 알 수 없다.
class SinglyLinkedList:
"""싱글리 링크드 리스트"""
def delete_after(self, previous_node):
data = previous_node.next.data
if previous_node.next is self.tail:
previous_node.next = None
self.tail = previous_node
else:
previous_node.next = previous_node.next.next
return data
이 경우에도 두 가지 경우를 생각해야 한다. previous_node.next가 tail인 경우와 아닌 경우. tail인 경우 previous_node가 tail이 되는 것이므로 next가 아무것도 가리키지 않도록 한 뒤, tail을 previous_node로 지정해주면 된다. tail이 아닌 경우에는 그냥 previous_node의 next가 다음 다음 노드를 가리키도록 하면 자연스럽게 빠진다.
삽입 연산과 마찬가지로 삭제할 노드에 탐색하거나 접근해 삭제 연산을 해야 하므로 사실상 O(n)의 시간 복잡도를 가진다.
맨앞 삭제 연산 (pop_left)
prepend 메소드와 마찬가지로, 싱글리 링크드 리스트에서는 어떤 노드 다음의 노드를 삽입하거나 삭제하기 때문에 맨 앞 노드를 다룰 수 없다. prepend와 반대로 맨 앞의 노드를 삭제하는 연산을 생각해보자.
class SinglyLinkedList:
"""싱글리 링크드 리스트"""
def pop_left(self):
data = self.head.data
if self.head.next is None:
self.head = None
self.tail = None
else:
self.head = self.head.next
return data
만약 맨 앞 노드인 head의 next가 없다면 유일한 노드이므로 head와 tail을 None으로 만들어 주면 자연스럽게 삭제되고, head의 next가 있다면 head의 다음 노드를 head로 지정해주면 된다.
head 정보를 이용해 노드에 접근해 삭제하면 되므로 O(1)의 시간 복잡도를 가진다.
'프로그래밍 > Computer Science' 카테고리의 다른 글
| [Data Structure] Linear - (3) Linked List - Circular Linked List (0) | 2023.09.11 |
|---|---|
| [Data Structure] Linear - (2) Linked List - Doubly Linked List (0) | 2023.09.11 |
| [Data Structure] Linear - (1) Array (0) | 2023.08.16 |
| [Overview] 03. Operating Systems - (2) Kernel and Virtual Machine (0) | 2023.08.02 |
| [Overview] 03. Operating Systems - (1) The History of Operating Systems (0) | 2023.07.31 |