لیست های پیوندی (Linked Lists)
«لیست پیوندی (Linked List)» ساختار داده ای است که «گره ها (Nodes)» با اشاره گر به هم وصل می شوند. هر گره یک داده و یک لینک به گره بعدی دارد.
لیست پیوندی چیست؟
لیست پیوندی از گره ها ساخته می شود. هر گره داده دارد و لینک بعدی. برخلاف «آرایه (Array)»، گره ها کنار هم در حافظه نیستند.
مقایسه لیست پیوندی و آرایه
آرایه اندازه ثابت دارد و دسترسی تصادفی ممکن است. اما درج یا حذف وسط آرایه زمان بر است. لیست پیوندی اندازه پویا دارد و حذف/درج بدون جابه جایی انجام می شود.
نکته: جزئیات ذخیره سازی حافظه در منبع W3Schools توضیح داده شده است.
انواع لیست های پیوندی
سه نوع اصلی داریم: «تک پیوندی»، «دودویی»، و «حلقوی». تک پیوندی ساده تر است. دودویی رفت وبرگشت را آسان می کند. حلقوی برای پیمایش بی پایان مناسب است.
پیمایش (Traversal) در لیست پیوندی
پیمایش یعنی از «هد (Head)» شروع کنیم و از لینک ها عبور کنیم تا به انتها برسیم.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverse_and_print(head):
current_node = head
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next
print("null")
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
traverse_and_print(node1)
کمترین مقدار را پیدا کن
با پیمایش، کمترین مقدار را به روزرسانی کن. این شبیه آرایه است؛ فقط باید از لینک ها عبور کنیم.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def find_lowest_value(head):
min_value = head.data
current_node = head.next
while current_node:
if current_node.data < min_value:
min_value = current_node.data
current_node = current_node.next
return min_value
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
print("Lowest:", find_lowest_value(node1))
حذف یک گره
قبل از حذف، لینک قبلی را به بعدی وصل کن. این کار زنجیر را نمی شکند.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverse_and_print(head):
current_node = head
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next
print("null")
def delete_specific_node(head, node_to_delete):
if head == node_to_delete:
return head.next
current_node = head
while current_node.next and current_node.next != node_to_delete:
current_node = current_node.next
if current_node.next is None:
return head
current_node.next = current_node.next.next
return head
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
print("Before deletion:")
traverse_and_print(node1)
node1 = delete_specific_node(node1, node4)
print("After deletion:")
traverse_and_print(node1)
درج یک گره
برای درج، گره جدید را بساز. سپس لینک قبلی به جدید و جدید به بعدی وصل می شود.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverse_and_print(head):
current_node = head
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next
print("null")
def insert_node_at_position(head, new_node, position):
if position == 1:
new_node.next = head
return new_node
current_node = head
for _ in range(position - 2):
if current_node is None:
break
current_node = current_node.next
new_node.next = current_node.next
current_node.next = new_node
return head
node1 = Node(7)
node2 = Node(3)
node3 = Node(2)
node4 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
print("Original list:")
traverse_and_print(node1)
new_node = Node(97)
node1 = insert_node_at_position(node1, new_node, 2)
print("After insertion:")
traverse_and_print(node1)
گام های عملی
- کلاس Node را بساز.
- پیمایش را پیاده سازی کن.
- حذف و درج را تمرین کن.
برای ساخت «صف»، صفحه صف ها را ببین. برای مقایسه با «پشته»، به پشته ها سر بزن.
جمع بندی سریع
- لیست پیوندی پویاست و جابه جایی ندارد.
- دسترسی تصادفی ندارد؛ باید پیمایش کنیم.
- حذف و درج بسیار سرراست انجام می شود.
- حافظه بیشتری نسبت به آرایه مصرف می کند.