Linked List는 데이터를 일렬로 연결하는 방법 중 하나로, 데이터의 순서가 메모리에 불연속적으로 위치하는 자료구조입니다. Linked List는 각각의 노드(Node)가 데이터와 포인터(Pointer)를 가지고 있는데 데이터는 저장하고자 하는 값을, 포인터는 다음 노드의 주소값을 가리킵니다.
기본적으로 Linked List는 head라는 포인터가 맨 앞 노드를 가리키며, 맨 마지막 노드의 포인터는 NULL 값을 가집니다. 새로운 노드를 추가하려면, 새로운 노드를 생성하고, 이전 노드의 포인터를 새로운 노드로 변경한 후, 새로운 노드의 포인터를 다음 노드로 변경해야 합니다.
Linked List는 배열(Array)과 비교했을 때, 삽입/삭제 연산이 용이하고, 메모리를 효율적으로 사용할 수 있으나, 특정 인덱스에 직접 접근하는 것이 불가능합니다. 따라서 Linked List는 데이터의 삽입/삭제가 많은 경우에 적합한 자료구조입니다.
물리적 비연속적, 논리적 연속적
각 node들은 데이터를 저장할 뿐 아니라, next node의 address 정보도 가지고 있기 때문에 논리적으로 연속성을 유지하면서 연결될 수 있습니다. Array의 경우 연속성을 유지하기 위해 메모리 상에서 순차적으로 데이터를 저장하는 방식을 사용하였지만, Linked list에는 메모리상에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유롭습니다. 다만 next node의 address도 추가적으로 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 커지게 됩니다.
class Node :
def __init__(self, value = 0, next = None):
self.value = value
seflf.next = next
class LinkedList(object):
def __init__(self):
self.head = None
def append(self,value):
new_node = Node(value)
if self.head is None:
self.head = new_node
# 맨 뒤의 node가 new_node를 가리켜야 한다.
else:
current = self.head
while (current.next):
current = current.next
current.next = new_node
p = LinkedList()
p.append(1)
p.append(2)
p.append(3)
p.append(4)