Xây dựng danh sách liên kết kép (Doubly Linked List) với con trỏ (pointer)

1. Định nghĩa danh sách liên kết kép

Danh sách liên kết kép (doubly linked list) có đặc điểm là mỗi phần tử liên kết với phần tử đứng trước và đứng sau nó trong danh sách.

Giả sử, chúng ta tạo ra một danh sách liên kết kép lưu trữ một dãy số nguyên như sau:

struct dNode{
	int info;
	struct dNode *pre;
	struct dNode *next;
};

struct dList{
	dNode *head;
	dNode *tail;
};

Mỗi node có thêm một con trỏ *pre để lưu trữ địa chỉ của node đứng trước nó. Đó là sự khác biệt lớn nhất của danh sách liên kết kếp so với danh sách liên kết đơn.

2. Các thao tác cơ bản trên danh sách liên kết kép

Cũng giống như danh sách liên kết đơn, danh sách liên kết kép cũng có những thao tác cơ bản như là thêm node, hủy node, duyệt danh sách, sắp xếp node,…

Tạo một danh sách liên kết kép rỗng

void createsList(dList &l){
	l.head = NULL;
	l.tail = NULL;
}

Tạo một node và gán giá trị cho node

dNode* createdNode(int x){
	dNode *p;
	p = new dNode;
	if(p==NULL){
		cout<<"khong con du bo nho";
		exit(1);
	}else{
		p->info=x;
		p->next=NULL;
		p->pre=NULL;
		return p;
	}
}

Thêm một node vào đầu danh sách

void insertHead(dList &l, int x){
	dNode *p;
	p = createdNode(x);
	if(p==NULL){
		cout<<"Khong tao duoc node!";
		exit(1);
	}
	if(l.head==NULL){//trường hợp danh sách rỗng
		l.head = p;
		l.tail = l.head;
	}else{//trường hợp danh sách không rỗng
		p->next = l.head;
		l.head->pre = p;
		l.head = p;
	}
}

Thêm một node vào cuối danh sách

void insertTail(dList &l, int x){
	dNode *p = createdNode(x);
	if(p==NULL){
		cout<<"Khong tao duoc nut moi!";
		exit(1);
	}
	if (l.head==NULL){//trường hợp danh sách rỗng
		l.head = p;
		l.tail = l.head;
	}else{//trường hợp danh sách không rỗng
		p->pre=l.tail;
		l.tail->next=p;
		l.tail=p;
	}
}

Duyệt các phần tử trong danh sách

void processList(dList &l){
	dNode *p;
	p = l.head;
	while (p!= NULL){
		cout<<p->info<<endl;//xuất giá trị trong node
		p = p->next;
	}
}

Hủy node đầu tiên trong danh sách

void DeleteFirst(dList &l){
	dNode *p;
	if(l.head!=NULL){
		p=l.head;
		l.head=l.head->next;
		l.head->pre=NULL;
		delete p;
		if(l.head==NULL){
			l.tail=NULL;
		}
	}
}

Hủy node cuối cùng trong danh sách

void DeleteEnd(dList &l ){
	dNode *p;
	if(l.head!=NULL){
		p=l.tail;
		l.tail=l.tail->pre;
		l.tail->next=NULL;
		delete p;
		if(l.tail==NULL){
			l.head=NULL;
		}
	}
}

Hủy toàn bộ danh sách

void deleteList(dList &l){
	dNode *p;
	while (l.head!= NULL){
		p = l.head;
		l.head = l.head->next;
		delete p;
	}
	l.tail = NULL;
}

Sắp xếp các node trong danh sách

void List_Interchange_Sort(dList &l){
	dNode *p,*q;
	p=l.head;
	while(p!=l.tail){
		q=p->next;
		while(q!=NULL){
			if(p->info>q->info){
				swap(p->info, q->info);
			}
			q=q->next;
		}
		p=p->next;
	}
}

3. Bài tập

Bên dưới là hình minh họa một danh sách liên kết kép.

Hãy viết chương trình với C++ với các yêu cầu trên danh sách liên kết kép ở trên:

a. Tạo danh sách liên kết kép như hình minh họa.

b. Thêm một node có giá trị là 9 vào đầu danh sách.

c. Xuất giá trị và địa chỉ của các node trong danh sách lên màn hình.

d. Sắp xếp danh sách theo thứ tự tăng dần các giá trị của các node.

e. Giải phóng bộ nhớ cho toàn bộ danh sách.