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)
-
11 vụ hack gây chấn động nước Mỹ trong thập kỷ qua
-
Chỉn chu hay chỉnh chu, từ nào là đúng chính tả?
-
Kích thước ảnh chuẩn trên Pinterest là bao nhiêu?
-
10 vạn lượng vàng tương đương 500kg, người xưa lấy đâu ra nhiều vàng mà ban thưởng vậy?
-
Đồ cho Jax DTCL, Jax Chiến Binh Thiết Giáp mùa 5 DTCL
-
Acer Swift 7 hay HP Elite Dragonfly là laptop siêu di động cao cấp tốt nhất?
-
Công thức tính thể tích hình chóp cụt, diện tích xung quanh và toàn phần của hình chóp cụt
-
Công thức tính diện tích hình Elip
-
Các công thức đạo hàm và đạo hàm lượng giác đầy đủ nhất
-
Cách tính diện tích hình tròn và chu vi hình tròn
-
Công thức tính diện tích xung quanh hình nón, diện tích toàn phần hình nón, thể tích hình nón
-
Công thức tính diện tích hình lập phương, thể tích hình lập phương
-
Giải thuật sắp xếp chọn (Selection Sort)
-
Công thức tính diện tích xung quanh hình trụ, diện tích toàn phần hình trụ, thể tích hình trụ
-
Giải thuật Định lý thợ (Master Theorem)