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

معرفی

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

به طور کلی، یک لیست مجموعه ای از عناصر داده منفرد است که از طریق مراجع به هم متصل می شوند. برنامه نویسان C این را می دانند اشاره گرها. به عنوان مثال، یک عنصر داده می تواند شامل داده های آدرس، داده های جغرافیایی، داده های هندسی، اطلاعات مسیریابی یا جزئیات تراکنش باشد. معمولاً، هر عنصر از لیست پیوند داده شده دارای همان نوع داده ای است که مختص لیست است.

یک عنصر لیست واحد a نامیده می شود node. گره ها مانند آرایه هایی نیستند که به صورت متوالی در حافظه ذخیره می شوند. در عوض، احتمالاً آنها را در بخش‌های مختلف حافظه پیدا می‌کند، که می‌توانید با دنبال کردن نشانگرهای یکی آن‌ها را پیدا کنید node بعدی. معمول است که انتهای لیست را با علامت علامت گذاری کنید عنصر NIL:

تصویر: لیست تک پیوندی

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

تصویر: لیست دوتایی

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

زبان پایتون شامل نمی شود یک نوع داده از پیش تعریف شده برای لیست های پیوندی. برای کنار آمدن با این وضعیت یا باید نوع داده خودمان را ایجاد کنیم یا باید از ماژول های اضافی پایتون استفاده کنید که اجرای چنین نوع داده ای را ارائه می دهند.

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

تعریف گره به عنوان ساختار داده

برای داشتن ساختار داده ای که بتوانیم با آن کار کنیم، a را تعریف می کنیم node. الف را اجرا خواهیم کرد node به عنوان یک کلاس به نام ListNode. کلاس شامل تعریفی برای ایجاد یک نمونه شی است، در این مورد، با دو متغیر – data برای نگه داشتن node ارزش، و next برای ذخیره ارجاع به بعدی node در لیست علاوه بر این، الف node دارای روش ها و خواص زیر است:

• __init_() – مقداردهی اولیه node با داده ها
• self.data – مقدار ذخیره شده در node
• self.next – اشاره گر مرجع به بعدی node
• has_value() – یک مقدار را با node ارزش

این روش ها تضمین می کنند که می توانیم a را مقداردهی اولیه کنیم node به درستی با داده های ما (__init__()، و استخراج و ذخیره سازی داده ها را پوشش می دهد (از طریق self.data ویژگی) و همچنین دریافت ارجاع به متصل node (از طریق self.next ویژگی). روش has_value() به ما اجازه می دهد تا مقایسه کنیم node ارزش با ارزش متفاوت node:

class ListNode:
    def __init__(self, data):
        "constructor to initiate this object"
        
        
        self.data = data
        
        
        self.next = None
    
    def has_value(self, value):
        "method to compare the value with the node data"
        if self.data == value:
            return True
        else:
            return False

حالا که ما خودمان را داریم ListNode کلاس، ایجاد یک node به سادگی مثال زدن یک شی از ماست node کلاس:

node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")

پس از انجام این کار، ما سه نمونه از آن را در دسترس داریم ListNode کلاس این نمونه ها سه گره مستقل را نشان می دهند که حاوی مقادیر هستند 15 (عدد صحیح)، 8.2 (شناور)، و "Berlin" (رشته).

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

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

• __init__() – شروع یک شی
• list_length() – تعداد گره ها را برگردانید
• output_list() – خروجی node ارزش های
• add_list_item() – اضافه کردن a node در انتهای لیست
• unordered_search() – لیست را برای گره هایی با مقدار مشخص جستجو کنید
• remove_list_item_by_id() – حذف کنید node با توجه به شناسه آن

هر یک از این روش ها را مرحله به مرحله مرور خواهیم کرد.

این __init__() متد دو متغیر کلاس داخلی را با نام تعریف می کند head و tail. آنها گره های آغاز و پایان لیست را نشان می دهند. در ابتدا، هر دو head و tail ارزش دارند None تا زمانی که لیست خالی باشد:

class SingleLinkedList:
    def __init__(self):
        "constructor to initiate this object"
        
        self.head = None
        self.tail = None

اضافه کردن گره ها به لیست تک پیوندی

افزودن موارد به لیست از طریق انجام می شود add_list_item(). این روش مستلزم الف node به عنوان یک پارامتر اضافی برای اطمینان از مناسب بودن آن node (نمونه ای از کلاس ListNode) ابتدا پارامتر با استفاده از تابع داخلی پایتون تأیید می شود isinstance(). در صورت موفقیت، node در انتهای لیست اضافه خواهد شد. اگر item یک نیست ListNode، سپس یکی ایجاد می شود.

در صورتی که لیست (هنوز) جدید را خالی کنید node رئیس لیست می شود. اگر یک node در حال حاضر در لیست است، سپس مقدار دم بر این اساس تنظیم می شود:

def add_list_item(self, item):
    "add an item at the end of the list"

    if not isinstance(item, ListNode):
        item = ListNode(item)

    if self.head is None:
        self.head = item
    else:
        self.tail.next = item

    self.tail = item

این list_length() متد تعداد گره ها را می شمارد و برمی گرداند طول لیست. برای گرفتن از یکی node به بعدی در لیست node ویژگی self.next وارد بازی می شود و پیوند را به بعدی برمی گرداند node. شمارش گره ها در a انجام می شود while تا زمانی که به انتهای لیست که با a نشان داده شده است نرسیده باشیم حلقه بزنید None لینک بعدی node:

def list_length(self):
    "returns the number of list items"

    count = 0
    current_node = self.head

    while current_node is not None:
        
        count = count + 1

        
        current_node = current_node.next

    return count

روش output_list() خروجی می دهد node ارزش های با استفاده از node ویژگی data. باز هم برای گرفتن از یکی node به لینک بعدی استفاده می شود که از طریق ارائه شده است next ویژگی:

def output_list(self):
    "outputs the list (the value of the node, actually)"

     current_node = self.head

    while current_node is not None:
        print(current_node.data)

        
        current_node = current_node.next

مستقر روی کلاس SingleLinkedList ما می توانیم یک لیست مناسب با نام ایجاد کنیم track، و با روش های آن همانطور که قبلاً در بالا توضیح داده شد بازی کنید. بنابراین، اجازه دهید چهار گره لیست ایجاد کنیم، آنها را در a ارزیابی کنیم for حلقه بزنید و محتوای لیست را خروجی بگیرید:

node1 = ListNode(15)
node2 = ListNode(8.2)
item3 = "Berlin"
node4 = ListNode(15)

track = SingleLinkedList()
print("track length: %i" % track.list_length())

for current_item in (node1, node2, item3, node4):
    track.add_list_item(current_item)
    print("track length: %i" % track.list_length())
    track.output_list()

خروجی به شرح زیر است و روش رشد لیست را نشان می دهد:

track length: 0
track length: 1
15
track length: 2
15
8.2
track length: 3
15
8.2
Berlin
track length: 4
15
8.2
Berlin
15

جستجو در لیست پیوندی

جستجوی کل لیست با استفاده از روش انجام می شود unordered_search(). برای جستجوی مقدار به یک پارامتر اضافی نیاز دارد. سر لیست نقطه شروع است.

در حین جستجو گره ها را می شماریم. برای نشان دادن یک تطابق از متن مربوطه استفاده می کنیم node عدد. روش unordered_search() لیستی از node اعدادی که نشان دهنده مسابقات هستند:

def unordered_search (self, value):
    "search the linked list for the node that has this value"

    
    current_node = self.head

    
    node_id = 1

    
    results = ()

    while current_node is not None:
        if current_node.has_value(value):
            results.append(node_id)

        
        current_node = current_node.next
        node_id = node_id + 1

    return results

در مثال قبل، هم اول و هم چهارم node حاوی مقدار باشد 15. بیایید جستجوی a را امتحان کنیم 15 در یک track لیست پیوندی از مثال قبلی:

search_result = track.unordered_search(15)
print(search_result)

این منجر به:

(1, 4)

همانطور که انتظار می رفت، درست است؟ از آنجا که track لیست پیوندی شامل 15 به عنوان عنصر اول و چهارم.

حذف یک مورد از لیست پیوند شده

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

روش زیر نامگذاری شده است remove_list_item_by_id(). به عنوان یک پارامتر، به تعداد گره های مشابه با مقدار بازگشتی اشاره می کند unordered_search():

def remove_list_item_by_id(self, item_id):
    "remove the list item with the item id"

    current_id = 1
    current_node = self.head
    previous_node = None

    while current_node is not None:
        if current_id == item_id:
            
            if previous_node is not None:
                previous_node.next = current_node.next
            else:
                self.head = current_node.next
                
                return

        
        previous_node = current_node
        current_node = current_node.next
        current_id = current_id + 1

برای حذف، مثلاً، عنصر چهارم از a track لیستی که فقط باید تماس بگیرید:

track.remove_list_item_by_id(4)

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

برای ایجاد یک لیست دوگانه، طبیعی است که فقط آن را گسترش دهید ListNode کلاس با ایجاد یک مرجع اضافی به قبلی node.

این روی روش‌های افزودن، حذف و مرتب‌سازی گره‌ها تأثیر می‌گذارد.

بیایید یک ویژگی جدید به نام اضافه کنیم previous برای ذخیره اشاره گر مرجع به قبلی node در لیست روش‌های خود را برای استفاده از این ویژگی برای ردیابی و پیمایش گره‌ها نیز تغییر می‌دهیم:

class ListNode:
    def __init__(self, data):
        "constructor class to initiate this object"

        
        self.data = data
        
        
        self.next = None

        
        self.previous = None

    def has_value(self, value):
        "method to compare the value with the node data"
        if self.data == value:
            return True
        else:
            return False

اکنون می‌توانیم یک لیست دوگانه را تعریف کنیم:

class DoubleLinkedList:
    def __init__(self):
        "constructor to initiate this object"

        self.head = None
        self.tail = None

    def list_length(self):
        "returns the number of list items"
        
        count = 0
        current_node = self.head

        while current_node is not None:
            
            count = count + 1
            
            
            current_node = current_node.next
        
        return count

    def output_list(self):
        "outputs the list (the value of the node, actually)"
        current_node = self.head

        while current_node is not None:
            print(current_node.data)

            
            current_node = current_node.next
        
    def unordered_search (self, value):
        "search the linked list for the node that has this value"

        
        current_node = self.head

        
        node_id = 1

        
        results = ()

        while current_node is not None:
            if current_node.has_value(value):
                results.append(node_id)
            
            
            current_node = current_node.next
            node_id = node_id + 1
        
        return results

همانطور که قبلا توضیح داده شد، اضافه کردن گره ها کمی اقدام بیشتری می طلبد بیایید نگاهی به روش اجرای آن بیندازیم:

def add_list_item(self, item):
    "add an item at the end of the list"

    if isinstance(item, ListNode):
        if self.head is None:
            self.head = item
            item.previous = None
            item.next = None
            self.tail = item
        else:
            self.tail.next = item
            item.previous = self.tail
            self.tail = item

حذف یک مورد از لیست هزینه های مشابه باید در نظر گرفته شود:

def remove_list_item_by_id(self, item_id):
    "remove the list item with the item id"

    current_id = 1
    current_node = self.head

    while current_node is not None:
        previous_node = current_node.previous
        next_node = current_node.next

        if current_id == item_id:
            
            if previous_node is not None:
                previous_node.next = next_node
                if next_node is not None:
                    next_node.previous = previous_node
            else:
                self.head = next_node
                if next_node is not None:
                    next_node.previous = None
            
            return

        
        current_node = next_node
        current_id = current_id + 1

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

node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")
node4 = ListNode(15)

track = DoubleLinkedList()
print("track length: %i" % track.list_length())

for current_node in (node1, node2, node3, node4):
    track.add_list_item(current_node)
    print("track length: %i" % track.list_length())
    track.output_list()

results = track.unordered_search(15)
print(results)

track.remove_list_item_by_id(4)
track.output_list()

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

تنها تغییر ساختار داده داخلی است!

ایجاد لیست های دوگانه با دکه هدف – شی

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

به عنوان مثال، این شی شامل متدهای زیر است:

• append(): یک مورد را به سمت راست لیست اضافه کنید (پایان)
• append_left(): یک مورد را به سمت چپ لیست اضافه کنید (سر)
• clear(): همه موارد را از لیست حذف کنید
• count(): تعداد اقلام با مقدار معین را بشمارید
• index(): اولین وقوع یک مقدار را در لیست پیدا کنید
• insert(): یک مورد را در لیست قرار دهید
• pop(): حذف یک مورد از سمت راست یک لیست (پایان)
• popleft(): حذف یک مورد از سمت چپ یک لیست (سر)
• remove(): یک مورد را از لیست حذف کنید
• reverse(): لیست را معکوس کنید

ساختار داده های زیربنایی deque یک لیست پایتون است که دو پیوند دارد. لیست اول node دارای شاخص 0. با استفاده از deque منجر به الف می شود ساده سازی قابل توجهی از ListNode کلاس. تنها چیزی که نگه می داریم متغیر کلاس است data برای ذخیره کردن node ارزش:

from collections import deque

class ListNode:
    def __init__(self, data):
        "constructor class to initiate this object"
        
        
        self.data = data

تعریف گره ها تغییر نمی کند و شبیه به آنچه قبلاً با آن کار کرده ایم است. با در نظر گرفتن این دانش، لیستی از گره ها را با استفاده از dequeue سازنده:

track = deque((node1, node2, node3))
print("three items (initial list):")
for item in track:
    print(item.data)

افزودن یک آیتم در ابتدای لیست با append_left() روش:

node4 = ListNode(15)
track.append_left(node4)
print("four items (added as the head):")
for item in track:
    print(item.data)

به همین ترتیب، append() الف را اضافه می کند node در انتهای لیست:

node5 = ListNode("Moscow")
print("five items (added at the end):")
track.append(node5)
for item in track:
    print(item.data)

نتیجه

لیست های پیوندی به عنوان ساختارهای داده به راحتی قابل پیاده سازی هستند و انعطاف پذیری زیادی در استفاده ارائه می دهند. با چند خط کد انجام می شود. به عنوان یک بهبود، می توانید یک را اضافه کنید node counter – یک متغیر کلاس که به سادگی تعداد گره های لیست را نگه می دارد. این امر تعیین طول لیست را به یک عملیات واحد با O(1) کاهش می دهد و شما مجبور نیستید کل لیست را طی کنید.

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