لیست های پیوندی با جزئیات با مثال های پایتون: لیست های پیوندی منفرد

معرفی

لیست های پیوندی یکی از متداول ترین ساختارهای داده ای هستند که در هر زبان برنامه نویسی از آنجایی که ارائه می دهند استفاده می شود تخصیص حافظه پویا که آرایه ها اغلب به سادگی نمی توانند ارائه کنند.

یک لیست پیوندی در پایتون را می توان به عنوان زنجیره ای از گره ها در نظر گرفت که هر کدام در آن قرار دارند node شامل یک عنصر داده و یک مرجع به بعدی است node در دنباله این ساختار اجازه می دهد درج و حذف کارآمد، زیرا به جای جابجایی چندین عنصر مانند یک آرایه، فقط باید تعداد انگشت شماری از مراجع را به روز کرد. با این وجود، عملکرد دسترسی مستقیم لیست های پیوندی در مقایسه با آرایه ها کندتر است.

در این مقاله لیست های لینک شده را به طور مفصل مطالعه خواهیم کرد. ما خواهیم دید که انواع مختلف لیست های پیوندی چیست، چگونه می توان از یک لیست پیوندی عبور کرد، چگونه عناصر را از لیست پیوندی درج کرد و حذف کرد، تکنیک های مختلف برای مرتب سازی لیست پیوندی چیست، چگونه یک لیست پیوندی را معکوس کرد، و غیره روی.

لیست پیوندی چیست؟

قبل از اینکه لیست‌های پیوندی را مطالعه کنیم، ابتدا به طور خلاصه روش ذخیره داده‌ها توسط آرایه‌ها را مرور می‌کنیم. در آرایه ها، داده ها در ذخیره می شوند مکان های حافظه پیوسته. به عنوان مثال، اگر اولین مورد در آرایه در شاخص 10 حافظه ذخیره شود و اندازه آن 15 بایت باشد، آیتم دوم در فهرست ذخیره می شود. 10+15+1 – شاخص 26. بنابراین، عبور از یک آرایه ساده است.

برای یافتن مورد سوم در یک آرایه، می‌توانید به سادگی از شاخص شروع اولین مورد، به اضافه اندازه مورد اول، به علاوه اندازه مورد دوم، به اضافه 1 استفاده کنید.

چگونه لیست های پیوندی داده ها را ذخیره می کنند

لیست های پیوندی، روی از سوی دیگر، متفاوت هستند. لیست های پیوندی، انجام ندهید ذخیره داده ها در مکان های حافظه پیوسته برای هر مورد در محل حافظه، لیست پیوندی مقدار مورد و مرجع (یا اشاره گر) مورد بعدی را ذخیره می کند. یک جفت از آیتم لیست پیوند شده و ارجاع به مورد بعدی عبارتند از a node.

به عنوان مثال، اگر الف node شامل 34|10، به این معنی است که ارزش node است 30، در حالی که مورد بعدی در محل حافظه ذخیره می شود "10". برای عبور از یک لیست پیوندی، فقط باید محل حافظه یا مرجع اولین را بدانید node، بقیه گره ها را می توان به صورت متوالی با استفاده از ارجاع به عنصر بعدی در هر یک پیمایش کرد node.

اشاره به اولی node به عنوان شروع نیز شناخته می شود node.

لیست های پیوندی در مقابل آرایه ها

یک لیست پیوندی یک است ساختار داده پویا به این معنی که حافظه رزرو شده برای لیست پیوندها را می توان در زمان اجرا افزایش یا کاهش داد. هیچ حافظه ای برای ساختار داده لیست پیوندی از قبل اختصاص داده نشده است. هر زمان که یک آیتم جدید لازم باشد به لیست پیوندی اضافه شود، حافظه مورد جدید node در زمان اجرا ایجاد می شود. از سوی دیگر، در مورد آرایه، حافظه باید از قبل برای تعداد خاصی از آیتم ها تخصیص داده شود. در مواردی که آیتم های کافی برای پر کردن همه فهرست های آرایه در دسترس نباشد، فضای حافظه تلف می شود.

از آنجایی که آرایه‌ها به مکان‌های حافظه پیوسته نیاز دارند، حذف یا درج یک آیتم در یک آرایه بسیار دشوار است، زیرا مکان‌های حافظه تعداد زیادی از آیتم‌ها باید به روز شوند. از سوی دیگر، لیست پیوندی موارد در یک مکان حافظه پیوسته ذخیره نمی شوند، بنابراین می توانید به راحتی لیست های پیوند شده را به روز کنید.

با توجه به آن انعطاف پذیری، یک لیست پیوندی برای پیاده سازی ساختارهای داده مانند پشته ها، صف ها و لیست ها مناسب تر است.

با این حال، برخی وجود دارد نکات منفی لیست پیوندی همچنین:

• از آنجایی که هر مورد لیست پیوند شده باید مرجع مورد بعدی را ذخیره کند، مقداری حافظه اضافی مورد نیاز است.
• برخلاف آرایه‌ها که می‌توانید مستقیماً به یک آیتم دسترسی داشته باشید، نمی‌توانید مستقیماً به یک آیتم لیست پیوندی دسترسی داشته باشید زیرا تنها اطلاعاتی که در اختیار دارید مرجع اولین مورد است. در اصطلاح Big O، بدترین زمان دسترسی O(n) است.

در این مقاله به تمرکز خواهیم پرداخت روی آ لیست پیوندی واحد و عملیات مختلف آن

لیست پیوندی واحد

یک لیست پیوندی منفرد ساده ترین از همه انواع لیست های پیوندی است. هر node در یک لیست پیوندی واحد شامل یک مورد و ارجاع به مورد بعدی و بس در این قسمت روش ایجاد a را خواهیم دید node برای لیست پیوندی واحد همراه با روش‌های انواع مختلف درج، پیمایش و حذف.

ایجاد کلاس Node

اولین کاری که باید انجام دهید این است که یک کلاس برای گره ها ایجاد کنید. اشیاء این کلاس گره های واقعی خواهند بود که در لیست پیوندی خود قرار می دهیم. می دانیم که الف node برای یک لیست پیوندی واحد حاوی آیتم و ارجاع به مورد بعدی است node. بنابراین، ما node کلاس شامل دو متغیر عضو خواهد بود item و ref. ارزش از item با مقدار ارسال شده از سازنده تنظیم می شود، در حالی که مرجع در ابتدا به تنظیم می شود None:

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

ایجاد کلاس Single Linked List

بعد، باید یک کلاس برای لیست پیوند شده ایجاد کنیم. این کلاس حاوی متدهایی برای درج، حذف، پیمایش و مرتب‌سازی لیست است. در ابتدا، کلاس فقط شامل یک عضو خواهد بود start_node که به شروع یا اول اشاره می کند node از لیست ارزش start_node تنظیم خواهد شد None با استفاده از سازنده، زیرا لیست پیوندی در زمان ایجاد خالی خواهد بود:

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

اکنون یک کلاس برای لیست واحد خود ایجاد کرده ایم. مرحله بعدی اضافه کردن یک روش درج برای درج موارد در لیست پیوند شده است. اما قبل از آن، روشی برای پیمایش یک لیست پیوندی اضافه می کنیم. این روش به ما کمک می کند تا داده های لیست خود را بخوانیم.

عبور از آیتم های لیست پیوند شده

برای اینکه ما بتوانیم روی لیست پیوندی خود تکرار کنیم، باید روش زیر را به آن اضافه کنیم LinkedList کلاسی که در بخش آخر ایجاد کردیم:

def traverse_list(self):
    if self.start_node is None:
        print("List has no element")
        return
    else:
        n = self.start_node
        while n is not None:
            print(n.item , " ")
            n = n.ref

بیایید ببینیم در روش فوق چه اتفاقی می افتد. روش دارد دو بخش اصلی. ابتدا، خالی بودن یا نبودن لیست پیوند شده را بررسی می کند:

  if self.start_node is None:
        print("List has no element")
        return

اگر لیست پیوندی خالی باشد، به این معنی است که هیچ موردی برای تکرار وجود ندارد. در چنین مواردی، traverse_list() متد به سادگی این عبارت را چاپ می کند که لیست هیچ موردی ندارد. در غیر این صورت، اگر لیست دارای آیتم باشد، کد زیر اجرا می شود:

    n = self.start_node
        while n is not None:
            print(n.item , " ")
            n = n.ref

