سال‌های خیلی دور دو مطلب در مورد لیست پیوندی یک طرفه و لیست پیوندی دو طرفه در سی‌پلاس‌پلاس نوشتم. می‌توانید در دو لینک زیر، آن دو مطلب را مشاهده بفرمایید.
همچنین مطالب دیگری در زمینه لیست پیوندی داریم که برای شما بسیار مفید خواهند بود:
اما امروز می‌خواهم در مورد لینک لیست در پایتون بنویسم. مفهوم لیست پیوندی در تمام زبان‌های برنامه نویسی به یک شکل است. به همین دلیل با مراجعه به دو آدرس بالا می‌توانید با مفاهیم لیست پیوندی یک طرفه آشنا شوید بخضوص که تصویرهای خوبی دارند.
برای تعریف یک لیست پیوندی ابتدا به یک کلاس گره (Node) نیاز داریم تا داده‌هایمان را در آن ذخیره کنیم و همچنین آدرس به گره بعدی را نگه داریم. برای این منظور کد پایتون زیر را نوشته‌ایم:
class Node:
def __init__(self, data=None, next=None):
# Data on node
self.data = data
# Next node
self.next = next
def set_data(self, data):
self.data = data
def set_next_node(self, node):
self.next = node
def get_data(self):
return self.data
def get_next(self):
return self.nextاین کلاس دو ویژگی برای ذخیره داده و آدرس گره بعدی دارد. همچنین چهار عملگر برای خواند و نوشتن آن دو ویژگی دارد.
اکنون که یک کلاس برای گره‌ها تعریف کردیم. حالا می‌توانیم کلاس لیست پیوندی را بنویسیم. تنها ویژگی‌ای که کلاس لینک لیست نیاز دارد، یک اشاره‌گر به گره اول لیست‌پیوندی است. در زیر این قسمت از کد کلاس را مشاهده می‌کنید.
class LinkedList:
def __init__(self, node=None):
self.head = nodeحالا که ویژگی کلاس Link List را تعریف کردیم، به ترتیب به عملگرهای (متد) این کلاس می‌پردازیم. اولین عملگری که برای کلاس لیست پیوندی می‌نویسیم، یک تابع برای شماردن تعداد گره‌های درون لیست است. این کار را با استفاده از کد زیر انجام می‌دهیم:
def size(self):
# counter
counter = 0
# start form head of linked list
pointer = self.head
while pointer is not None:
# count
counter += 1
# go to next node
pointer = pointer.get_next()
return counterدر این کد مقدار شمارنده را برابر صفر می‌گذاریم. سپس از اشاره‌گر به اول لیست شروع میکنیم و در ادامه به آدرس گره بعدی می‌رویم و این کار را تا زمانی که به آخر لیست برسیم ادامه می‌دهیم. زمانی به آخر لیست می رسیم که آدرس بعدی گره بعدی یک گره برابر با None یا پوچ باشد.
متد بعدی، تابعی برای اضافه کردن یک گره به لیست پیوندی است. برای این کار تابع زیر را نوشته‌ایم:
def insert_node(self, data):
# start from head of linked list
pointer = self.head
# if linked list is empty
if pointer is None:
self.head = Node(data=data)
return
# find last node in the linked list
while pointer.get_next() is not None:
pointer = pointer.get_next()
# link last node on list to new node
pointer.set_next_node(Node(data=data))در این تابع یک داده به عنوان ورودی به متد داده می‌شود که این داده هر نوعی (type) می‌تواند باشد. سپس از گره اول لیست شروع به حرکت می‌کند و هر بار با استفاده از آدرس گره بعدی که در گره موجود است به گره بعد می‌رود. این کار تا زمانی که به آخر لیست پیوندی برسیم ادامه خواهد یافت. سپس با استفاده از داده یک گره ساخته می‌شود و آدرس گره بعدی گره‌ی آخر برابر با آدرس گره‌ی آخر قرار داده می‌شود. اینگونه گره‌ای جدید به لیست اضافه می‌شود.
تابع بعدی، تابع جست و جو درون لیست پیوندی است. با این تابع می‌تواینم درون لینک لیست را برای پیدا کردن یک گره با داده‌ای مشخص بگردیم. برای این کار متد زیر را برای کلاس لیست پیوندی نوشته‌ایم:
def search(self, data):
# counter
counter = 0
# start form head of linked list
pointer = self.head
while pointer is not None:
# count
counter += 1
if pointer.get_data() == data:
# if found
return counter-1, pointer
# go next node
pointer = pointer.get_next()
# If not found
return None, Noneمانند تابع‌های قبل از گره‌ای نخست شروع میکنیم و مرتب به گره‌ی بعد می‌رویم تا زمانی که به آخر لیست پیوندی برسیم و یا گره‌ای را پیدا کنیم که داده‌های مد نظر را داشته باشد. در صورت پیدا شدن اندیس گره در لیست پیوندی و یک اشاره‌گر به گره برگردانده می‌شود.
تابع بعدی، تابع حذف یک گره با استفاده از اندیس آن گره در لیست پیوندی است. برای این کار متد زیر را نوشته‌ایم:
def delete(self, node_index):
# counter
counter = -1
# pointer to the previous node
pre_pointer = None
# start form head of linked list
pointer = self.head
while counter + 1 != node_index and pointer is not None:
# set previous pointer
pre_pointer = pointer
# go next node
pointer = pointer.get_next()
# increment counter
counter += 1
if pointer is self.head:
# delete first node
self.head = pointer.get_next()
del pointer
elif pointer.get_next() is None:
# delete last object
pre_pointer.set_next_node(node=None)
del pointer
else:
# node in middle
pre_pointer.set_next_node(node=pointer.get_next())
del pointerبرای این کار ابتدا یک اشاره گر به گره اول قرار می‌دهیم. هر بار یک گره به جلو می‌رویم تا به گره با اندیس مورد نظر برسیم. همچنین هر بار که اشاره‌گر را جلو می‌بریم یک اشاره گر دیگر استفاده میکنیم تا مقدار قبلی اشاره‌گر را نگه داریم. بعد از پیدا کردن گره مورد نظر، با توجه به موقعیت گره که می‌تواند در ابتدا، وسط و انتهای لیست پیوندی باشد عمل میکنیم. اگر گره در ابتدا باشد اشاره‌گر لیست پیوندی که به خانه اول اشاره می‌کند باید عوض شود تا به خانه بعدی اشاره کند. در صورتی که گره مورد نظر، گره انتهایی باشد، اشاره‌گر به گره بعدی، گره یکی به آخر را باید برابر با None و یا پوچ قرار دهیم. در صورتی که گره مورد نظر یک گره در اواسط لیست پیوندی باشد، باید گره قبل از آن را به گره بعد از آن وصل کرد. مانند شکل زیر:
متد آخر نیز برای چاپ اطلاعات درون لیست پیوندی به ترتیب محل قرارگیری آن‌ها درون لیست پیوندی است:
def print(self):
# counter
counter = 0
# start form head of linked list
pointer = self.head
while pointer is not None:
# count
counter += 1
# print data of Node
print("Node {}\'th Data: {}".format(counter, pointer.get_data()))
# go to next node
pointer = pointer.get_next()
return counter
اکنون که کد لیست پیوندی در پایتون را نوشتیم، متد‌های نوشته شده را تست می‌کنید. ابتدا یک شی از لیست پیوندی ایجاد میکنیم:
# create an object
ll_obj = LinkedList()سپس یک گره (Node) به لیست پیوندی اضافه میکنیم و بعد از آن لیست‌پیوندی و اندازه آن را چاپ میکنیم:
# add 1'th node to linked list
ll_obj.insert_node(data=[3, 7])
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)خروجی این قسمت از کد برابر می‌شود با
Node 1'th Data: [3, 7] Size of Linked List: 1
در ادامه ۵ گره دیگر با مقدارهای متفاوت به لیست پیوندی اضافه میکنیم و در گام لیست پیوندی و اندازه‌اش را چاپ میکنیم:
#########################################################
# add 2'th node to linked list
ll_obj.insert_node(data="open-mind.ir")
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# add 3'th node to linked list
ll_obj.insert_node(data=['Rostam', 'Ferdosi', 'Bahram'])
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# add 4'th node to linked list
ll_obj.insert_node(data={'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'})
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# add 5'th node to linked list
ll_obj.insert_node(data=3.14)
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}".format(ll_obj.size()))
print('=' * 20)
#########################################################
# add 6'th node to linked list
ll_obj.insert_node(data=[[6, 7], [2, 4]])
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################خروجی این تکه کد برابر زیر است:
====================
Node 1'th Data: [3, 7]
Node 2'th Data: open-mind.ir
Size of Linked List: 2
====================
Node 1'th Data: [3, 7]
Node 2'th Data: open-mind.ir
Node 3'th Data: ['Rostam', 'Ferdosi', 'Bahram']
Size of Linked List: 3
====================
Node 1'th Data: [3, 7]
Node 2'th Data: open-mind.ir
Node 3'th Data: ['Rostam', 'Ferdosi', 'Bahram']
Node 4'th Data: {'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'}
Size of Linked List: 4
====================
Node 1'th Data: [3, 7]
Node 2'th Data: open-mind.ir
Node 3'th Data: ['Rostam', 'Ferdosi', 'Bahram']
Node 4'th Data: {'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'}
Node 5'th Data: 3.14
Size of Linked List: 5
====================
Node 1'th Data: [3, 7]
Node 2'th Data: open-mind.ir
Node 3'th Data: ['Rostam', 'Ferdosi', 'Bahram']
Node 4'th Data: {'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'}
Node 5'th Data: 3.14
Node 6'th Data: [[6, 7], [2, 4]]
Size of Linked List: 6اکنون مقدارهای مختلف را در لیست پیوندی جست‌وجو میکنیم تا اندیس گره‌های متناظر با آن‌ها را در صورت موجود بودن پیدا کنیم:
# search
idx_in_ll, pointer = ll_obj.search(data=[1, 3])
print('Search Result:')
print('Index in Linked List {}.'.format(idx_in_ll))
print('=' * 20)
#########################################################
# search
idx_in_ll, pointer = ll_obj.search(data=['Rostam', 'Ferdosi', 'Bahram'])
print('Search Result:')
print('Index in Linked List {}.'.format(idx_in_ll))
print('=' * 20)
#########################################################
# search
idx_in_ll, pointer = ll_obj.search(data=3.14)
print('Search Result:')
print('Index in Linked List {}.'.format(idx_in_ll))
print('=' * 20)
#########################################################
# search
idx_in_ll, pointer = ll_obj.search(data={'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'})
print('Search Result:')
print('Index in Linked List {}.\n'.format(idx_in_ll))
print('=' * 20)خروجی این تکه کد را در زیر مشاهده می‌کنید:
==================== Search Result: Index in Linked List None. ==================== Search Result: Index in Linked List 2. ==================== Search Result: Index in Linked List 4. ==================== Search Result: Index in Linked List 3.
اکنون نوبت تست عملگر حذف یک گره با استفاده از اندیس آن گره در لیست پیوندی است. به این منظور هر بار یک گره با اندیس مشخص را انتخاب میکنیم و آن را حذف میکنیم و لیست پیوندی قبل و بعد از حذف آن گره را در هر گام نشان می‌دهیم.
#########################################################
# delete
# print linked list
print('Before delete 6\'th node')
ll_obj.print()
print("Size of Linked List: {}\n".format(ll_obj.size()))
# delete 5'th node
ll_obj.delete(node_index=5)
# print linked list
print('After delete 6\'th node')
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# delete
# print linked list
print('Before delete 1\'th node')
ll_obj.print()
print("Size of Linked List: {}\n".format(ll_obj.size()))
# delete 5'th node
ll_obj.delete(node_index=0)
# print linked list
print('After delete 1\'th node')
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# delete
# print linked list
print('Before delete 2\'th node')
ll_obj.print()
print("Size of Linked List: {}\n".format(ll_obj.size()))
# delete 5'th node
ll_obj.delete(node_index=1)
# print linked list
print('After delete 2\'th node')
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################خروجی این تکه کد در زیر آورده شده است:
====================
Before delete 6'th node
Node 1'th Data: [3, 7]
Node 2'th Data: open-mind.ir
Node 3'th Data: ['Rostam', 'Ferdosi', 'Bahram']
Node 4'th Data: {'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'}
Node 5'th Data: 3.14
Node 6'th Data: [[6, 7], [2, 4]]
Size of Linked List: 6
After delete 6'th node
Node 1'th Data: [3, 7]
Node 2'th Data: open-mind.ir
Node 3'th Data: ['Rostam', 'Ferdosi', 'Bahram']
Node 4'th Data: {'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'}
Node 5'th Data: 3.14
Size of Linked List: 5
====================
Before delete 1'th node
Node 1'th Data: [3, 7]
Node 2'th Data: open-mind.ir
Node 3'th Data: ['Rostam', 'Ferdosi', 'Bahram']
Node 4'th Data: {'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'}
Node 5'th Data: 3.14
Size of Linked List: 5
After delete 1'th node
Node 1'th Data: open-mind.ir
Node 2'th Data: ['Rostam', 'Ferdosi', 'Bahram']
Node 3'th Data: {'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'}
Node 4'th Data: 3.14
Size of Linked List: 4
====================
Before delete 2'th node
Node 1'th Data: open-mind.ir
Node 2'th Data: ['Rostam', 'Ferdosi', 'Bahram']
Node 3'th Data: {'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'}
Node 4'th Data: 3.14
Size of Linked List: 4
After delete 2'th node
Node 1'th Data: open-mind.ir
Node 2'th Data: {'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'}
Node 3'th Data: 3.14
Size of Linked List: 3
====================
خوب لیست پیوندیمان را در Python ایجاد کردیم و آن را تست کردیم. این لینک لیست یک نمونه ساده بود و حالا می‌توانید با آن سر و کله بزنید و امکانات بیشتری به آن اضافه کنید.
کد کلی برنامه لیست پیوندی در پایتون را در زیر مشاهده می‌فرمایید:
class Node:
def __init__(self, data=None, next=None):
# Data on node
self.data = data
# Next node
self.next = next
def set_data(self, data):
self.data = data
def set_next_node(self, node):
self.next = node
def get_data(self):
return self.data
def get_next(self):
return self.next
class LinkedList:
def __init__(self, node=None):
self.head = node
def size(self):
# counter
counter = 0
# start form head of linked list
pointer = self.head
while pointer is not None:
# count
counter += 1
# go to next node
pointer = pointer.get_next()
return counter
def insert_node(self, data):
# start from head of linked list
pointer = self.head
# if linked list is empty
if pointer is None:
self.head = Node(data=data)
return
# find last node in the linked list
while pointer.get_next() is not None:
pointer = pointer.get_next()
# link last node on list to new node
pointer.set_next_node(Node(data=data))
def search(self, data):
# counter
counter = 0
# start form head of linked list
pointer = self.head
while pointer is not None:
# count
counter += 1
if pointer.get_data() == data:
# if found
return counter-1, pointer
# go next node
pointer = pointer.get_next()
# If not found
return None, None
def delete(self, node_index):
# counter
counter = -1
# pointer to the previous node
pre_pointer = None
# start form head of linked list
pointer = self.head
while counter + 1 != node_index and pointer is not None:
# set previous pointer
pre_pointer = pointer
# go next node
pointer = pointer.get_next()
# increment counter
counter += 1
if pointer is self.head:
# delete first node
self.head = pointer.get_next()
del pointer
elif pointer.get_next() is None:
# delete last object
pre_pointer.set_next_node(node=None)
del pointer
else:
# node in middle
pre_pointer.set_next_node(node=pointer.get_next())
del pointer
def print(self):
# counter
counter = 0
# start form head of linked list
pointer = self.head
while pointer is not None:
# count
counter += 1
# print data of Node
print("Node {}\'th Data: {}".format(counter, pointer.get_data()))
# go to next node
pointer = pointer.get_next()
return counter
if __name__ == '__main__':
# create an object
ll_obj = LinkedList()
#########################################################
# add 1'th node to linked list
ll_obj.insert_node(data=[3,7])
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# add 2'th node to linked list
ll_obj.insert_node(data="open-mind.ir")
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# add 3'th node to linked list
ll_obj.insert_node(data=['Rostam', 'Ferdosi', 'Bahram'])
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# add 4'th node to linked list
ll_obj.insert_node(data={'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'})
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# add 5'th node to linked list
ll_obj.insert_node(data=3.14)
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}".format(ll_obj.size()))
print('=' * 20)
#########################################################
# add 6'th node to linked list
ll_obj.insert_node(data=[[6, 7], [2, 4]])
# print linked list
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# search
idx_in_ll, pointer = ll_obj.search(data=[1, 3])
print('Search Result:')
print('Index in Linked List {}.'.format(idx_in_ll))
print('=' * 20)
#########################################################
# search
idx_in_ll, pointer = ll_obj.search(data=['Rostam', 'Ferdosi', 'Bahram'])
print('Search Result:')
print('Index in Linked List {}.'.format(idx_in_ll))
print('=' * 20)
#########################################################
# search
idx_in_ll, pointer = ll_obj.search(data=3.14)
print('Search Result:')
print('Index in Linked List {}.'.format(idx_in_ll))
print('=' * 20)
#########################################################
# search
idx_in_ll, pointer = ll_obj.search(data={'Iran': 'Tehran', 'Sweden': 'Stockholm', 'India': 'New Delhi'})
print('Search Result:')
print('Index in Linked List {}.\n'.format(idx_in_ll))
print('=' * 20)
#########################################################
# delete
# print linked list
print('Before delete 6\'th node')
ll_obj.print()
print("Size of Linked List: {}\n".format(ll_obj.size()))
# delete 5'th node
ll_obj.delete(node_index=5)
# print linked list
print('After delete 6\'th node')
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# delete
# print linked list
print('Before delete 1\'th node')
ll_obj.print()
print("Size of Linked List: {}\n".format(ll_obj.size()))
# delete 5'th node
ll_obj.delete(node_index=0)
# print linked list
print('After delete 1\'th node')
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
# delete
# print linked list
print('Before delete 2\'th node')
ll_obj.print()
print("Size of Linked List: {}\n".format(ll_obj.size()))
# delete 5'th node
ll_obj.delete(node_index=1)
# print linked list
print('After delete 2\'th node')
ll_obj.print()
# Print size of Linked List
print("Size of Linked List: {}\n".format(ll_obj.size()))
print('=' * 20)
#########################################################
نوشته لیست پیوندی در پایتون – Linked List in Python اولین بار در اوپن مایند. پدیدار شد.
