רשימות מקושרות ב-Python

מבוא

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

יתרונות וחסרונות של רשימות מקושרות

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

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

יישום רשימות מקושרות ב-Python

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

רשימה מקושרת יחידה

רשימה מקושרת יחידה מורכבת מצמתים שבהם כל צומת מכיל ערך והפניה לצומת הבא ברצף. כך תוכל ליצור רשימה מקושרת יחידה ב-Python:

class Node: def __init__(self, value): self.value = value self.next = None class Linked List: def __init__(self): self.head = None

יצירת רשימה מקושרת יחידה

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

הוספת צמתים ברשימה מקושרת בודדת

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

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

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

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

def delete_node(self, value): current = self.head if current.value == value: self.head = current.next else: while current.next: if current.next.value == value: current.next = current.next.next break current = current.next

חיפוש ברשימה מקושרת בודדת

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

def search(self, value): current = self.head while current: if current.value == value: return True current = current.next return False

היפוך רשימה מקושרת יחידה

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

def reverse(self): previous = None current = self.head while current: next_node = current.next current.next = previous previous = current current = next_node self.head = previous

רשימה מקושרת כפולה

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

class Node: def __init__(self, value): self.value = value self.next = None self.previous = None class DoublyLinked List: def __init__(self): self.head = None

יצירת רשימה מקושרת כפולה

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

הוספת צמתים ברשימה כפולה מקושרת

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

def insert_at_beginning(self, value): new_node = Node(value) if self.head: self.head.previous = new_node new_node.next = self.head self.head = new_node

מחיקת צמתים מרשימה מקושרת כפולה

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

def delete_node(self, value): current = self.head if current.value == value: self.head = current.next if self.head: self.head.previous = None else: while current.next: if current.next.value == value: current.next = current.next.next if current.next: current.next.previous = current break current = current.next

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

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

def search(self, value): current = self.head while current: if current.value == value: return True current = current.next return False

היפוך רשימה מקושרת כפולה

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

def reverse(self): current = self.head while current: next_node = current.next current.next = current.previous current.previous = next_node if not next_node: self.head = current current = next_node

רשימה מקושרת מעגלית

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

class Node: def __init__(self, value): self.value = value self.next = None class CircularLinked List: def __init__(self): self.head = None

יצירת רשימה מעגלית מקושרת

כדי ליצור רשימה מקושרת מעגלית, אנו מגדירים מחלקת Node שמכילה ערך והפניה לצומת הבא. המחלקה CircularLinked List משמשת כמיכל עבור הצמתים, כאשר תכונת head מצביעה על הצומת הראשון ברשימה. בנוסף, ההתייחסות הבאה של הצומת האחרונה מוגדרת לראש, ויוצרת מבנה מעגלי.

הוספת צמתים ברשימה מקושרת מעגלית

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

def insert_at_beginning(self, value): new_node = Node(value) if not self.head: self.head = new_node new_node.next = self.head else: current = self.head while current.next != self.head: current = current.next current.next = new_node new_node.next = self.head self.head = new_node 

מחיקת צמתים מרשימה מקושרת מעגלית

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

def delete_node(self, value): if not self.head: return current = self.head if current.value == value: while current.next != self.head: current = current.next if current == self.head: self.head = None else: current.next = self.head.next self.head = self.head.next else: previous = None while current.next != self.head: previous = current current = current.next if current.value == value: previous.next = current.next break

חיפוש ברשימה מקושרת מעגלית

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

def search(self, value): if not self.head: return False current = self.head while True: if current.value == value: return True current = current.next if current == self.head: break return False

היפוך רשימה מקושרת מעגלית

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

def reverse(self): if not self.head: return previous = None current = self.head next_node = current.next while True: current.next = previous previous = current current = next_node next_node = next_node.next if current == self.head: break self.head = previous

פעולות נפוצות ברשימות מקושרות

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

גישה לאלמנטים ברשימה מקושרת

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

def get_element(self, index): current = self.head count = 0 while current: if count == index: return current.value count += 1 current = current.next raise IndexError("Index out of range")

שינוי אלמנטים ברשימה מקושרת

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

def modify_element(self, index, new_value): current = self.head count = 0 while current: if count == index: current.value = new_value return count += 1 current = current.next raise IndexError("Index out of range")

מציאת אורכה של רשימה מקושרת

כדי למצוא את אורכה של רשימה מקושרת, נוכל לחצות את הרשימה ולספור את מספר הצמתים. הנה דוגמה למציאת האורך של רשימה מקושרת:

def get_length(self): current = self.head count = 0 while current: count += 1 current = current.next return count

בודק אם רשימה מקושרת ריקה

כדי לבדוק אם רשימה מקושרת ריקה, אנחנו יכולים פשוט לבדוק אם צומת הראש הוא None. הנה דוגמה לבדיקה אם רשימה מקושרת ריקה:

def is_empty(self): return self.head is None

שרשור רשימות מקושרות

כדי לשרשר שתי רשימות מקושרות, נוכל לעבור ברשימה הראשונה כדי למצוא את הצומת האחרון ולעדכן את ההתייחסות הבאה שלו לראש הרשימה השנייה. הנה דוגמה לשרשרת שתי רשימות מקושרות:

def concatenate(self, other_list): if not self.head: self.head = other_list.head else: current = self.head while current.next: current = current.next current.next = other_list.head

רשימה מקושרת לעומת מערך

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

יעילות זיכרון

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

יעילות הכנסה ומחיקה

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

יעילות גישה אקראית

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

בחירת מבנה הנתונים הנכון

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

יישומי רשימה מקושרת

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

אתה יכול גם להירשם אלינו קורסים חינם היום!

יישום ערימות ותורים

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

מחסנית היא מבנה נתונים העוקב אחר עקרון ה-Last-In-First-Out (LIFO). אלמנטים מתווספים ומוסרים מאותו קצה, המכונה החלק העליון של הערימה. רשימות מקושרות מספקות דרך יעילה ליישם ערימות מכיוון שאנו יכולים בקלות להוסיף או להסיר אלמנטים מראש הרשימה.

הנה דוגמה ליישום מחסנית באמצעות רשימה מקושרת ב-Python:

class Node: def __init__(self, data): self.data = data self.next = None class Stack: def __init__(self): self.head = None def push(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node def pop(self): if self.head is None: return None popped = self.head.data self.head = self.head.next return popped

תור, לעומת זאת, עוקב אחר עקרון First-In-First-Out (FIFO). אלמנטים מתווספים בקצה אחד, הידוע כחלק האחורי, ומוסרים מהקצה השני, המכונה הקדמי. ניתן להשתמש ברשימות מקושרות גם כדי ליישם תורים ביעילות.

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

class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.front = None self.rear = None def enqueue(self, data): new_node = Node(data) if self.rear is None: self.front = new_node self.rear = new_node else: self.rear.next = new_node self.rear = new_node def dequeue(self): if self.front is None: return None dequeued = self.front.data self.front = self.front.next if self.front is None: self.rear = None return dequeued

טיפול במערכי נתונים גדולים

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

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

אלגוריתמי מעבר גרפים

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

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

ייצוג פולינומי

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

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

רשימות השמעה של מוזיקה ווידאו

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

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

סיכום

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

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

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

אתה יכול גם לקרוא מאמרים נוספים הקשורים לרשימות Python כאן:

שאלות נפוצות

מוצרים מקושרים

• הפצת תוכן ויחסי ציבור מופעל על ידי SEO. קבל הגברה היום.
• PlatoData.Network Vertical Generative Ai. העצים את עצמך. גישה כאן.
• PlatoAiStream. Web3 Intelligence. הידע מוגבר. גישה כאן.
• PlatoESG. פחמן, קלינטק, אנרגיה, סביבה, שמש, ניהול פסולת. גישה כאן.
• PlatoHealth. מודיעין ביוטכנולוגיה וניסויים קליניים. גישה כאן.
• מקור: https://www.analyticsvidhya.com/blog/2024/02/linked-lists-in-python/