30 نمونه سوال لیست پیوندی ساختمان داده با جواب

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

اصطلاحات پایه‌ای لیست پیوندی

•  سر (Head): سر لیست پیوندی یک اشاره‌گر به اولین گره یا مرجع اولین گره از لیست پیوندی است. این اشاره‌گر آغاز لیست پیوندی را نشان می‌دهد.
• گره (Node): لیست پیوندی شامل یک سری از گره‌ها است که هر گره دو بخش دارد: داده و اشاره‌گر به گره بعدی
• داده (Data): داده بخشی از گره است که اطلاعات را در لیست پیوندی ذخیره می‌کند
• اشاره‌گر به گره بعدی (Next pointer): اشاره‌گر به گره بعدی بخشی از گره است که به گره بعدی در لیست پیوندی اشاره می‌کند.

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

ساختار داده دینامیک

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

• ساختار داده دینامیک: اندازه حافظه می‌تواند در زمان اجرا بر اساس عملیات درج یا حذف تخصیص داده شود یا آزاد شود.
• سهولت در درج/حذف: درج و حذف عناصر در مقایسه با آرایه‌ها ساده‌تر است زیرا نیازی به جابجایی عناصر پس از درج و حذف نیست، فقط آدرس نیاز به بروزرسانی دارد.
• استفاده بهینه از حافظه: همانطور که می‌دانیم لیست پیوندی یک ساختار داده دینامیک است، اندازه آن بر اساس نیاز افزایش یا کاهش می‌یابد بنابراین از هدررفت حافظه جلوگیری می‌کند.
• پیاده‌سازی: ساختارهای داده پیشرفته مختلفی می‌توانند با استفاده از لیست پیوندی پیاده‌سازی شوند، مانند پشته (stack)، صف (queue)، گراف (graph)، نقشه‌های هش (hash maps) و غیره.

حتما دانلود کنید: آموزش ساختمان داده از صفر تا صد (10 درس رایگان)

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

لیست‌های پیوندی (Linked Lists) یکی از ساختارهای داده‌ای مهم در علوم کامپیوتر و برنامه‌نویسی هستند که برای ذخیره‌سازی و مدیریت داده‌ها به صورت پویا استفاده می‌شوند. این ساختارها شامل مجموعه‌ای از گره‌ها (Nodes) هستند که هر کدام شامل داده‌ها و یک اشاره‌گر به گره بعدی می‌باشند. انواع مختلفی از لیست‌های پیوندی وجود دارند که هر کدام کاربردها و مزایای خاص خود را دارند.

این نوع لیست شامل گره‌هایی است که هر کدام تنها به گره بعدی اشاره می‌کنند. این ساختار ساده‌ترین نوع لیست پیوندی است و عملیات اضافه کردن یا حذف کردن گره‌ها در آن به راحتی انجام می‌شود. با این حال، پیمایش معکوس در این لیست‌ها دشوار است زیرا هر گره فقط به گره بعدی دسترسی دارد.
2. لیست پیوندی دوگانه (Doubly Linked List): در این نوع لیست، هر گره دارای دو اشاره‌گر است؛ یکی به گره بعدی و دیگری به گره قبلی اشاره می‌کند. این ویژگی امکان پیمایش در هر دو جهت را فراهم می‌کند و عملیات‌هایی مثل حذف گره از وسط لیست را ساده‌تر می‌کند. با این حال، این لیست‌ها از لحاظ حافظه بیشتر از لیست‌های پیوندی ساده نیاز دارند.

در این لیست، آخرین گره به جای اشاره به مقدار null، به اولین گره اشاره می‌کند. این ویژگی باعث می‌شود تا پیمایش در لیست به صورت چرخشی انجام شود. این نوع لیست می‌تواند به صورت ساده یا دوگانه پیاده‌سازی شود و معمولاً در سیستم‌های مبتنی بر چرخه‌ها کاربرد دارد.
4. لیست پیوندی چندگانه (Multi-linked List): در این نوع لیست، هر گره ممکن است دارای چندین اشاره‌گر به گره‌های مختلف باشد. این نوع ساختار معمولاً برای پیاده‌سازی گراف‌ها یا سیستم‌های پیچیده‌تری که نیاز به ارتباطات چندگانه بین داده‌ها دارند، استفاده می‌شود.
هر نوع لیست پیوندی با توجه به نیازهای خاص برنامه و شرایط مختلف، مزایا و معایب خود را دارد. انتخاب نوع مناسب از این لیست‌ها می‌تواند تأثیر زیادی بر عملکرد و کارایی برنامه‌های کامپیوتری داشته باشد. به عنوان مثال، اگر نیاز به پیمایش سریع و دسترسی دو طرفه به داده‌ها باشد، لیست پیوندی دوگانه انتخاب بهتری است. از سوی دیگر، اگر به دنبال ساختاری ساده و کارآمد از نظر حافظه هستیم، لیست پیوندی ساده گزینه مناسبی خواهد بود.

از دست ندین: 7 بهترین آموزشگاه کلاس برنامه نویسی (تهران+ شهرهای بزرگ)

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

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

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

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

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

 ایجاد یک لیست جدید

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

