LinkedList는 데이터를 순서대로 저장하는 자료구조입니다. 각 데이터는 노드(Node)라는 객체로 구성되어 있으며, 각 노드는 데이터와 다음 노드를 가리키는 포인터(Pointer)로 이루어져 있습니다.
LinkedList는 배열과 달리 새로운 데이터를 추가하거나 삭제할 때 전체 데이터를 이동시키지 않아도 되므로, 데이터의 삽입과 삭제가 빠르고 유연합니다. 하지만 배열과 달리 인덱스로 접근할 수 없기 때문에 특정 위치의 데이터에 접근하려면 처음부터 순서대로 검색해야 합니다.
LinkedList는 단방향(Forward LinkedList)과 양방향(Doubly LinkedList)으로 나뉘며, 양방향 LinkedList는 각 노드가 이전 노드를 가리키는 포인터를 추가로 가지고 있어서 이전 노드에서도 다음 노드로 바로 접근할 수 있습니다.
LinkedList는 자료구조를 학습하는 데 중요한 개념 중 하나이며, 실제로도 많이 사용됩니다.
파이썬을 이용해 LinkedList를 구현하기
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def add_node(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = new_node
def print_list(self):
current_node = self.head
while current_node is not None:
print(current_node.data)
current_node = current_node.next링크드 리스트의 장점은 데이터를 삽입하거나 삭제할 때 빠르다는 것입니다. 이는 배열과 다릅니다. 배열은 전체 데이터를 이동시켜야 하지만, 링크드 리스트는 그렇지 않습니다.
또한, 링크드 리스트는 데이터 크기를 동적으로 변경할 수 있습니다.
링크드 리스트의 단점은 배열과 다르게 특정 위치의 데이터에 바로 접근할 수 없습니다. 데이터를 찾을 때는 처음부터 순서대로 찾아야 합니다. 링크드 리스트는 배열보다 메모리를 더 사용합니다. 링크드 리스트의 각 노드는 다음 노드를 가리키는 포인터가 추가로 필요하기 때문입니다.
따라서 링크드 리스트는 데이터의 추가와 삭제가 빈번하게 일어나는 경우에 유용합니다. 예를 들어, 큐(Queue)나 스택(Stack)과 같은 자료구조를 구현할 때 링크드 리스트가 사용됩니다.
