Trong cấu trúc dữ liệu, Danh sách liên kết (Linked List) là tập hợp tuyến tính các phần tử dữ liệu. Mỗi phần tử hoặc nút của danh sách bao gồm hai mục - dữ liệu và tham chiếu đến nút tiếp theo. Nút cuối cùng có tham chiếu đến null. Điểm vào của danh sách liên kết được gọi là đầu (head) của danh sách.
Danh sách liên kết kép (Doubly Linked List) bao gồm một tập hợp các bản ghi liên kết tuần tự gọi là nút. Mỗi nút chứa ba trường: một trường dữ liệu và hai trường liên kết; tham chiếu đến nút trước và nút tiếp theo trong chuỗi nút.
Trong trường hợp danh sách liên kết kép đã sắp xếp, theo giá trị của các trường dữ liệu đã sắp xếp, danh sách liên kết sẽ vẫn giữ thứ tự đã sắp xếp.
Thuật toán
Bắt đầu
Hàm createnode() để chèn nút vào danh sách:
Tạo newnode và chèn số vào trường data của newnode.
Kiểm tra danh sách có rỗng không. Nếu rỗng, đặt nút làm phần tử đầu tiên và cập nhật head.
Cả con trỏ prev và next đều được khởi tạo với NULL.
Nếu danh sách không rỗng, newnode sẽ được chèn vào danh sách liên kết hiện có sao cho cuối cùng danh sách vẫn giữ thứ tự đã sắp xếp.
Con trỏ prev và next sẽ được cập nhật tương ứng.
Kết thúc
Bắt đầu
Hàm display_head() để hiển thị danh sách từ head:
Khởi tạo c=0.
Khởi tạo biến con trỏ với địa chỉ nút head.
while (c <= i)
In thông tin nút
Cập nhật biến con trỏ
Tăng c.
Kết thúc
Bắt đầu
Hàm display_tail() để hiển thị danh sách từ tail:
Khởi tạo m=0.
Khởi tạo biến con trỏ với địa chỉ nút tail.
while (m <= i)
In thông tin nút
Cập nhật biến con trỏ
Tăng m.
Kết thúc
Mã ví dụ
#include <iostream>
using namespace std;
struct nod {
int d;
nod *n, *p;
} *p = NULL, *head = NULL, *r = NULL, *np = NULL, *tail = NULL;
int c = 0;
void createnode(int n) {
np = new nod;
np->d = n;
np->n = NULL;
np->p = NULL;
if (c == 0) {
tail = np;
head = np;
p = head;
p->n = head;
p->p = head;
c++;
} else if (c == 1) {
p = head;
r = p;
if (np->d < p->d) {
np->n = p;
p->p = np;
head = np;
p->n = np;
np->p = p;
tail = p;
} else if (np->d > p->d) {
p->n = np;
np->p = p;
np->n = head;
p->p = np;
}
c++;
} else {
p = head;
r = p;
if (np->d < p->d) {
np->n = p;
p->p = np;
head = np;
do {
p = p->n;
} while (p->n != r);
tail = p;
p->n = np;
np->p = p;
} else if (np->d > p->d) {
while (p->n != head && np->d > p->d) {
r = p;
p = p->n;
if (p->n == head && (p->d < np->d)) {
p->n = np;
np->p = p;
np->n = head;
tail = np;
head->p = np;
break;
} else if (np->d < p->d) {
r->n = np;
np->p = r;
np->n = p;
p->p = np;
if (p->n != head) {
do {
p = p->n;
} while (p->n != head);
}
tail = p;
break;
}
}
}
}
}
void display_head(int i) {
nod *t = head;
int c = 0;
while (c <= i) {
cout << t->d << "\t";
t = t->n;
c++;
}
cout << endl;
}
void display_tail(int i) {
nod *t = tail;
int m = 0;
while (m <= i) {
cout << t->d << "\t";
t = t->p;
m++;
}
cout << endl;
}
int main() {
int i = 0, n, a, ch;
cout << "Nhập số nút:\n";
cin >> n;
while (i < n) {
cout << "\nNhập giá trị nút:\n";
cin >> a;
createnode(a);
i++;
}
cout << "\nDanh sách liên kết kép đã sắp xếp - head first:\n";
display_head(n);
cout << "\nDanh sách liên kết kép đã sắp xếp - tail first:\n";
display_tail(n);
return 0;
}
Kết quả đầu ra
Nhập số nút: 5 Nhập giá trị nút: 7 Nhập giá trị nút: 4 Nhập giá trị nút: 6 Nhập giá trị nút: 2 Nhập giá trị nút: 1 Danh sách liên kết kép đã sắp xếp - head first 1 2 4 6 7 1 Danh sách liên kết kép đã sắp xếp - tail first 7 6 4 2 1 7