פייתון/פייתון גרסה 3/רשימה מקושרת
רשימה מקושרת או משורשת היא מבנה נתונים בו יש אוסף איברים ("ערכים") המפוזרים בזיכרון מחשב ומצביע לאיבר הבא ברשימה.
ההבדל בין רשימה לרשימה מקושרת
עריכהרשימה רגילה תופסת מקום מסוים בזיכרון. בכדי להוסיף אל רשימה איבר נוסף עלינו להעתיק למיקום חדש בזיכרון את הרשימה כולה ולהוסיף את האיברים החדשים. רשימה מקושרת לעומת זאת היא רשימה שמקשרת בין איברים הנמצאים בזיכרון של פיתון.
דוגמה
עריכה# simple example
class Node:
def __init__(self, data=None):
self.data = data
def __str__(self):
return str(self.data)
node_1 = Node(1)
node_2 = Node(33)
node_3 = Node(55)
#linked
node_1.next = node_2 # 1-->33
node_2.next = node_3 # 33-->55
lst = [node_1.data, node_1.next.data, (node_1.next).next.data]
print(lst)
>>>[1, 33, 55]
יצרנו רשימה מקושרת. איננו יכולים להציגה ולכן נעזרו בהכנסת ערכיה אל רשימה. הרשימה מקשרת בין האוביקטים שה-data שלהם: 1,33,55.
כיצד מיצרים רשימה מקושרת
עריכהמהדוגמה לעיל אנו מבינים כי יש לבצע שתי פעולות ליצירת רשימה מקושרת:
- יצירת אוביקטים בעלי מאפיינים דומה.
- לקשר בין האובייקטים.
בכדי לא לכתוב שוב ושוב מחדש את פעולת next נהוג ליצור מחלקה נוספת שמקשרת בין איברי הרשימה.
דוגמה שנייה
עריכהclass Node:
def __init__(self, data = None):
self. data = data
self.next = None
class Linked_list:
def __init__(self):
self.head = Node()
def append(self,data):
current_node = self.head
new_node = Node(data) #creates new object
#linked new node with the last node - go over the list
while current_node.next != None:
current_node = current_node.next #go to the last node
current_node.next = new_node #the next one , after it, will recived the value which we will input
def display(self):
elems = []
current_node = self.head
while current_node.next != None:
current_node = current_node.next
elems.append(current_node.data)
print(elems)
my_list = Linked_list()
my_list.display()
>>>[]
my_list.append(1)
my_list.append(1)
my_list.display()
>>>[1, 1]
בדוגמה זו יצרנו רשימה מקושרת שניתן להציגה באמצעות רשימה.
ראשית יצרנו הגדרה משותפת לכל האוביקטיים שמקושרים אחד לשני ברשימה המקושרת. המשותף להם הוא ה-data בהם וקיום איבר אחריהם.
לאחר מכן יצרנו מחלקה של הרשימה המקושרת. המחלקה הזו מייצרת 'קשר בין האובייקטים ב-node על ידי הגדרה שהוספה של node חדש תהיה רק כאשר פייתון תגיע לאיבר האחרון (לפני ה-none) ותוסיף את הערך החדש שנכניס כשנקרא לפונקצית add.
לבסוף יצרנו מתודת עזר שתעזור לנו להציג את הרשימה המקושרת.
דוגמא 3
עריכהיצרת שתי מחלקות : ראש (קדימה ואחורה), אוביקט עם איבר הבא.
הסרת איבר
עריכהמציאת איבר ברשימה מקושרת
עריכהdef find_node(head, i):
if =< 0:
return None
else:
while head and i>0 : #while head is not None and i>0
i-=1
head=head.next()
return head