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

معرفی

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

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

لیست های پیوندی چندین مزیت را نسبت به سایر ساختارهای داده ارائه می دهند. اولاً، آنها اجازه درج و حذف مؤثر عناصر را می دهند، زیرا فقط به به روز رسانی مراجع گره های همسایه نیاز دارند. این باعث می شود LinkedLists برای سناریوهایی که در آن تغییرات مکرر مورد انتظار است، ایده آل باشد. علاوه بر این، LinkedLists برخلاف آرایه‌ها که اندازه ثابتی دارند، می‌توانند به صورت پویا بزرگ یا کوچک شوند.

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

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

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

لیست تک پیوندی

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

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

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

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

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 را تعریف می کنیم که حاوی مقدار، ارجاع به گره بعدی و ارجاع به گره قبلی است. کلاس DoublyLinked 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

فهرست پیوندی دایره ای

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

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

بررسی اینکه آیا یک لیست پیوندی خالی است یا خیر

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

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) پیروی می کند. عناصر از همان انتهایی که به بالای پشته معروف است اضافه و حذف می شوند. لیست‌های پیوندی روشی کارآمد برای پیاده‌سازی پشته‌ها فراهم می‌کنند، زیرا می‌توانیم به راحتی عناصر را از سر فهرست اضافه یا حذف کنیم.

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

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) پیروی می کند. عناصری در یک سر اضافه می شوند که به عنوان عقب شناخته می شود و از انتهای دیگر که به عنوان جلو شناخته می شود حذف می شوند. از لیست های پیوندی نیز می توان برای اجرای کارآمد صف ها استفاده کرد.

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

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) نیز می‌توانند با استفاده از لیست‌های پیوندی پیاده‌سازی شوند. در پیمایش گراف، از هر رأس یا گره در یک گراف به ترتیب خاصی بازدید می کنیم.

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

بازنمایی چند جمله ای

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

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

لیست های پخش موسیقی و ویدیو

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

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

نتیجه

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

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

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

همچنین می‌توانید مقالات بیشتر مرتبط با فهرست‌های پایتون را در اینجا بخوانید:

پرسش و پاسخهای متداول

مربوط

• محتوای مبتنی بر SEO و توزیع روابط عمومی. امروز تقویت شوید.
• PlatoData.Network Vertical Generative Ai. به خودت قدرت بده دسترسی به اینجا.
• PlatoAiStream. هوش وب 3 دانش تقویت شده دسترسی به اینجا.
• PlatoESG. کربن ، CleanTech، انرژی، محیط، خورشیدی، مدیریت پسماند دسترسی به اینجا.
• PlatoHealth. هوش بیوتکنولوژی و آزمایشات بالینی. دسترسی به اینجا.
• منبع: https://www.analyticsvidhya.com/blog/2024/02/linked-lists-in-python/