مسیر رتبه‌برترشدن در کنکور ارشد مهندسی کامپیوتر و IT
ثبت‌نام رایگان
مدت زمان باقیمانده :
ثانیه -
دقیقه -
ساعت -
روز -
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

لیست پیوندی دو طرفه

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

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

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

لیست پیوندی دوطرفه

نمایش لیست پیوندی دوطرفه

بیایید ببینیم چگونه می‌توانیم لیست پیوندی دو طرفه را در یک الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوانالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد یا سورس کد (Source Code)سورس کد چیست؟ آیا سورس کد یا سورس برنامه قابلیت اجرا دارند؟سورس کد چیست؟ آیا سورس کد یا سورس برنامه قابلیت اجرا دارند؟این مقاله عالی به سورس کد یا سورس برنامه پرداخته؛ همچنین به بررسی اهداف سورس کد، نحوه ساخت سورس کد و اینکه آیا سورس کد ها قابلیت اجرا دارند پرداخته نشان دهیم. فرض کنید ما یک لیست پیوندی دو طرفه داریم:

نمونه ای از یک لیست پیوندی دوطرفه

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

struct node {
    int data;
    struct node *next;
    struct node *prev;
}

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

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
one->prev = NULL;

two->next = three;
two->prev = one;

three->next = NULL;
three->prev = two;

/* Save address of first node in head */
head = one;

در کد بالا، one, two و three به ترتیب، گره‌هایی با داده‌های 1، 2 و 3 هستند.

توجه کنید که در مورد گره prev ،head به null و در مورد اشاره گر tail، نقطه بعدی به null است. در اینجا، یک گره head و سه گره tail است.

درج در لیست پیوندی دوطرفه

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

فرض کنید یک لیست دو طرفه با عناصر 1، 2 و 3 به شکل زیر داریم:

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

درج در ابتدا

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

  1. یک گره جدید ایجاد کنید. ایجاد گره جدید
  2. اشاره‌گرهای قبلی و بعدی گره جدید را تنظیم کنید.
    • اشاره‌گر next گره جدید را به اولین گره از لیست پیوندی دوطرفه اشاره دهید.
    • اشاره‌گر prev را به null اشاره دهید.
    درج گره در ابتدای لیست پیوندی دوطرفه
  3. گره جدید را به عنوان گره head قرار دهید.
    • اشاره‌گر prev گره اول را به گره جدید اشاره دهید.
    • head را به گره جدید ببرید.
    نمونه ای از لیست پیوندی دوطرفه که گره جدید در ابتدای آن درج شده است

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

// insert node at the front
void insertFront(struct Node** head, int data) {

    // allocate memory for newNode
    struct Node* newNode = new Node;

    // assign data to newNode
    newNode->data = data;

    // point next of newNode to the first node of the doubly linked list
    newNode->next = (*head);

    // point prev to NULL
    newNode->prev = NULL;

    // point previous of the first node (now first node is the second node) to newNode
    if ((*head) != NULL)
        (*head)->prev = newNode;

    // head points to newNode
    (*head) = newNode;
}

درج در بین دو گره

بیایید یک گره با مقدار 6 بعد از گره با مقدار 1 در لیست پیوندی دوطرفه اضافه کنیم.

  1. یک گره جدید ایجاد کنید.
    • برای گره جدید، حافظه تخصیص دهید.
    • داده را به گره جدید اختصاص دهید.
    ایجاد گره جدید
  2. اشاره‌گر next گره جدید و گره قبلی را تنظیم کنید.
    • مقدار اشاره‌گر next از گره قبلی را به اشاره‌گر next گره جدید اختصاص دهید.
    • آدرس گره جدید را به اشاره‌گر next گره قبلی اختصاص دهید.
    درج گره جدید در وسط لیست پیوندی دوطرفه
  3. اشاره‌گر prev گره جدید و گره بعدی را تنظیم کنید.
    • مقدار اشاره‌گر prev گره بعدی را به اشاره‌گر prev گره جدید اختصاص دهید.
    • آدرس گره جدید را به اشاره‌گر prev گره بعدی اختصاص دهید.
    درج گره جدید در وسط لیست پیوندی دوطرفه

