DANH SÁCH LIÊN KẾT ĐÔI
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

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

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.

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é.

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.

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.

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é!!!

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Top