همانطور که قبلاً گفتیم، start متغیر شامل ارجاع به اولین گره ها خواهد بود. بنابراین، یک متغیر را مقداردهی اولیه می کنیم n با start متغیر. در مرحله بعد یک حلقه را اجرا می کنیم که تا اجرا می شود n هیچ می شود. در داخل حلقه، ما print مورد ذخیره شده در جریان فعلی node و سپس مقدار را تعیین کنید n متغیر به n.ref، که حاوی ارجاع به بعد است node. مرجع آخرین node است None از آنجایی که وجود ندارد node بعد از آن. بنابراین، زمانی که n تبدیل می شود None، حلقه خاتمه می یابد.

اکنون که روشی برای پیمایش یک لیست پیوندی داریم، بیایید ببینیم چگونه می توانیم موارد را به یک لیست پیوندی اضافه کنیم.

درج موارد

بسته به مکانی که می خواهید یک مورد را در آن درج کنید، روش های مختلفی برای درج موارد در یک لیست پیوندی وجود دارد.

درج موارد در ابتدا

ساده ترین راه برای درج یک مورد در یک لیست پیوندی، افزودن یک آیتم است در ابتدای لیست. بیایید ببینیم چگونه یک مورد را در ابتدای لیست درج کنیم. این روش را به LinkedList کلاسی که قبلا ایجاد کردیم:

    def insert_at_start(self, data):
        new_node = Node(data)
        new_node.ref = self.start_node
        self.start_node= new_node

در اسکریپت بالا یک متد ایجاد می کنیم insert_at_start()، متد یک پارامتر را می پذیرد که اساساً مقدار موردی است که می خواهیم درج کنیم. در داخل متد، ما به سادگی یک شی از the ایجاد می کنیم Node کلاس و مرجع آن را به start_node از آنجا که start_node قبلاً اولین مورد را ذخیره می کرد node، که پس از درج یک جدید node در ابتدا تبدیل به دوم خواهد شد node.

بنابراین، مرجع را اضافه می کنیم start_node به ref متغیر جدید node. در حال حاضر از زمان new_node اولین است node، مقدار the را تنظیم می کنیم start_node متغیر به new_node.

درج موارد در انتها

حالا بیایید یک روش ایجاد کنیم insert_at_end()، که عنصر را وارد می کند در پایان از لیست پیوندی:

  def insert_at_end(self, data):
        new_node = Node(data)
        if self.start_node is None:
            self.start_node = new_node
            return
        n = self.start_node
        while n.ref is not None:
            n= n.ref
        n.ref = new_node;

مقدار موردی که می خواهیم درج کنیم به عنوان آرگومان به متد ارسال می شود. روش شامل دو بخش است. ابتدا بررسی می کنیم که لیست پیوندی خالی است یا خیر، اگر لیست پیوندی خالی است، تنها کاری که باید انجام دهیم این است که مقدار آن را تنظیم کنیم. start_node متغیر به new_node هدف – شی.

از طرف دیگر، اگر لیست قبلاً شامل تعدادی گره باشد. یک متغیر را مقداردهی اولیه می کنیم n با شروع node. سپس در تمام گره های لیست با استفاده از a تکرار می کنیم while حلقه همانطور که در مورد the انجام دادیم traverse_list روش. وقتی به آخرین حلقه رسیدیم، حلقه خاتمه می یابد node. سپس مرجع آخرین را تنظیم می کنیم node به تازه ایجاد شده new_node.

درج یک مورد پس از یک مورد دیگر

ممکن است لازم باشد یک مورد را پس از یک مورد دیگر در یک لیست پیوندی واحد اضافه کنیم. برای انجام این کار، ما آن را ایجاد می کنیم insert_after_item() روش:

    def insert_after_item(self, x, data):

        n = self.start_node
        print(n.ref)
        while n is not None:
            if n.item == x:
                break
            n = n.ref
        if n is None:
            print("item not in the list")
        else:
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

این insert_after_item() روش دو پارامتر را می پذیرد: x و data. اولین پارامتر آیتمی است که پس از آن می خواهید مورد جدید را وارد کنید node در حالی که پارامتر دوم حاوی مقدار جدید است node.

