Cấu trúc dữ liệu danh sách liên kết đôi
Danh sách liên kết đôi (Doubly Linked List) là gì?
Danh sách liên kết đôi (Doubly Linked List) là một biến thể của Danh sách liên kết (Linked List), trong đó hoạt động duyệt qua các nút có thể được thực hiện theo hai chiều: về trước và về sau một cách dễ dàng khi so sánh với Danh sách liên kết đơn. Dưới đây là một số khái niệm quan trọng cần ghi nhớ về Danh sách liên kết đôi.
Link: mỗi link của một Danh sách liên kết có thể lưu giữ một dữ liệu và được gọi là một phần tử.
Next: mỗi link của một Danh sách liên kết có thể chứa một link tới next link và được gọi là Next.
Prev: mỗi link của một Danh sách liên kết có thể chứa một link tới previous link và được gọi là Prev.
First và Last: một Danh sách liên kết chứa link kết nối tới first link được gọi là First và tới last link được gọi là Last.
Biểu diễn Danh sách liên kết đôi
Như hình minh họa trên, bạn cần ghi nhớ:
Danh sách liên kết đôi chứa một phần tử link và được gọi là First và Last.
Mỗi link mang một trường dữ liệu và một trường link được gọi là Next.
Mỗi link được liên kết với phần tử kế tiếp bởi sử dụng Next Link.
Mỗi link được liên kết với phần tử phía trước bởi sử dụng Prev Link.
Last Link mang một link trỏ tới NULL để đánh dầu phần cuối của Danh sách liên kết.
Các hoạt động cơ bản trên Danh sách liên kết đôi
Hoạt động chèn: thêm một phần tử vào vị trí đầu của Danh sách liên kết.
Hoạt động xóa: xóa một phần tử tại vị trí đầu của Danh sách liên kết.
Hoạt động chèn vào cuối: thêm một phần tử vào vị trí cuối của Danh sách liên kết.
Hoạt động xóa phần tử cuối: xóa một phần tử tại vị trí cuối của Danh sách liên kết.
Hoạt động chèn vào sau: thêm một phần tử vào sau một phần tử của Danh sách liên kết.
Hoạt động xóa (bởi key): xóa một phần tử từ Danh sách liên kết bởi sử dụng khóa đã cung cấp.
Hiển thị danh sách về phía trước: hiển thị toàn bộ Danh sách liên kết theo chiều về phía trước.
Hiển thị danh sách về phía sau: hiển thị toàn bộ Danh sách liên kết theo chiều về phía sau.
Hoạt động chèn trong Danh sách liên kết đôi
Phần dưới đây là giải thuật minh họa cho hoạt động chèn tại vị trí đầu của một Danh sách liên kết đôi.
//Chèn link tại vị trí đầu tiên void insertFirst(int key, int data) { //tạo một link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if(isEmpty()) { //Biến nó thành last link last = link; }else { //Cập nhật prev link đầu tiên head->prev = link; } //Trỏ nó tới first link cũ link->next = head; //Trỏ first tới first link mới head = link; }
Để tìm hiểu chi tiết code minh họa của danh sách liên kết đôi trong ngôn ngữ C, mời bạn click chuột vào chương: Chương trình danh sách liên kết đôi trong C.
Theo Tutorialspoint
Bài trước: Cấu trúc dữ liệu danh sách liên kết (Linked List)
Bài tiếp: Cấu trúc dữ liệu Danh sách liên kết vòng (Circular Linked List)

- Kiến trúc dữ liệu Rational DA và DB2 9: Xây dựng một lệnh SQL
- Cách tạo và xóa danh sách phát video trên YouTube
- Cách chỉnh sửa và chia sẻ danh sách phát Youtube
- Cấu trúc dữ liệu và giải thuật có cần thiết với một Web Developer không?
- Cấu trúc dữ liệu (Data Structure) là gì?
- Cấu trúc dữ liệu mảng
- Cấu trúc dữ liệu danh sách liên kết (Linked List)
-
Build Cuồng Long DTCL, cách chơi 9 Cuồng Long mùa 7
-
Nhật ký "tập đoàn" hacker Conti, Phần 4: Tấn công thị trường tiền số
-
Chromebook hiện có thể cảnh báo người dùng khi kết nối với cáp USB Type C “không phù hợp"
-
5 tựa game giải trí thú vị trong Linux Terminal
-
Mẹo hoàn tác tin nhắn đang gửi trên iPhone
-
Google Project Zero tiết lộ lỗ hổng USB có mức độ nghiêm trọng cao trong Chrome OS
-
Cây tìm kiếm nhị phân (Binary Search Tree)
-
Cài đặt môi trường trong Cấu trúc dữ liệu
-
Các công thức đạo hàm và đạo hàm lượng giác đầy đủ nhất
-
Số hữu tỉ là gì? Số vô tỉ là gì?
-
Giải thuật sắp xếp trong cấu trúc dữ liệu & giải thuật
-
Giải thuật tìm kiếm tuyến tính (Linear Search)
-
Cấu trúc dữ liệu đồ thị (Graph)
-
Mật độ dân số là gì? Công thức tính mật độ dân số
-
Công thức tính diện tích hình hộp chữ nhật