פייתון/פייתון גרסה 3/רשימה מקושרת

רשימה מקושרת או משורשת היא מבנה נתונים בו יש אוסף איברים ("ערכים") המפוזרים בזיכרון מחשב ומצביע לאיבר הבא ברשימה.

ההבדל בין רשימה לרשימה מקושרת

רשימה רגילה תופסת מקום מסוים בזיכרון. בכדי להוסיף אל רשימה איבר נוסף עלינו להעתיק למיקום חדש בזיכרון את הרשימה כולה ולהוסיף את האיברים החדשים. רשימה מקושרת לעומת זאת היא רשימה שמקשרת בין איברים הנמצאים בזיכרון של פיתון.

list VS linked list

דוגמה

# 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.

כיצד מיצרים רשימה מקושרת

מהדוגמה לעיל אנו מבינים כי יש לבצע שתי פעולות ליצירת רשימה מקושרת:

1. יצירת אוביקטים בעלי מאפיינים דומה.
2. לקשר בין האובייקטים.

בכדי לא לכתוב שוב ושוב מחדש את פעולת 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