ما با ایجاد یک متغیر جدید شروع می کنیم n و اختصاص الف start_node متغیر برای آن در مرحله بعد، با استفاده از a از لیست پیوند داده شده عبور می کنیم while حلقه این while حلقه اجرا می شود تا زمانی که n تبدیل می شود None. در طول هر تکرار، بررسی می کنیم که آیا مقدار در جریان ذخیره شده است یا خیر node برابر است با مقدار ارسال شده توسط x پارامتر. اگر مقایسه درست باشد، حلقه را می شکنیم.

بعد، اگر مورد پیدا شد، n متغیر نخواهد بود None. مرجع از new_node تنظیم شده است به مرجع ذخیره شده توسط n و مرجع از n تنظیم شده است new_node. اضافه کردن insert_after_item() روش به LinkesList کلاس

درج یک مورد قبل از یک مورد دیگر

حال، بیایید ایجاد کنیم insert_before_item() روشی که یک مورد را قبل از یک مورد دیگر در یک لیست پیوندی درج می کند:

    def insert_before_item(self, x, data):
        if self.start_node is None:
            print("List has no element")
            return

        if x == self.start_node.item:
            new_node = Node(data)
            new_node.ref = self.start_node
            self.start_node = new_node
            return

        n = self.start_node
        print(n.ref)
        while n.ref is not None:
            if n.ref.item == x:
                break
            n = n.ref
        if n.ref is None:
            print("item not in the list")
        else:
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

روش دارای سه بخش است. بیایید هر قسمت را با جزئیات بررسی کنیم:

     if self.start_node is None:
        print("List has no element")
        return

در اسکریپت بالا، بررسی می کنیم که آیا لیست خالی است. اگر واقعا خالی است، ما به سادگی print که لیست هیچ عنصر و بازگشتی از متد ندارد.

بعد، بررسی می کنیم که آیا عنصر در اولین شاخص قرار دارد یا خیر:

     if x == self.start_node.item:
        new_node = Node(data)
        new_node.ref = self.start_node
        self.start_node = new_node
        return

اگر عنصری که بعد از آن می خواهیم یک جدید درج کنیم node در اولین شاخص قرار دارد. ما به سادگی مرجع درج شده جدید را تنظیم می کنیم node به start_node و سپس مقدار را تعیین کنید start_node به new_node.

در نهایت، اگر لیست نیست None و عنصر در اولین شاخص یافت نمی شود، یک متغیر جدید ایجاد می کنیم n و الف را اختصاص دهید start_node متغیر برای آن در مرحله بعد، با استفاده از a از لیست پیوند داده شده عبور می کنیم while حلقه اجرا می شود تا زمانی که n.ref تبدیل می شود None. در طول هر تکرار، بررسی می کنیم که آیا مقدار در مرجع جریان ذخیره شده است یا خیر node برابر است با مقدار ارسال شده توسط x پارامتر. اگر مقایسه برگردد True، حلقه را می شکنیم.

بعد، اگر مورد پیدا شد، n.ref متغیر نخواهد بود None. مرجع از new_node به مرجع تنظیم شده است n و مرجع از n روی “new_node” تنظیم شده است:

    if n.ref is None:
        print("item not in the list")
    else:
        new_node = Node(data)
        new_node.ref = n.ref
        n.ref = new_node

درج یک مورد در فهرست خاص

گاهی اوقات، ما نیاز داریم که یک مورد را در یک شاخص خاص درج کنیم. بیایید روشی را تعریف کنیم که به ما در دستیابی به آن کمک می کند:

    def insert_at_index (self, index, data):
        if index == 1:
            new_node = Node(data)
            new_node.ref = self.start_node
            self.start_node = new_node
        i = 1
        n = self.start_node
        while i < index-1 and n is not None:
            n = n.ref
            i = i+1
        if n is None:
            print("Index out of bound")
        else: 
            new_node = Node(data)
            new_node.ref = n.ref
            n.ref = new_node

ابتدا بررسی می کنیم که آیا فهرستی که می خواهیم مورد را در آن ذخیره کنیم، وجود دارد یا خیر 1، سپس به سادگی اختصاص دهید start_node به مرجع از new_node و سپس مقدار را تعیین کنید start_node به new_node.

سپس یک حلقه while اجرا کنید که تا شمارنده اجرا می شود i بزرگتر یا مساوی می شود index-1. به عنوان مثال، اگر می خواهید یک مورد جدید اضافه کنید node به شاخص سوم در طول اولین تکرار حلقه while، i خواهد شد 2 و در حال حاضر تکرار شده است node خواهد بود 2. از آن زمان حلقه دوباره اجرا نخواهد شد i اکنون است 2 که برابر با شاخص است 1 (3-1=2). بنابراین، حلقه شکسته خواهد شد. در مرحله بعد یک مورد جدید اضافه می کنیم node پس از تکرار فعلی node (که هست node 2)، از این رو جدید node در شاخص اضافه می شود.

روش‌های درج تست

اکنون همه روش های درج خود را تعریف کرده ایم، بیایید آنها را آزمایش کنیم. ابتدا یک شی از کلاس لیست پیوندی ایجاد کنید:

new_linked_list = LinkedList()

بعد، اجازه دهید ابتدا با آن تماس بگیریم insert_at_end() روش اضافه کردن سه عنصر به لیست پیوندی:

new_linked_list.insert_at_end(5)
new_linked_list.insert_at_end(10)
new_linked_list.insert_at_end(15)

برای اینکه ببینیم آیا موارد واقعاً درج شده‌اند یا نه، بیایید با استفاده از روش تراورس از لیست پیوندی عبور کنیم:

new_linked_list.traverse_list()

شما باید خروجی زیر را ببینید:

5
10
15

در مرحله بعد، بیایید در ابتدا یک عنصر اضافه کنیم:

new_linked_list.insert_at_start(20)

حال، اگر لیست را طی کنید، باید خروجی زیر را ببینید:

20
5
10
15

بیایید یک مورد جدید اضافه کنیم 17 بعد از مورد 10:

new_linked_list.insert_after_item(10, 17)

عبور از لیست خروجی زیر را اکنون برمی گرداند:

20
5
10
17
15 

میتوانی ببینی 17 بعد درج شده است 10.

حالا بیایید یک مورد دیگر را وارد کنیم 25 قبل از مورد 17 با استفاده از insert_before_item() روش:

new_linked_list.insert_before_item(17, 25)

اکنون لیست حاوی عناصر زیر خواهد بود:

20
5
10
25
17
15

در نهایت، اجازه دهید یک عنصر اضافه کنیم در مکان سوم، که در حال حاضر توسط 10. آن را خواهید دید 10 یک مکان را به جلو می برد و مورد جدید در جای خود درج می شود. این insert_at_index() برای این منظور می توان از روش استفاده کرد. اسکریپت زیر مورد را درج می کند 8 در نمایه سومین نمایه لیست:

new_linked_list.insert_at_index(3,8)

حالا اگر از لیست عبور کنید، باید خروجی زیر را ببینید:

20
5
8
10
25
17
15

و با آن، ما تمام روش های درج خود را آزمایش کرده ایم. ما در حال حاضر 7 عنصر در لیست خود داریم. بیایید روشی بنویسیم که تعداد عناصر موجود در یک لیست پیوندی را برمی گرداند.

شمارش عناصر

حال، بیایید یک را ایجاد کنیم get_count() روشی که تعداد عناصر موجود در لیست پیوندی را می شمارد. این روش به سادگی از تمام گره های آرایه عبور می کند و یک شمارنده را با استفاده از a افزایش می دهد while حلقه در انتهای حلقه، شمارنده شامل تعداد کل عناصر در حلقه است:

    def get_count(self):
        if self.start_node is None:
            return 0;
        n = self.start_node
        count = 0;
        while n is not None:
            count = count + 1
            n = n.ref
        return count

روش بالا را به LinkedList کلاس، کامپایل LinkedList کلاس، و سپس برخی از عناصر را در آن وارد کنید LinkedList همانطور که در بخش گذشته انجام دادیم. ما تا پایان آخرین بخش، 7 مورد در لیست پیوندی خود داشتیم.

بیایید استفاده کنیم get_count() روش برای به دست آوردن تعداد کل موارد در لیست:

new_linked_list.get_count()

شما باید تعداد موارد موجود در لیست پیوندی خود را در خروجی ببینید.

روش دیگر برای به دست آوردن «شمار» لیست، ردیابی تعداد موارد درج شده و حذف شده از لیست در یک متغیر شمارنده ساده متعلق به LinkedList کلاس این به خوبی کار می کند و سریعتر از آن است get_count اگر ساختار داده لیست زیربنایی را نتوان از خارج از کلاس دستکاری کرد.

