لینک لیست LinkedList چیست؟

مقدمه

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

گره یا Node

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

انواع Linkedlist

• linkedlist منفرد : در لینک لیست منفرد، هر گره مرجعی به گره بعدی دارد که یک زنجیره یک طرفه را تشکیل می دهد. آخرین گره به null اشاره می کند تا پایان لیست را نشان دهد.

• linkedlist دوگانه : در linkedlist دوگانه، هر گره به هر دو گره بعدی و قبلی ارجاعاتی دارد که یک زنجیره دو طرفه را تشکیل می دهد. این امکان پیمایش در هر دو جهت را فراهم می کند.

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

عملیات های پایه

• اضافه کردن : درج یا همان اضافه کردن در linkedlist سه نوع دارد یعنی اضافه کردن به اول لینک لیست ، اضافه کردن به اخر linkedlist یعنی اضافه کردن به اخرین و یا اولین گره و اخرین نوع هم اضافه کردن در گره مورد نظر هستش.

• حذف کردن: حذف یک گره از linkedlist شامل بروزرسانی مراجع گره‌های قبلی و بعدی است که سه نوع دارد ، حذف از ابتدای لیست که باید مرجع و یا همان ادرس head رو به گره دوم بروزرسانی کنیم، حذف از انتهای لیست که باید لیست رو تا گره دوم از اخر عبور بدیم و ادرس بعدی اون رو null قرار بدیم. و در اخر حذف از موقعیت خاص که مانند اضافه ردن عمل میکند منتها برعکس و حذف میکند.

• پیمایش : linkedlist را می توان از ابتدا تا انتها با دنبال کردن مراجع بعدی هر گره تا رسیدن به انتهای لیست طی کرد.

همچنین بخوانید: تفاوت استک و هیپ: کدام برای تخصیص حافظه بهتر است؟

پیاده سازی

# Node class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# Linked List class
class LinkedList:
    def __init__(self):
        self.head = None
 
    # Insertion at the beginning of the list
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
 
    # Insertion at the end of the list
    def insert_at_end(self, data):
        new_node = Node(data)
 
        # If the list is empty, make the new node the head
        if self.head is None:
            self.head = new_node
            return
 
        current = self.head
        while current.next:
            current = current.next
 
        current.next = new_node
 
    # Insertion at a specific position
    def insert_at_position(self, data, position):
        new_node = Node(data)
 
        # If the list is empty or position is 0, insert at the beginning
        if self.head is None or position == 0:
            self.insert_at_beginning(data)
            return
 
        current = self.head
        prev = None
        count = 0
 
        while current and count < position:
            prev = current
            current = current.next
            count += 1
 
        if current is None:
            # If the position exceeds the length of the list, insert at the end
            prev.next = new_node
        else:
            # Insert at the specified position
            new_node.next = current
            prev.next = new_node
 
    # Deletion of a node with given data
    def delete_node(self, data):
        if self.head is None:
            return
 
        # If the node to be deleted is the head node
        if self.head.data == data:
            self.head = self.head.next
            return
 
        current = self.head
        prev = None
 
        while current and current.data != data:
            prev = current
            current = current.next
 
        if current is None:
            # Node not found
            return
 
        prev.next = current.next
 
    # Traversal of the linked list
    def traverse(self):
        current = self.head
 
        while current:
            print(current.data, end=" ")
            current = current.next
 
        print()

همچنین برای اشناییت با نحوه پیاده سازی Linkedlist میتوانید از این ریپو یک نمونه کار ببینید: Linkedlist

مزایا

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

معایب

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

همچنین بخوانید: معرفی GPT-4.5 اوریون جدیدترین مدل هوش مصنوعی OpenAI

موارد استفاده linkedlist

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

خلاصه

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