در زبان برنامه‌نویسی Python، این ساختار به شکل زیر تعریف می‌شود:

class Node:

    def __init__(self, data=None):

        self.data = data

        self.next = None

برای ایجاد یک لیست جدید، نیاز است که یک شیء از این کلاس بسازیم و اشاره‌گر سر لیست (Head) را به آن اختصاص دهیم. این کار به شکل زیر انجام می‌شود:

class LinkedList:

    def __init__(self):

        self.head = None

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

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

حتما دانلود کنید: آموزش مهندسی کامپیوتر از صفر با 8 درس رایگان

 افزودن به ابتدای لیست

برای افزودن یک نود به ابتدای لیست، نیاز است که اشاره‌گر سر لیست به نود جدید اشاره کند و اشاره‌گر نود جدید به نود قبلی که در ابتدای لیست بود اشاره کند.

def add_to_beginning(self, data):

    new_node = Node(data)

    new_node.next = self.head

    self.head = new_node

 افزودن به انتهای لیست

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

def add_to_end(self, data):

    new_node = Node(data)

    if not self.head:

        self.head = new_node

        return

    last_node = self.head

    while last_node.next:

        last_node = last_node.next

    last_node.next = new_node

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

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

def add_at_position(self, data, position):

    if position == 0:

        self.add_to_beginning(data)

        return

    new_node = Node(data)

    current = self.head

    for _ in range(position - 1):

        if current is None:

            raise IndexError("Position out of bounds")

        current = current.next

    new_node.next = current.next

    current.next = new_node

حذف یک نود از لیست

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

 حذف از ابتدای لیست

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

def remove_from_beginning(self):

    if self.head is None:

        raise ValueError("List is empty")

    self.head = self.head.next

 حذف از انتهای لیست

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

def remove_from_end(self):

    if self.head is None:

        raise ValueError("List is empty")

    if self.head.next is None:

        self.head = None

        return

    second_last = self.head

    while second_last.next.next:

        second_last = second_last.next

    second_last.next = None

 حذف از موقعیت خاصی در لیست

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

def remove_at_position(self, position):

    if self.head is None:

        raise ValueError("List is empty")

    if position == 0:

        self.head = self.head.next

        return

    current = self.head

    for _ in range(position - 1):

        if current.next is None:

            raise IndexError("Position out of bounds")

        current = current.next

    if current.next is None:

        raise IndexError("Position out of bounds")

    current.next = current.next.next

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

برای جستجوی یک نود در لیست پیوندی، نیاز است که از ابتدا تا انتهای لیست پیمایش کنیم و داده مورد نظر را با داده هر نود مقایسه کنیم.

def search(self, key):

    current = self.head

    while current:

        if current.data == key:

            return True

        current = current.next

    return False

مرتب‌سازی یک لیست

مرتب‌سازی یک لیست پیوندی می‌تواند به روش‌های مختلفی انجام شود. یکی از ساده‌ترین روش‌ها، استفاده از مرتب‌سازی حبابی (Bubble Sort) است. در این روش، ما چندین بار از ابتدا تا انتهای لیست پیمایش می‌کنیم و در هر پیمایش، دو نود مجاور را مقایسه و در صورت نیاز جابه‌جا می‌کنیم.

def bubble_sort(self):

    end = None

    while end != self.head:

        current = self.head

        while current.next != end:

            next_node = current.next

            if current.data > next_node.data:

                current.data, next_node.data = next_node.data, current.data

            current = current.next

        end = current

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

برای معکوس کردن یک لیست پیوندی، نیاز است که جهت اشاره‌گرهای هر نود را تغییر دهیم، به طوری که هر نود به نود قبلی اشاره کند. این کار را می‌توان با استفاده از سه اشاره‌گر انجام داد: قبلی (Previous)، فعلی (Current) و بعدی (Next).

def reverse(self):

    prev = None

    current = self.head

    while current:

        next_node = current.next

        current.next = prev

        prev = current

        current = next_node

    self.head = prev<br>
این روش به ما امکان می‌دهد که به صورت گام به گام از ابتدا تا انتهای لیست پیمایش کنیم و در هر گام، جهت اشاره‌گر فعلی را تغییر دهیم.

آموزش طراحی الگوریتم از صفر تا صد (20 درس رایگان)

مزایای لیست پیوندی

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

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

• استفاده از حافظه: استفاده از اشاره‌گرها در لیست‌های پیوندی بیشتر است، بنابراین پیچیده‌تر بوده و نیاز به حافظه بیشتری دارد.
• دسترسی به یک گره: دسترسی تصادفی به دلیل تخصیص حافظه پویا ممکن نیست.
• عملیات جستجو پرهزینه: جستجوی یک عنصر پرهزینه است و به پیچیدگی زمانی O(n) نیاز دارد.
• پیمایش معکوس: پیمایش معکوس زمان بیشتری می‌برد و پیمایش معکوس در لیست‌های پیوندی تک‌سویه ممکن نیست.

حتما دانلود کنید: آموزش صفر تا صد sql (رایگان)

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