جستجوی عناصر

جستجوی یک عنصر کاملاً شبیه به شمارش یا عبور از یک لیست پیوندی است، تنها کاری که باید انجام دهید این است که مقدار مورد جستجو را با مقدار آن مقایسه کنید. node در طول هر تکرار اگر مقدار پیدا شد، print که مقدار پیدا شود و حلقه را بشکنید. اگر بعد از عبور از تمام گره ها عنصر پیدا نشد، به سادگی print که عنصر پیدا نشد:

    def search_item(self, x):
        if self.start_node is None:
            print("List has no elements")
            return
        n = self.start_node
        while n is not None:
            if n.item == x:
                print("Item found")
                return True
            n = n.ref
        print("item not found")
        return False

روش بالا را به LinkedList کلاس بیایید یک عنصر را در لیست ایجاد شده قبلی جستجو کنیم:

new_linked_list.search_item(5)

از آنجایی که ما 5 را در لیست پیوندی خود درج کردیم، روش بالا باز خواهد گشت True:

Item found
True

روشی برای ایجاد لیست پیوندی

اگرچه می‌توانیم موارد را یکی یکی با استفاده از هر یک از روش‌های درج اضافه کنیم. بیایید روشی ایجاد کنیم که از کاربر بخواهد تعداد عناصر را وارد کند node و سپس عنصر فردی را وارد می کند و آن عنصر را در لیست پیوند شده وارد می کند:

    def make_new_list(self):
        nums = int(input("How many nodes do you want to create: "))
        if nums == 0:
            return
        for i in range(nums):
            value = int(input("Enter the value for the node:"))
            self.insert_at_end(value)

این make_new_list() روش ابتدا از کاربر تعداد موارد موجود در لیست را می پرسد. بعد با استفاده از a for حلقه، از کاربر خواسته می شود که مقدار هر یک را وارد کند node، که سپس با استفاده از insert_at_end() روش.

تصویر زیر نشان می دهد make_new_list() روش در عمل

حذف عناصر

در این بخش، روش های مختلف حذف یک عنصر از یک لیست پیوندی را مشاهده خواهیم کرد.

حذف از شروع

حذف یک عنصر یا آیتم از ابتدا لیست پیوندی ساده است. ما باید مرجع را تنظیم کنیم start_node به دومی node که می توانیم به سادگی با اختصاص مقدار مرجع شروع انجام دهیم node (که به دومی اشاره دارد node) تا شروع node:

    def delete_at_start(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        self.start_node = self.start_node.ref

ابتدا بررسی می کنیم که آیا لیست خالی است یا خیر. اگر لیست خالی باشد، این پیام را نشان می دهیم که لیست هیچ عنصری برای حذف ندارد. در غیر این صورت، مقدار the را اختصاص می دهیم start_node.ref به start_node. این start_node اکنون به عنصر دوم اشاره خواهد کرد.

حذف در پایان

برای حذف یک عنصر از انتهای لیست، به سادگی باید از طریق لیست پیوندی تا آخرین عنصر تکرار کنیم و سپس باید مرجع دومین عنصر آخر را تنظیم کنیم. None، که دومین عنصر آخر را به آخرین عنصر تبدیل می کند:

    def delete_at_end(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return

        n = self.start_node
        while n.ref.ref is not None:
            n = n.ref
        n.ref = None

حذف بر اساس مقدار مورد

برای حذف عنصر بر اساس مقدار، ابتدا باید آن را پیدا کنیم node که حاوی آیتم با مقدار مشخص شده است و سپس آن را حذف کنید node. یافتن آیتم با مقدار مشخص شده بسیار شبیه به جستجوی مورد است. هنگامی که موردی که باید حذف شود پیدا شد، مرجع node قبل از اینکه مورد روی مقدار تنظیم شود node که پس از حذف آیتم وجود دارد:

  def delete_element_by_value(self, x):
    if self.start_node is None:
        print("The list has no element to delete")
        return

    
    if self.start_node.item == x:
        self.start_node = self.start_node.ref
        return

    n = self.start_node
    while n.ref is not None:
        if n.ref.item == x:
            break
        n = n.ref

    if n.ref is None:
        print("item not found in the list")
    else:
        n.ref = n.ref.ref

طبق معمول، ابتدا بررسی می کنیم که آیا لیست خالی است یا خیر. بعد، بررسی می کنیم که آیا عنصری که باید حذف شود در ابتدای لیست پیوند شده قرار دارد یا خیر. اگر عنصر در ابتدا پیدا شد، با تنظیم اول آن را حذف می کنیم node به مرجع اولی node (که اساساً به دومی اشاره دارد node).

در نهایت، اگر عنصر در اولین فهرست یافت نشد، از طریق لیست پیوندی تکرار می کنیم و بررسی می کنیم که آیا مقدار node تکرار شدن برابر با مقداری است که باید حذف شود. اگر مقایسه برگردد True، مرجع قبلی را تنظیم می کنیم node به node که بعد از وجود دارد node که در حال حذف شدن است

تست روش های حذف

بیایید روش های حذفی را که به تازگی ایجاد کرده ایم آزمایش کنیم. اما قبل از آن مقداری داده ساختگی را به لیست پیوندی خود اضافه کنید:

new_linked_list.insert_at_end(10)
new_linked_list.insert_at_end(20)
new_linked_list.insert_at_end(30)
new_linked_list.insert_at_end(40)
new_linked_list.insert_at_end(50)

اسکریپت فوق 5 عنصر را در یک لیست پیوندی درج می کند. اگر از لیست عبور کنید، باید موارد زیر را مشاهده کنید:

10
20
30
40
50

بیایید ابتدا یک مورد را از ابتدا حذف کنیم:

new_linked_list.delete_at_start()

حالا اگر از لیست عبور کنید، باید خروجی زیر را ببینید:

20
30
40
50 

حالا بیایید یک عنصر را از آخر حذف کنیم:

new_linked_list.delete_at_end()

اکنون لیست شامل موارد زیر است:

20
30
40

در نهایت، بیایید یک عنصر را بر اساس مقدار، مثلاً حذف کنیم 30.

new_linked_list.delete_element_by_value(30)

حالا اگر از لیست عبور کنید، نباید موردی را ببینید 30.

معکوس کردن یک لیست پیوندی

برای معکوس کردن یک لیست پیوندی، باید سه متغیر داشته باشید: prev، n، و next. این prev قبلی را پیگیری خواهد کرد node، next موارد بعدی را پیگیری خواهد کرد node، و n با جریان مطابقت خواهد داشت node.

ما شروع می کنیم a while حلقه با اختصاص شروع node به متغیر n و prev متغیر به مقدار دهی اولیه می شود None. حلقه تا زمانی اجرا می شود n تبدیل می شود None. درون while حلقه، باید موارد زیر را انجام دهید:

• مقدار مرجع جریان را تعیین کنید node به next
• مقدار مرجع جریان را تنظیم کنید node n به prev
• تنظیم prevمتغیر به جریان node n
• تنظیم جریان node n به ارزش next node

در انتهای حلقه، prev متغیر به آخرین مورد اشاره خواهد کرد node، باید اول آن را بسازیم node بنابراین ما مقدار را تعیین می کنیم self.start_node متغیر به prev. این while حلقه هر کدام را می سازد node به قبلی اش اشاره کند node، که منجر به یک لیست پیوندی معکوس می شود:

    def reverse_linkedlist(self):
        prev = None
        n = self.start_node
        while n is not None:
            next = n.ref
            n.ref = prev
            prev = n
            n = next
        self.start_node = prev

روش بالا را به LinkedList کلاس یک لیست پیوندی از اعداد تصادفی ایجاد کنید و سپس ببینید که آیا می توانید آن را با استفاده از آن برگردانید reverse_linkedlist() روش.

نتیجه

در این مقاله، بحث خود را در مورد یک لیست پیوندی واحد آغاز کردیم. ما دیدیم که چه روش های مختلفی را می توان انجام داد روی لیست پیوندی مانند عبور از یک لیست پیوندی، درج موارد در یک لیست پیوندی، جستجو و شمارش موارد لیست پیوندی، حذف موارد از یک لیست پیوندی، و معکوس کردن یک لیست پیوندی واحد.

این قسمت 1 از سری مقالات است روی لیست پیوندی در قسمت بعدی روش مرتب سازی یک لیست پیوندی، روش ادغام لیست های پیوندی مرتب شده و روش حذف چرخه ها از یک لیست پیوندی را خواهیم دید.