لیست پیوند دوگانه با مثال های پایتون

معرفی

این سومین مقاله از مجموعه مقالات است روی پیاده سازی لیست های پیوندی با پایتون در قسمت 1 و قسمت 2 این مجموعه، لیست پیوندی تکی را به طور مفصل مطالعه کردیم.

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

در یک لیست پیوندی واحد، هر یک node از لیست دارای دو جزء، ارزش واقعی از node و اشاره به بعد node در لیست پیوند شده در لیست دوگانه پیوند خورده، هر یک node دارای سه جزء است: مقدار node، اشاره به قبلی node، و اشاره به بعد node. برای شروع node از لیست پیوند دوگانه، ارجاع به قبلی node پوچ است (None در پایتون). به طور مشابه، برای آخرین node در فهرست پیوندی مضاعف، ارجاع به بعدی node پوچ است.

مزایا و معایب لیست پیوندی دوگانه

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

طرفداران

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

منفی

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

پیاده سازی لیست پیوند دوگانه با پایتون

در این بخش خواهیم دید که چگونه می توانیم یک لیست بسیار ساده با پیوند دوگانه در پایتون ایجاد کنیم. اگر قسمت 1 و قسمت 2 این سری مقالات را خوانده اید، کد باید کاملاً ساده باشد.

مثل همیشه، بیایید ابتدا یک کلاس برای تک آهنگ ایجاد کنیم node در لیست:

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

می بینید که در کد بالا، a ایجاد می کنیم Node کلاس با سه متغیر عضو: item، nref، و pref. این item متغیر داده های واقعی را ذخیره می کند node. این nref مرجع را به بعدی ذخیره می کند node، در حالی که pref مرجع قبلی را ذخیره می کند node در لیست دارای پیوند دوگانه

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

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

در طول این مقاله، ما متدهایی را به این کلاس اضافه می کنیم.

درج موارد در لیست پیوندی دوگانه

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

درج موارد در لیست خالی

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

def insert_in_emptylist(self, data):
    if self.start_node is None:
        new_node = Node(data)
        self.start_node = new_node
    else:
        print("list is not empty")

این روش ابتدا بررسی می کند که آیا self.start_node متغیر است None یا نه. اگر متغیر باشد None، به این معنی است که لیست در واقع خالی است. بعد، جدید node ایجاد می شود و مقدار آن با مقداری که به عنوان پارامتر به آن ارسال می شود مقداردهی اولیه می شود data پارامتر از insert_in_emptylist() روش. در نهایت، ارزش self.start_node متغیر روی new تنظیم شده است node. در صورت خالی نبودن لیست، به سادگی پیغامی مبنی بر خالی نبودن لیست به کاربر نمایش داده می شود.

اضافه کردن insert_in_emptylist() روش به DoublyLinkedList کلاسی که قبلا ایجاد کردید

درج موارد در شروع

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

در غیر این صورت، اگر لیست خالی نیست، باید سه عملیات را انجام دهیم:

1. برای جدید node، اشاره به بعد node تنظیم خواهد شد self.start_node
2. برای self.start_node اشاره به قبلی node روی جدیدا درج شده تنظیم خواهد شد node
3. در نهایت، self.start_node تبدیل به جدید درج شده خواهد شد node

بیایید آن را در عمل اجرا کنیم insert_at_start() روش:

def insert_at_start(self, data):
    if self.start_node is None:
        new_node = Node(data)
        self.start_node = new_node
        print("node inserted")
        return
    new_node = Node(data)
    new_node.nref = self.start_node
    self.start_node.pref = new_node
    self.start_node = new_node

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

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

مرجع قبلی برای جدید node به آخرین تنظیم شده است nodeو مرجع بعدی برای آخرین node روی جدیدا درج شده تنظیم شده است node:

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

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

برای درج یک مورد بعد از آیتم دیگر، ابتدا بررسی می کنیم که آیا لیست خالی است یا خیر. اگر لیست واقعاً خالی است، ما به سادگی این پیام را نمایش می دهیم "list is empty".

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

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

برای جمع بندی همه اینها:

def insert_after_item(self, x, data):
    if self.start_node is None:
        print("List is empty")
        return
    else:
        n = self.start_node
        while n is not None:
            if n.item == x:
                break
            n = n.nref
        if n is None:
            print("item not in the list")
        else:
            new_node = Node(data)
            new_node.pref = n
            new_node.nref = n.nref
            if n.nref is not None:
                n.nref.prev = new_node
            n.nref = new_node

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

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

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

1. مرجع بعدی درج شده جدید را تنظیم کنید node به انتخاب شده node.
2. مرجع قبلی درج شده جدید را تنظیم کنید node به مرجع قبلی انتخاب شده
3. مرجع بعدی را تنظیم کنید node قبل از انتخاب شده node، به موارد جدید اضافه شده است node.
4. در نهایت، مرجع قبلی انتخاب شده را تنظیم کنید node به تازه وارد شده node.

در کل، بیایید همه اینها را در آن قرار دهیم insert_before_item() روش:

def insert_before_item(self, x, data):
    if self.start_node is None:
        print("List is empty")
        return
    else:
        n = self.start_node
        while n is not None:
            if n.item == x:
                break
            n = n.nref
        if n is None:
            print("item not in the list")
        else:
            new_node = Node(data)
            new_node.nref = n
            new_node.pref = n.pref
            if n.pref is not None:
                n.pref.nref = new_node
            n.pref = new_node

عبور از یک لیست دارای پیوند دوگانه

عبور از یک لیست دارای پیوند دوگانه بسیار شبیه به پیمایش یک لیست دارای پیوند منفرد است:

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

حذف عناصر از لیست پیوند دوگانه

مانند درج، راه‌های متعددی برای حذف عناصر از فهرست پیوندی مضاعف وجود دارد. در این قسمت به بررسی برخی از آنها می پردازیم.

حذف عناصر از ابتدا

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

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

حذف عناصر از انتها

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

def delete_at_end(self):
    if self.start_node is None:
        print("The list has no element to delete")
        return 
    if self.start_node.nref is None:
        self.start_node = None
        return
    n = self.start_node
    while n.nref is not None:
        n = n.nref
    n.pref.nref = None

حذف عناصر بر اساس مقدار

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

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.nref is None:
        if self.start_node.item == x:
            self.start_node = None
        else:
            print("Item not found")
        return 

    if self.start_node.item == x:
        self.start_node = self.start_node.nref
        self.start_node.pref = None
        return

    n = self.start_node
    while n.nref is not None:
        if n.item == x:
            break;
        n = n.nref
    if n.nref is not None:
        n.pref.nref = n.nref
        n.nref.pref = n.pref
    else:
        if n.item == x:
            n.pref.nref = None
        else:
            print("Element not found")

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

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

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

if self.start_node.nref is None:
    if self.start_node.item == x:
        self.start_node = None
    else:
        print("Item not found")
    return 

در مرحله بعد، مواردی را بررسی می کنیم که لیست بیش از یک مورد داشته باشد اما موردی که باید حذف شود اولین مورد است. در آن صورت، ما به سادگی منطقی را که برای متد نوشتیم اجرا می کنیم delete_at_start(). کد زیر یک عنصر را از ابتدا در صورت وجود چندین مورد حذف می کند:

if self.start_node.item == x:
    self.start_node = self.start_node.nref
    self.start_node.pref = None
    return

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

1. مقدار مرجع بعدی مرجع قبلی را تنظیم کنید node به مرجع بعدی node حذف شود
2. مقدار قبلی بعدی را تنظیم کنید node به مرجع قبلی node حذف شود

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

n = self.start_node
while n.nref is not None:
    if n.item == x:
        break;
    n = n.nref
if n.nref is not None:
    n.pref.nref = n.nref
    n.nref.pref = n.pref
else:
    if n.item == x:
        n.pref.nref = None
    else:
        print("Element not found")

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

برای معکوس کردن یک لیست دارای پیوند دوگانه، اساساً باید عملیات زیر را انجام دهید:

1. مرجع بعدی شروع node باید روی هیچ تنظیم شود زیرا اولی node آخرین خواهد شد node در لیست معکوس
2. مرجع قبلی آخرین node باید تنظیم شود None از آخرین node قبلی خواهد شد node
3. مراجع بعدی گره ها (به جز اولین و آخرین node) در لیست اصلی باید با مراجع قبلی جایگزین شود

روش معکوس کردن یک لیست دارای پیوند دوگانه باید چیزی شبیه به این باشد:

def reverse_linked_list(self):
    if self.start_node is None:
        print("The list has no element to delete")
        return 
    p = self.start_node
    q = p.nref
    p.nref = None
    p.pref = q
    while q is not None:
        q.pref = q.nref
        q.nref = p
        p = q
        q = q.pref
    self.start_node = p

آزمایش روش‌های فهرست پیوندی دوگانه

در این قسمت روش های پیوند دوگانه ای که در قسمت های قبل ایجاد کردیم را تست می کنیم. بیایید ابتدا شیء the را ایجاد کنیم DoublyLinkedList کلاس:

new_linked_list = DoublyLinkedList()

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

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

new_linked_list.insert_in_emptylist(50)

حالا اگر از لیست عبور کنید، همانطور که در زیر نشان داده شده است، باید 50 را به عنوان تنها عنصر در لیست ببینید:

new_linked_list.traverse_list()

این به ما می دهد:

50

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

new_linked_list.insert_at_start(10)
new_linked_list.insert_at_start(5)
new_linked_list.insert_at_start(18)

حال اگر از لیست عبور کنید، باید عناصر زیر را در لیست مشاهده کنید:

18
5
10
50

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

new_linked_list.insert_at_end(29)
new_linked_list.insert_at_end(39)
new_linked_list.insert_at_end(49)

اکنون اگر لیست پیوند دوگانه را طی کنید، باید عناصر زیر را مشاهده کنید:

18
5
10
50
29
39
49 

بیایید یک عنصر را بعد از آن وارد کنیم 50:

new_linked_list.insert_after_item(50, 65)

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

18
5
10
50
65
29
39
49 

در نهایت، اجازه دهید یک عنصر قبل از آیتم اضافه کنیم 29.

new_linked_list.insert_before_item(29, 100)

لیست در این مرحله باید شامل عناصر زیر باشد:

18
5
10
50
65
100
29
39
49 

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

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

new_linked_list.delete_at_start()

مورد 18 از لیست حذف خواهد شد:

5
10
50
65
100
29
39
49 

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

new_linked_list.delete_at_end()

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

5
10
50
65 
100 
29
39

در نهایت، شما همچنین می توانید عناصر را با استفاده از مقدار حذف کنید delete_element_by_value() روش:

new_linked_list.delete_element_by_value(65)

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

تست روش معکوس

در نهایت، بیایید لیست را با استفاده از reverse_linked_list() روش. اسکریپت زیر را اجرا کنید:

new_linked_list.reverse_linked_list()

اکنون اگر لیست را طی کنید، لیست پیوند شده معکوس را مشاهده خواهید کرد:

39
29
100
50
10
5 

نتیجه

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

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