در نهایت لیست پیوندی دو طرفه بعد از این درج، به شکل زیر است:

نمونه ای از لیست پیوندی دوطرفه با گره درج شده در بین لیست

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

// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {

    // check if previous node is NULL
    if (prev_node == NULL) {
        cout  “previous node cannot be NULL”;
        return;
    }

    // allocate memory for newNode
    struct Node* newNode = new Node;

    // assign data to newNode
    newNode->data = data;

    // set next of newNode to next of prev node
    newNode->next = prev_node->next;

    // set next of prev node to newNode
    prev_node->next = newNode;

    // set prev of newNode to the previous node
    newNode->prev = prev_node;

    // set prev of newNode’s next to newNode
    if (newNode->next != NULL)
        newNode->next->prev = newNode;
}

درج در انتها

حال بیایید یک گره با مقدار 6 در انتهای لیست پیوندی دوطرفه اضافه کنیم.

  1. یک گره جدید ایجاد کنید.
    ایجاد گره جدید
  2. اشاره‌گر prev و next گره جدید و گره قبلی را تنظیم کنید.

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

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

در نهایت، لیست پیوندی دوطرفه بعد از این درج، به شکل زیر است:

نمونه ای از لیست پیوندی دوطرفه به همراه گره درج شده در انتها

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

// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
    // allocate memory for node
    struct Node* newNode = new Node;

    // assign data to newNode
    newNode->data = data;

    // assign NULL to next of newNode
    newNode->next = NULL;

    // store the head node temporarily (for later use)
    struct Node* temp = *head;

    // if the linked list is empty, make the newNode as head node
    if (*head == NULL) {
        newNode->prev = NULL;
        *head = newNode;
        return;
    }

    // if the linked list is not empty, traverse to the end of the linked list
    while (temp->next != NULL)
        temp = temp->next;
   
    // now, the last node of the linked list is temp

    // point the next of the last node (temp) to newNode.
    temp->next = newNode;

    // assign prev of newNode to temp
    newNode->prev = temp;
}

آموزش درس ساختمان داده

قبل از مطالعه ادامه مقاله لازم به ذکر است که برای مشاهده و آموزش سایر مباحث مربوط به درس ساختمان داده و الگوریتم می‌توانید از فیلم‌های زیر استفاده کنید

 

فیلم ساختمان داده جلسه 1

فیلم ساختمان داده جلسه 1

فیلم ساختمان داده جلسه 1

فیلم ساختمان داده جلسه 2

فیلم ساختمان داده جلسه 2

فیلم ساختمان داده جلسه 3

فیلم ساختمان داده جلسه 3

فیلم ساختمان داده جلسه 4

فیلم ساختمان داده جلسه 4

فیلم ساختمان داده جلسه 5

فیلم ساختمان داده جلسه 5

فیلم ساختمان داده جلسه 6

فیلم ساختمان داده جلسه 6

فیلم ساختمان داده جلسه 7

فیلم ساختمان داده جلسه 7

فیلم ساختمان داده جلسه 8

فیلم ساختمان داده جلسه 8

حل تست ساختمان و الگوریتم جلسه 1

حل تست ساختمان و الگوریتم جلسه 1

حل تست ساختمان و الگوریتم جلسه 2

حل تست ساختمان و الگوریتم جلسه 2

حل تست ساختمان و الگوریتم جلسه 3

حل تست ساختمان و الگوریتم جلسه 3

حل تست ساختمان و الگوریتم جلسه 4

حل تست ساختمان و الگوریتم جلسه 4

انواع پیمایش‌های درخت

انواع پیمایش‌های درخت

نحوه ساخت درخت BST

نحوه ساخت درخت BST

آموزش درخت B-Tree

آموزش درخت B-Tree

بررسی مرتبه ساخت هیپ

بررسی مرتبه ساخت هیپ

آموزش مرتب سازی سریع

آموزش مرتب سازی سریع

آموزش شبکه شار

آموزش شبکه شار

حل سوالات ساختمان ارشد کامپیوتر 99

حل سوالات ساختمان ارشد کامپیوتر 99

حل ساختمان ارشد 95 بخش 1

حل ساختمان ارشد 95 بخش 1

حل ساختمان ارشد 95 بخش 2

حل ساختمان ارشد 95 بخش 2

نمایش بیشتر
نمایش کمتر

 

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

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

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

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

فرض کنید گره‌‌ای که می‌خواهیم حذفش کنیم، گره 1 باشد و آن‌را del_node بنامیم. اگر گره‌ای که باید حذف شود در ابتدا باشد، اشاره‌گرهای head و گره 2 را دوباره مقداردهی می‌کنیم:

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

در نهایت لیست پیوندی، به صورت زیر خواهد بود:

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

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

if (*head == del_node)
    *head = del_node->next;

if (del_node->prev != NULL)
    del_node->prev->next = del_node->next;

free(del);

حذف گره داخلی

فرض کنید گره‌‌ای که می‌خواهیم حذفش کنیم، گره 2 باشد و آن‌را del_node بنامیم. اگر del_node یک گره داخلی (گره دوم) باشد، باید مقدار next و prev گره‌های قبل و بعد از del_node را بازنشانی کنیم؛ برای گره قبل از del_node (یعنی اولین گره) مقدار next گره del_node را به next گره اول اختصاص دهید و برای گره بعد از del_node (یعنی گره سوم) مقدار prev گره del_node را به prev گره سوم اختصاص دهید.

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

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

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

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

if (del_node->next != NULL)
    del_node->next->prev = del_node->prev;

if (del_node->prev != NULL)
    del_node->prev->next = del_node->next;

حذف آخرین گره از لیست پیوندی دوطرفه

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

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

لیست پیوندی دوطرفه پس از حذف گره 3، به صورت زیر خواهد بود:

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

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

if (del_node->prev != NULL)
    del_node->prev->next = del_node->next;

پیچیدگی زمانی و فضایی

پیچیدگی عملیات درج

پیچیدگی عملیات حذف

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

در ادامه، قطعه کد پیاده سازی لیست پیوندی دوطرفه در زبان پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته آمده است:

import gc

# node creation

class Node:

    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


class DoublyLinkedList:

    def __init__(self):
        self.head = None

    # insert node at the front
    def insert_front(self, data):

        # allocate memory for newNode and assign data to newNode
        new_node = Node(data)

        # make newNode as a head
        new_node.next = self.head

        # assign null to prev (prev is already none in the constructore)

        # previous of head (now head is the second node) is newNode
        if self.head is not None:
            self.head.prev = new_node

        # head points to newNode
        self.head = new_node

    # insert a node after a specific node
    def insert_after(self, prev_node, data):

        # check if previous node is null
        if prev_node is None:
            print(“previous node cannot be null”)
            return

        # allocate memory for newNode and assign data to newNode
        new_node = Node(data)

        # set next of newNode to next of prev node
        new_node.next = prev_node.next

        # set next of prev node to newNode
        prev_node.next = new_node

        # set prev of newNode to the previous node
        new_node.prev = prev_node

        # set prev of newNode’s next to newNode
        if new_node.next:
            new_node.next.prev = new_node

    # insert a newNode at the end of the list
    def insert_end(self, data):

        # allocate memory for newNode and assign data to newNode
        new_node = Node(data)

        # assign null to next of newNode (already done in constructor)

        # if the linked list is empty, make the newNode as head node
        if self.head is None:
            self.head = new_node
            return

        # store the head node temporarily (for later use)
        temp = self.head

        # if the linked list is not empty, traverse to the end of the linked list
        while temp.next:
            temp = temp.next

        # now, the last node of the linked list is temp

        # assign next of the last node (temp) to newNode
        temp.next = new_node

        # assign prev of newNode to temp
        new_node.prev = temp

        return

    # delete a node from the doubly linked list
    def deleteNode(self, dele):

        # if head or del is null, deletion is not possible
        if self.head is None or dele is None:
            return

        # if del_node is the head node, point the head pointer to the next of del_node
        if self.head == dele:
            self.head = dele.next

        # if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node
        if dele.next is not None:
            dele.next.prev = dele.prev

        # if del_node is not the first node, point the next of the previous node to the next node of del_node
        if dele.prev is not None:
            dele.prev.next = dele.next

        # free the memory of del_node
        gc.collect()

    # print the doubly linked list
    def display_list(self, node):

        while node:
            print(node.data, end=”->”)
            last = node
            node = node.next


# initialize an empty node
d_linked_list = DoublyLinkedList()

d_linked_list.insert_end(5)
d_linked_list.insert_front(1)
d_linked_list.insert_front(6)
d_linked_list.insert_end(9)

# insert 11 after head
d_linked_list.insert_after(d_linked_list.head, 11)

# insert 15 after the seond node
d_linked_list.insert_after(d_linked_list.head.next, 15)

d_linked_list.display_list(d_linked_list.head)

# delete the last node
d_linked_list.deleteNode(d_linked_list.head.next.next.next.next.next)

print()
d_linked_list.display_list(d_linked_list.head)

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

جمع بندی

لیست پیوندی دو طرفه (Doubly Linked List)، نوع خاصی از لیست پیوندی است که در آن، هر گره دارای اشاره‌گر به گره قبلی و همچنین گره بعدی در لیست پیوندی است. در این مقاله با این نوع لیست پیوندی آشنا شدیم و همین‌طور به بررسی و پیاده‌سازی عملیات‌های اساسی آن پرداختیم؛ همچنین با کاربردها و پیچیدگی‌های زمانی و فضایی و پیاده‌سازی آن آشنا شدیم.

لیست پیوندی دوطرفه چیست؟

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

لیست پیوندی دوطرفه برای چه مواردی استفاده می شود؟

به طور کلی، لیست پیوندی برای سیستم‌های ناوبری که در آن ناوبری به جلو و عقب مورد نیاز است، مرورگرهای وب برای پیمایش به عقب و جلو در صفحات وب، LRU (کمترین استفاده اخیر)/MRU (اخیراً استفاده شده) حافظه نهان، توسط برنامه‌های مختلف برای حفظ عملکردهای لغو و مجدد و در سیستم‌عامل‌ها، برای پیگیری فرآیندهایی که در آن زمان اجرا می‌شوند، مورد استفاده قرار می‌گیرد.

مزایای لیست پیوندی دوطرفه چیست؟

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

معایب لیست پیوندی دوطرفه چیست؟

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

آرایه بهتر است یا لیست پیوندی دوطرفه؟

در آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100آموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100در این مقاله موارد زیر بررسی شده است : 1- آرایه چیست 2- انواع اندیس گذاری در آرایه 3- انواع آرایه 4- محاسبه آدرس در آرایه 5- محاسبه شماره در آرایه 6- آرایه در برنامه نویسی 7- مزایای استفاده از آرایه انجام هر عملیاتی مانند درج، حذف و غیره، زمان بیشتری می‌برد. لیست پیوندی هنگام انجام هر عملیاتی مانند درج، حذف و غیره زمان کمتری می‌برد. دسترسی به هر عنصر در یک آرایه سریع‌تر است؛ زیرا عنصر موجود در یک آرایه می‌تواند مستقیماً از طریق اندیس قابل دسترسی باشد.

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (1 امتیاز)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام