Danh sách liên kết đôi là gì? Cấu trúc dữ liệu của nó

Posted on by mtoplistChuyên mục:Top List

Trong hướng dẫn này, mình sẽ giới thiệu các bạn một trong các danh sách liên kết thường gặp là danh sách liên kết đôi.

test php

banquyen png

Bài viết này được đăng tại

freetuts.net

, không được copy dưới mọi hình thức.

Khi các bạn nắm được thành thạo danh sách liên kết đơn thì việc học danh sách liên kết đôi rất đơn giản. Về cơ bản nó là một danh sách liên kết đơn, vì vậy các bạn hãy học DSLK đơn trước khi qua bài này nhé.

1. Danh sách liên kết đôi là gì?

Danh sách liên kết đôi (Doubly linked list) là danh sách liên kết mà mỗi phần tử có hai liên kết đến phần tử liền trước và liền sau nó.

Khi duyệt các nút sẽ thực hiện theo hai chiều về trước và về sau thay vì thực hiền duyệt một chiều như danh sách liên kết đơn.

Bài viết này được đăng tại [free tuts .net]

doubly linked list png

Danh sách liên kết đôi có các thông số cần quan tâm:

  • Giá trị (data).
  • Mối liên kết tới Node khác (pPre và pNext).

Ở mối liên kết tới Node khác, thay vì chỉ có mỗi pNext trỏ tới phần tử sau nó như DSLK đơn, thì trong DSLK đôi cần có thêm pPrev để trỏ tới phần tử trước nó.

2. Cấu trúc dữ liệu của danh sách liên kết đôi

Tương tự như danh sách liên kết đơn, trong DSLK đôi cũng có cấu trúc dữ liệu, đây là điều kiện cần để có thể thực hiện các thao tác trên danh sách liên kết đôi.

Cấu trúc của một Node

dslk doi 1 PNG

Trong Node có:

  • Data là giá trị của Node.
  • pPre là con trỏ, trỏ tới phần tử liền trước.
  • pNext là con trỏ, trỏ tới phần tử liền sau.

Tổ chức biểu diễn một Node của danh sách liên kết đôi.

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

Cấu trúc danh sách liên kết đôi

dslk doi 2 PNG

Ta có:

  • pHead là Node đầu tiên trong DSLK đôi, nó luôn luôn quản lý Node đầu.
  • pTail là Node cuối cùng trong DSLK đôi, nó luôn luôn quản lý Node cuối.
  • Node B có hai con trỏ, trỏ đến A và C, tương tự các Node khác cũng vậy.

Khai báo con trỏ đầu danh sách:

/* Khai báo Node đầu pHead và Node cuối pTail*/
struct SingleList
{
  Node *pHead; //Node đầu pHead
  Node *pTail; // Node cuối pTail
};

Khởi tạo giá trị cho pHead và pTail:

void Initialize(SingleList &list)
{
  list.pHead=list.pTail=NULL;// khởi tạo giá trị cho Node đầu và Node cuối là Null
}

3. Các thao tác trong danh sách liên kết đôi

Trong danh sách liên kết đôi cũng có các thao tác tương tự như danh sách liên kết đơn, các thao tác này được sử dụng rất nhiều khi làm việc với DSLK.

  • Tạo Node mới trong DSLK đôi
  • Chèn Node trong DSLK đôi
  • Xoa Node trong DSLK đôi
  • Duyệt DSLK đôi
  • Tìm kiếm và sắp xếp trong DSLK đôi

Chèn Node trong danh sách liên kết đôi có hai trường hợp là: chèn vào đầu, chèn vào cuối.

Xóa Node trong danh sách liên kết đôi cũng có hai trường hợp là: xóa ở đầu và xóa ở cuối.

Ở DSLK đơn việc duyệt danh sách thực hiện duyệt từ đầu đến cuối, riêng DSLK đôi có thể thực hiện duyệt từ cuối về đầu.

4. Kết luận

Như vậy là mình đã giới thiệu về danh sách liên kết đôi, cấu trúc dữ liệu của nó và các thao tác trong danh sách. Khi làm việc với DSLK đôi, các bạn chú ý rằng nó có mối liên kết hai chiều, vì vậy các bạn hãy cận thận khi thay đổi mối liên kết của nó. Ở các bài tiếp theo mình sẽ thực hiện lần lượt các thao tác trong danh sách. Các bạn hãy chú ý theo dõi nhé!!!

mtoplist