Linked list - רשימה מקושרת - תיאוריה, קוד ואתגרים תכנותיים

Linked list "רשימה מקושרת" היא מבנה נתונים פשוט למדי המורכב מאיברים nodes כשכל איבר מצביע refers על האיבר הבא ברשימה, והאיבר האחרון מצביע על "שום דבר" (Null).

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

ניתן להשתמש ברשימות מקושרות Linked lists על מנת ליישם מבני נתונים אחרים דוגמת: stacks ערימות, queues תורים, ומילונים dictionaries.

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

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

רשימה מקושרת מורכבת מאיברים nodes כשכל איבר מצביע על האיבר הבא ברשימה, והאיבר האחרון מצביע על Null (מכונה None בפייתון).

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

הגדרת קלאס Node בשביל איבר ברשימה

רשימה מקושרת בנויה מאיברים, Nodes. לכל איבר 2 תכונות, מידע ומצביע על האיבר הבא ברשימה:

• data - המידע שהאיבר מכיל
• next - מצביע על האיבר הבא ברשימה

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

הגדרת קלאס LinkedList בשביל רשימה מקושרת

האיבר הראשון ברשימה מכונה ראש הרשימה head, ואין מצביע next אשר מצביע עליו.

אם הרשימה ריקה אז ה-head יצביע על None:

class LinkedList:
    def __init__(self):
        self.head = None

אם הרשימה מכילה שני איברים אז התכונה next של הראשון תצביע על האיבר השני:

• האיבר בראש הרשימה מכונה head. האיבר בזנב הרשימה tail מצביע על Null (שזה אומר שהוא לא מצביע על מידע קיים בזיכרון).

הוספת איבר לסוף רשימה מקושרת

הוספת איבר לסוף הרשימה נעשית על ידי כיוון המצביע next של זנב הרשימה על ה-node החדש.

נוסיף לקלאס LinkedList את המתודה insert_at_end() אשר מוסיפה איבר לסוף הרשימה:

def insert_at_end(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    return node

• המתודה מתחילה מיצירת איבר חדש מהקלאס Node.
• אם הרשימה ריקה המתודה תוסיף את ה-node בתור ראש הרשימה head.
• אם הרשימה אינה ריקה המתודה תעבור באופן סדרתי traverse על איברי הרשימה וכשתגיע לאיבר האחרון ברשימה תכוון את המצביע next של האיבר על ה-node החדש.

הוספת איבר לתחילת רשימה מקושרת

בניגוד למערך, אפשר להוסיף איבר עוד לפני ראש הרשימה הקיים על ידי כיוון next של ה-node החדש על ה-head המקורי של הרשימה וכיוון ה-head של הרשימה על האיבר החדש.

נוסיף את המתודה insert_at_beginning() שתוסיף איברים לתחילת הרשימה:

def insert_at_beginning(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

• המתודה מתחילה מיצירת איבר node חדש וכיוון ה-next שלו על ה-head הקיים של הרשימה.
• המתודה מסיימת בהגדרת ה-head של הרשימה על ה-node החדש.

מעבר סדרתי על איברי רשימה מקושרת traversal

כדי לעבור באופן סדרתי על איברי הרשימה traverse מתחילים מה-node בראש הרשימה. המצביע של head מצביע על האיבר השני ברשימה אז עוברים לאיבר השני ברשימה. ה-next של השני מצביע על האיבר השלישי אז עוברים אליו. וחוזר חלילה, עוברים לפי סדר על כל ה-nodes הבאים בתור באמצעות התכונה next של כל node . המעבר נפסק כשמגיעים ל-Null כיוון שזנב הרשימה למעשה לא מצביע על שום דבר. הפסאודו-קוד הבא מדגים תהליך של מעבר סדרתי באמצעות לולאה שמתקדמת בכל פעם איבר אחד:

current = head

while current: 
    current = current.next 

נסביר:

1. current = head

   המצביע pointer ששמו current מתחיל מהצבעה לראשה של הרשימה head.

2. הלולאה while תרוץ כל עוד המצביע אינו None כדי להבטיח שעוברים על כל האיברים ברשימה עד סופה.

3. בתוך הלולאה רצה השורה:

   current = current.next

   בשורה זו הערך של current.next מחליף את הערך של current ועל ידי זה הסמן מתקדם לאיבר הבא ברשימה.

נוסיף לקלאס LinkedList מתודה count_nodes() אשר מיישמת מעבר סדרתי על איברי הרשימה traversal לצורך ספירת מספר האיברים ברשימה:

def count_nodes(self):
    count = 0
    current_node = self.head
    while current_node:
        count += 1
        current_node = current_node.next
    return count

1. המתודה מתחילה באתחול המונה count ל-0. תפקיד המונה לעקוב אחר מספר ה-nodes ברשימה.
2. הגדרת current_node על head הרשימה כדי להכין את השטח למעבר על איברי הרשימה באופן סדרתי traversal.
3. כניסה ללולאה while שתמשיך לרוץ כל עוד ישנם איברים נוספים ברשימה (כל עוד current_node אינו None).
4. בתוך הלולאה, תוסיף אחד למונה עבור כל איבר נוסף.

5. current_node = current_node.next

   מניע את המעבר לאיבר הבא של הרשימה.

6. חזרה על שלבים 4 ו- 5 עד שמגיעים לסוף הרשימה כאשר current_node מקבלת ערך None.
7. כאשר הלולאה מסיימת לרוץ, תחזיר את הערך אותו צבר המונה count המייצג את מספר האיברים ברשימה.

מתודה להדפסת רשימה מקושרת באמצעות מעבר סדרתי

חשוב להוסיף מתודת __str__ לכל קלאס כדי להדפיס את תוצאת ההפעלה של הקלאס. (למה ואיך? קרא על מתודות ותכונות קסם של פייתון). אנחנו נשתמש במעבר סדרתי traversal בשביל להדפיס את התוצאה של הקלאס:

def __str__(self):
    ll_str = ""
    current_node = self.head
    while current_node:
        ll_str += f"{current_node.data}->"
        current_node = current_node.next
    ll_str += "None"
    return ll_str

הסרת איבר מרשימה מקושרת

נוסיף את המתודה remove() שתפקידה להסיר nodes מהרשימה. הדבר הראשון הוא לבדוק אם הרשימה ריקה:

def remove(self, data):
    if self.head is None:
        return

• התנאי הראשון אותו יש לבדוק הוא אם הרשימה ריקה. כלומר, האם head הוא None. במקרה זה המתודה לא תחזיר דבר.

במקרה בו צריך להסיר את האיבר הראשון של הרשימה המתודה תכוון את ה-head של ה-LinkedList על האיבר הבא של הרשימה:

def remove(self, data):
    if self.head is None:
        return

    # If the node to remove is the head node
    # point head to the next node then return
    if self.head.data == data:
       self.head = self.head.next
       return

• אם המידע data אשר ב-node הראשון של הרשימה (מכונה head) תואם לערך הפרמטר data אותו קיבלה הפונקציה יש להסיר את האיבר. לשם כך, הפונקציה תעדכן את head הרשימה להצביע על ה-next של האיבר המהווה head ברשימה הנוכחית.

self.head = self.head.next

כדי להבין איך מסירים איבר מהאמצע צריך לקחת בחשבון 3 איברים בכל פעם:

• האיבר הנוכחי
• האיבר הקודם לנוכחי
• האיבר הבא אחרי הנוכחי

במידה והאיבר אותו רוצים להסיר הוא לא האיבר הראשון יש לעבור על האיברים באופן סדרתי ואם נמצא האיבר אותו מבקשים להסיר יש לכוון את המצביע next של ה-node הקודם לנוכחי על ה-node הבא אחרי הנוכחי:

def remove(self, data):
    if self.head is None:
        return


    # If the node to remove is the head node
    # point head to the next node then return
    if self.head.data == data:
        self.head = self.head.next
        return


    # Prepare for list traversal
    current_node = self.head
    prev_node = None


    # As long as data is not found
    # store the values of the previous and next nodes
    while current_node and current_node.data != data:
        prev_node = current_node
        current_node = current_node.next
        # If not found - return
        if current_node is None:
            return
        # If found - point previous node to next node
        prev_node.next = current_node.next

ועכשיו הכל ביחד

אחרי שהסברנו וכתבנו נסכם.

קלאס Node:

class Node:
    """
    A node in a linked list.

    Attributes:
        data: The data stored in the node.
        next: The next node in the list.
    """
    def __init__(self, data=None, next=None):
        """
        Initialize a node with the given data and next node.

        Args:
            data: The data to store in the node.
            next: The next node in the list.
        """
        self.data = data
        self.next = next

קלאס LinkedList:

class LinkedList:
    """
    A linked list.

    Attributes:
        head: The head node of the list.
    """
    def __init__(self):
        """
        Initialize an empty linked list.
        """
        self.head = None

    def insert_at_end(self, data):
        """
        Append the given data to the end of the list.

        Args:
            data: The data to append to the list.
        """
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current_node = self.head
            while current_node.next:
                current_node = current_node.next
            current_node.next = new_node
            
    def insert_at_beginning(self, data):
        """
        Insert the given data at the beginning of the list.

        Args:
            data: The data to insert at the beginning of the list.
        """
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    
    def remove(self, data):
        """
        Remove the node with the given data from the list.

        Args:
            data: The data of the node to remove.
        """
        if self.head is None:
            return

        # If the node to remove is the head node
        # point head to the next node then return
        if self.head.data == data:
            self.head = self.head.next
            return

        # Prepare for list traversal
        current_node = self.head
        prev_node = None

        # As long as data is not found
        # store the values of the previous and next nodes
        while current_node and current_node.data != data:
            prev_node = current_node
            current_node = current_node.next
        
        # If not found - return
        if current_node is None:
            return  
        
        # If found - point previous node to next node
        prev_node.next = current_node.next  
        
    def count_nodes(self):
        """
        Count the number of nodes in the linked list.

        Returns:
            The number of nodes in the linked list.
        """
        count = 0  
        current_node = self.head
        while current_node:
            count += 1
            current_node = current_node.next
        return count
            

    def __str__(self):
        """
        Return a string representation of the list.

        Returns:
            A string representation of the list.
        """
        ll_str = ""
        current_node = self.head
        while current_node:
            ll_str += f"{current_node.data}->"
            current_node = current_node.next
        ll_str += "None"
        return ll_str

ניתוח ביצועים

כפי שראינו, רשימה מקושרת linked list היא שרשרת של איברים nodes, כאשר כל איבר מכיל מידע data ומצביע next שמורה על האיבר הבא בשרשרת. העובדה שמבנה הנתונים נעזר במצביע מקלה על אחסון הנתונים כי לא צריך לשנות את הגודל המוקצה בזכרון (כמו שצריך לעשות עם מערכים) מה שאומר שאם רוצים להוסיף או להסיר איבר מראש הרשימה או מסופה אז משך הזמן לביצוע מוערך כזמן קבוע O(1) מה שהופך את הפעולות להכי יעילות שאפשר (אם משהו לא ברור נא לקרוא את מדריך big - O). מצד שני, גישה לאיברים, תוספת או מחיקה מאמצע הרשימה דורש מעבר סדרתי traversal שמשך הזמן שלו במקרה הגרוע הוא לינארי O(n).

"המתחרה" העיקרי של רשימות מקושרות הוא המערך. מערכים של פייתון מציעים יתרון בביצועים כשרוצים לגשת או לערוך פריטים באמצע המערך בגלל שניתן לגשת לפריטים על סמך האינדקס שלהם. מחיקה או הוספה של פריטים לאמצע המערך היא מסובכת יותר מאשר ב-linked list בגלל שצריך להזיז את כל הפריטים אחרי מקום השינוי. כיוון שמערכים ורשימות מקושרות מציעים יתרונות וחסרונות שונים צריך לבחור במבנה על פי הנדרש במשימה התכנותית. בדרך כלל הנטייה היא לבחור במערכים אבל ידע על רשימות מקושרות עשוי להועיל עבור משימות ספציפיות.

אתגרים תכנותיים עבור רשימות מקושרות

אתגר 1: זיהוי כפילויות ברשימה מקושרת

עליך לכתוב פונקציה שמקבלת רשימה מקושרת בתור קלט ומחזירה True אם הרשימה מכילה ערכים כפולים, אחרת False. לשם כך, עליך ליישם את הפונקציה detect_duplicates(head) כאשר head הוא האיבר הראשון של הרשימה המקושרת.

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

1 -> 2 -> 3 -> 2 -> 4

הפונקציה צריכה להחזיר True כיוון שה-node שערכו 2 מופיע פעמיים ברשימה.

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

5 -> 7 -> 9 -> 3 -> 1

הפונקציה צריכה להחזיר False כיוון שאין כפילויות ברשימה.

תנסה לכתוב פונקציה:

detect_duplicate(head: Node) -> bool

שמקבלת את ה-head של רשימה כפרמטר.

רק אחרי שניסית אתה רשאי להציץ בפתרון. אם תציץ בלי לנסות אז דיר-באלק! אני לא אחראי לתוצאה…

תשובה לדוגמה:

# Take the head node of the linked list as an input
def detect_duplicates(head): 
    # Initialize an empty list, elements, to keep track of elements encountered.
    current = head 
    elements = [] 
    # Iterate through the linked list by traversing the nodes using the next pointers.
    while current: 
        # For each node, check if the data value is already present in the elements list.
        # If a duplicate is found, return True.

        if current.data in elements: 
            return True 
        # Append the current node to the elements list
        elements.append(current.data) 
        current = current.next 
    # If the end of the linked list is reached without finding any duplicates return False
    return False

נבחן את הפתרון:

# Case 1: Has no duplicate
l = [1, 2, 3]
ll = LinkedList() 
for item in l:
    ll.insert_at_end(item) 

print(detect_duplicates(ll.head)) # False


# Case 2: Contains duplicate
l = [1, 2, 3, 1]
ll = LinkedList() 
for item in l:
    ll.insert_at_end(item) 

print(detect_duplicates(ll.head)) # True

אתגר 2: זיהוי מעגל ברשימה מקושרת

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

def has_cycle(head: Node) -> bool:
    pass

• Input: הפונקציה has_cycle מקבלת את ה-head של רשימה מקושרת בתור קלט.
• Output: הפונקציה צריכה להחזיר ערך בוליאני- True אם הפונקציה מכילה מעגל. אחרת False.

דוגמאות:

דוגמה 1:

קלט:

head = 1 -> 2 -> 3 -> 1

פלט:

True

הסבר:

הרשימה המקושרת מכילה מעגל: הצומת שערכו 3 מצביע חזרה על הצומת שערכו 1.

דוגמה 2:

קלט:

head = 1 -> 2 -> 3

פלט:

False

האתגר הוא ליישם את הפונקציה has_cycle לבדיקה האם רשימה מקושרת מכילה מעגל. אם מעגל קיים הפונקציה צריכה להחזיר True אחרת False.

פתרון:

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

לדוגמה, נתונה רשימה שבה הזנב מצביע על הראש כי שניהם אותו node שהוא 1:

1 -> 2 -> 3 -> 1

בשביל ליצור את הרשימה, נגדיר בקוד שהזנב 3 יצביע על 1:

ll = LinkedList()
n1 = ll.insert_at_end(1)
n2 = ll.insert_at_end(2)
n3 = ll.insert_at_end(3)
n3.next = n1

הפתרון מסתמך על אלגוריתם שחשוב לדעת המכונה Floyd algorithm או "אלגוריתם הצב והארנב" שבו משתמשים ב- 2 מצביעים. אחד מהיר שרץ פי 2 יותר מהר מהאיטי:

fast = fast.next.next
slow = slow.next

אם קיים מעגל ברשימה המקושרת, המצביע המהיר יפגע באיטי באיזשהו שלב מה שיגרום לקיום השוויון:

fast == slow

אחרת, המצביע המהיר מגיע לזנבה של הרשימה המקושרת.

פתרון לדוגמה כולל בדיקות קוד:

def has_cycle(head):
    # Initialize slow and fast pointers to the head of the linked list
    slow, fast = head, head

    while fast and fast.next:
        # Move the slow pointer one step at a time
        slow = slow.next
        # Move the fast pointer two steps at a time
        fast = fast.next.next

        # If there is a cycle, the fast pointer will eventually catch up with the slow pointer
        if fast == slow:
            return True

    # If the fast pointer reaches the end (null) or the next node (null), there is no cycle
    return False

# Test cases
ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
print(ll)

res = has_cycle(ll.head)
print(res)
# Output: False


ll1 = LinkedList()
n1 = ll1.insert_at_end(1)
n2 = ll1.insert_at_end(2)
n3 = ll1.insert_at_end(3)
n3.next = n1
# The linked list cannot be printed because it has a cycle

res = has_cycle(ll1.head)
print(res)
# Output: True

הסברנו את הקוד אבל למה הוא עובד?

נדגים באמצעות רשימה מקושרת שבה הזנב "3" מצביע על ראש הרשימה "0":

0 -> 1 -> 2 -> 3 -> 0

שני המצביעים, fast ו-slow מתחילים מפוזיציה "0". אחרי פעם אחת שהלולאה רצה האיטי נמצא בפוזיציה "1" והמהיר בפוזיציה "2". בפעם השנייה שהלולאה רצה האיטי יתקדם בצעד 1 לפוזיציה "2" והמהיר יתקדם שני צעדים ויחזור לפוזיציה "0".

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

4 צעדים דרושים כדי לגרום למצביעים האיטי והמהיר להיפגש באותה הפוזיציה וזה גם אורך הלולאה. זה היה עובד גם עבור לולאה באורך 5, 6 וכיו"ב אז על סמך אינדוקציה אנחנו יכולים להסיק שדרושים n צעדים כדי לאתר לולאה אם משתמשים באלגוריתם "הארנב והצב" המשתמש בשני סמנים - איטי שנע צעד אחד בכל פעם ומהיר שנע פי 2 מהר יותר.

אתגר 3: היפוך רשימה מקושרת

נתונה לך התחלה של קוד הפונקציה ששמה reverse_linked_list() שמקבלת קלט head של רשימה מקושרת ומחזירה רשימה מקושרת שבה סדר האיברים הפוך. עליך להשלים את הקוד החסר:

def reverse_linked_list(head: Node) -> Node:
    ...

נראה 3 דוגמאות לקלט ופלט הפונקציה.

1. בהינתן רשימה:

   1 -> 2 -> 3 -> 4 -> 5

   הפונקציה צריכה להחזיר את הרשימה בסדר הפוך:

   5 -> 4 -> 3 -> 2 -> 1

2. בהינתן רשימה:

   1

   הפונקציה צריכה להחזיר:

   1

3. בהינתן רשימה ריקה הפונקציה תחזיר רשימה ריקה.

הפתרון משתמש בשני מצביעים:

1. prev: מצביע העוקב אחר הצומת הקודם ברשימה כיוון שאין לנו מצביע על האיבר הקודם ברשימה מקושרת אנחנו צריכים משתנה שיאפשר לנו לדעת מיהו האיבר הקודם.

2. current: מצביע על הצומת הנוכחי ברשימה המקושרת.

שני המצביעים עובדים יחד כדי להפוך את הרשימה המקושרת במקום. כאשר מצביע prev מורה על האיבר הבא ברשימה ההפוכה, בעוד שמצביע curr מתקדם בתוך הרשימה המקורית. השילוב של שניהם בקוד גורם לכל איבר ברשימה ההפוכה להצביע על האיבר הקודם במקום על הבא.

אנחנו יכולים ליצור רשימה חדשה אבל זה פתרון פחות יעיל. הפתרון שלנו מבוסס על היפוך מצביעי next של כל איבר בתוך רשימה קיימת. משך הזמן הדרוש לביצוע המשימה הוא יעיל O(n) כיוון שצריך לעבור על כל איבר ברשימה שאורכה n בדיוק פעם אחת והמקום בזכרון הנדרש לפעולה הוא קבוע O(1) כיוון שגישת הפתרון מבוססת הלולאה אותה נציג מיד אינה דורשת תוספת זיכרון לצורך הפתרון כיוון שכל השינויים נעשים במקום, על ידי מניפולציה של מצביעים, ללא צורך במבני נתונים נוספים.

הקוד להלן פותר את הבעיה של היפוך הרשימה המקושרת:

def reverse_linked_list(head: Node) -> Node:
    # Initialize pointers:
    # `prev` - Keeps track of the previous node
    # `curr` - Keeps track of the current node
    prev = None
    curr = head

    # Keep iterating while the `curr` pointer hasn't reached the tail of the original list
    while curr:
        # Cache the pointer to the next node
        next = curr.next
        # Reverse the `next` pointer of the current node to point to the previous node
        curr.next = prev
        # Advance `prev` pointer to the current position
        prev = curr
        # Advance `curr` pointer to the next node in the original list
        curr = next

    # Return the head of the reversed list
    return prev


# Test cases

# Test case 1: Reverse a multi-node linked list
ll1 = LinkedList()
ll1.append(1)
ll1.append(2)
ll1.append(3)
ll1.append(4)

ll1.head = reverse_linked_list(ll1.head)
ll1.display()
# Output: 4 -> 3 -> 2 -> 1 -> None

# Test case 2: Reverse a single-node linked list
ll2 = LinkedList()
ll2.append(1)

ll2.head = reverse_linked_list(ll2.head)
ll2.display()
# Output: 1 -> None

נסביר:

המטרה היא לסובב את כיוונו של כל איבר ברשימה כך שהמצביע next של כל איבר יצביע על האיבר הקודם במקום על הבא בתור.

פתרון האתגר משתמש בשני מצביעים (Two pointers):

• curr - מצביע על האיבר הנוכחי
• prev - מצביע על האיבר הקודם

1. נאתחל את שני המצביעים:

   curr = head
   prev = None

   

   • המצביע curr מצביע על ראש הרשימה ממנו מתחילים לסרוק את הרשימה.

   • המצביע prev מורה מאותחל להיות None (=אין מקום כזה בזכרון, Null) כי אין איבר המקדים את ראש הרשימה. המעקב אחר מיקומו של האיבר הקודם הוא חשוב כדי שנדע להיכן להפנות את המצביע next לאחר ההיפוך.

2. במסגרת ההיפוך, המצביע curr עובר להצביע על האיבר הקודם עליו מצביע prev. כך יוצא שהמצביע עובר להצביע על Null והופך את האיבר הראשון ברשימה לזנב של רשימה.

   

3. מזיזים את המצביעים prev ו- curr כל אחד בנפרד איבר אחד קדימה ברשימה המקורית. עכשיו prev מצביע על איבר 1 ו- curr על 2.

   

   עדיין באותו שלב. מסובבים את המצביע של האיבר עליו מצביע curr כדי שיצביע על האיבר הקודם prev. במקום בו אנו נמצאים בתהליך, האיבר 2 יעבור להצביע על 1.

   

4. חוזרים על אותו התהליך גם עבור האיבר הבא ברשימה. מזיזים את המצביעים curr ו-prev איבר אחד קדימה, ואז מפנים את המצביע של האיבר הנוכחי על האיבר הקודם. במקרה שלנו, איבר 3 עובר להצביע על 2.

   

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

   

6. בשלב האחרון, מחזירים את ה-head של הרשימה ההפוכה.

אתגר 4: פיצול רשימה מקושרת

עליך לפצל רשימה מקושרת לשתי רשימות מקושרות נפרדות - אחת שמקורה בחצי הקדמי של הרשימה המקורית ושנייה שמקורה החצי האחורי. אם מספר האיברים ברשימה המקורית אינו זוגי, האיבר הנוסף צריך להשתייך לחצי הקדמי. הפתרון צריך להיות במסגרת של פונקציה: split_in_two(head) אשר מקבלת פרמטר head של הרשימה אותה רוצים לפצל ומחזירה את שני הראשים של הרשימות שנוצרו בעקבות הפיצול.

def split_in_two(head: Optional[Node]) -> Tuple[Optional[Node], Optional[Node]]:
    ....

• קלט: ראש הרשימה המקושרת שיכול להיות Node או None (במקרה של רשימה ריקה).
• פלט: טאפל של פייתון. המכיל שני heads - הראשון עבור הרשימה שמקורה בחציו הראשון של הרשימה המקורית, ושני שמקורו בחצי השני.

דוגמאות:

• קלט: רשימה מקושרת בעלת מספר אי זוגי של איברים:

  1 -> 2 -> 3 -> 4 -> 5

  פלט: 2 רשימות מקושרות:

  1 -> 2 -> 3, 4 -> 5

• קלט: רשימה מקושרת בעלת מספר זוגי של איברים:

  1 -> 2 -> 3 -> 4 

  פלט: 2 רשימות מקושרות:

  1 -> 2 , 3 -> 4

• קלט: רשימה מקושרת ריקה.

  פלט:

  None , None

• קלט: רשימה מקושרת בעלת איבר בודד: 1

  פלט:

  1 , None

פתרון לדוגמה:

def split_in_two(head):
    # Check if the linked list is empty or has only one node
    if not head or not head.next:
        return head, None
    
    # Initialize two pointers: fast and slow
    fast = head.next
    slow = head
    
    # Move the fast pointer twice as fast as the slow pointer
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    
    # Split the linked list into two halves
    # Head of the second half
    second_half_head = slow.next
    # Set the next of slow pointer to None to separate the halves
    slow.next = None
    # Head of the first half
    first_half_head = head
    
    # return tuple with the heads of the two lists
    return first_half_head, second_half_head

ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.insert_at_end(4)
ll.insert_at_end(5)

# Split the linked list into two halves
first_head, second_head = split_in_two(ll.head)

# Create a new linked list for the two halves
first_half_linked_list = LinkedList()
first_half_linked_list.head = first_head

second_half_linked_list = LinkedList()
second_half_linked_list.head = second_head

# Print the two halves
print(first_half_linked_list)
print(second_half_linked_list)

נסביר:

• הפונקציה split_in_two מקבלת head של רשימה מקושרת כקלט.
• קודם כל היא בודקת אם הרשימה המקושרת היא ריקה או שיש לה איבר אחד בלבד. אם זה המצב, היא תחזיר את ה- head של הרשימה בתור החלק הראשון ו-None בתור החלק השני.
• היא מיישמת דפוס שחייבים לדעת "אלגוריתם הצב והארנב" אשר משתמש בשני מצביעים slow ו-fast אותם היא מקדמת לאורך הרשימה. את המצביע fast מזיזים כפליים יותר מהר מאשר את המצביע slow וכך קורה כי כאשר fast מסיים לרוץ כי הוא הגיע לסוף הרשימה, slow נמצא באיבר האמצעי מה שהופך את האלגוריתם לשימושי ביותר כשרוצים לעשות משהו עם אמצע של רשימה.
• הפונקציה מפצלת את הרשימה באמצעות עדכון המצביע slow.next כך שיצביע על None.

אתגר 5: מיזוג שתי רשימות מקושרות

נתונות שתי רשימות מקושרות, l1 ו-l2 כל אחת מהם מסודרת בסדר עולה. עליך למזג את שתי הרשימות לרשימה מקושרת אחת ולהחזיר את ראשה של הרשימה הממוזגת. הרשימה צריכה להיות בסדר עולה.

עליך לכתוב פונקציה merge_lists כדי לפתור את האתגר:

def merge_lists(l1: Node, l2: Node) -> Node:
    ...

דוגמאות:

בהינתן 2 רשימות מקושרות:
l1: 1 -> 2 -> 6
l2: 1 -> 3 -> 4 -> 5

הפונקציה תחזיר רשימה ממוזגת: 1 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6

פתרון:

def merge_lists(l1, l2):
    # A new linked list to store the merged list
    merged = LinkedList()

    # Pointers to traverse the lists: l1 and l2
    current1 = l1.head
    current2 = l2.head

    # Merge the two lists in sorted order
    while current1 and current2:
        if current1.data <= current2.data:
            # If current1 data is smaller, insert it into the merged list
            merged.insert_at_end(current1.data)
            current1 = current1.next
        else:
            # If current2 data is smaller, insert it into the merged list
            merged.insert_at_end(current2.data)
            current2 = current2.next

    # Append the remaining nodes from either l1 or l2
    while current1:
        merged.insert_at_end(current1.data)
        current1 = current1.next
    while current2:
        merged.insert_at_end(current2.data)
        current2 = current2.next

    return merged


# Test case
l1 = LinkedList()
l1.insert_at_end(1)
l1.insert_at_end(2)
l1.insert_at_end(6)

l2 = LinkedList()
l2.insert_at_end(1)
l2.insert_at_end(3)
l2.insert_at_end(4)
l2.insert_at_end(5)

# Merge the two lists
merged_list = merge_lists(l1, l2)

# Print the merged list
print(merged_list)

נסביר:

• merged = LinkedList()

  יוצרים אובייקט חדש LinkedList שיאחסן את הרשימה הממוזגת.

• current1 = l1.head
  current2 = l2.head

  אתחול שני מצביעים current1 ו-current2 שיצביעו על ראשי הרשימות l1 ו-l2. מצביעים אילה יעברו באופן סדרתי traverse על שתי הרשימות.

• while current1 and current2:
      if current1.data <= current2.data:
          merged.insert_at_end(current1.data)
          current1 = current1.next
      else:
          merged.insert_at_end(current2.data)
          current2 = current2.next

  • נכנסים ללולאה שתמשיך לרוץ כל עוד current1 ו-current2 אינם None.
  • בתוך הלולאה משווים בין הערכים של current1 ו-current2.
    • אם הערך של current1 הוא נמוך או שווה ל-current2, מכניסים את האיבר עליו מצביע current1 לרשימה הממוזגת, ומזיזים את הסמן current1 לאיבר הבא בתור.
    • אחרת, מכניסים את הערך של current2 לרשימה הממוזגת

• # Append the remaining nodes from either l1 or l2
  while current1:
      merged.insert_at_end(current1.data)
      current1 = current1.next
  while current2:
      merged.insert_at_end(current2.data)
      current2 = current2.next

  אחרי שהלולאה מסיימת לרוץ יתכנו איברים נוספים שלא עברנו עליהם ב-l1 או l2, אז עוברים באופן סדרתי על האיברים הנותרים ומוסיפים את ערכם לרשימה merged.

לסיכום

רשימות מקושרות Linked lists הם מבנה נתונים שצריך להכיר בגלל שהוא מאפשר גמישות באחסון ובמניפולציה של מידע. בניגוד למערכים רשימות מקושרות מקצות זיכרון באופן דינמי לכל איבר בנפרד, מה שמאפשר הוספה ומחיקה של איברים ביעילות רבה. במדריך הסברנו את העקרונות של רשימות מקושרות, החל במבנה. כל איבר node מכיל מידע ומצביע לאיבר הבא. הקלאס LinkedList מכיל בתוכו את האופרציות החשובות ביותר לניהול רשימות מקושרות, כדוגמת: הוספה לסוף הרשימה, מעבר סדרתי ומחיקה.

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

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

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

big-O ביטוי ליעילות הקוד

יישום תורת הגרפים בפייתון - חלק א

מה זה data classes בפייתון ואיך להשתמש בזה

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים