Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng 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é.
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]
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
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
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é!!!
