Danh sách liên kết đơn là một trong những kiến thức lập trình đơn giản để bạn có thể tạo được cơ sở dữ liệu cho phần mềm của bạn. Việc ứng dụng danh sách liên kết sẽ làm cho dữ liệu của bạn được linh động hơn, tiết kiệm được rất nhiều bộ nhớ, không bị giới hạn bởi yếu tố dung lượng dữ liệu.

     Danh sách liên kết ra đời nhằm mục đích khắc phục những hạn chế còn tồn tại trong mảng. Với danh sách liên kết này, bạn có thể tăng thêm hay giảm bớt cơ sở dữ liệu mà không cần phải mất nhiều công sức để tái tạo lại dữ liệu. Ưu điểm của danh sách liên kết đơn sẽ là nhược điểm của mảng hiện tại mà bạn đang gặp phải khi thiết kế những cơ sở dữ liệu lớn. Ngoài ta, các bạn cũng có thể xem thêm kiểu dữ liệu struct trong C, cũng tương tự như dạng danh sách này.

     Ưu điểm:

• Danh sách liên kết đơn trong lập trình C++ không cần bạn phải khai báo một vùng nhớ cố định giống như mảng, việc khai báo vùng nhớ cố định sẽ làm cho chương trình bạn chạy không ổn định và có sự lãng phí vùng nhớ rất nhiều. Giả sử bạn khai báo vùng nhớ quá nhiều nhưng khi người dùng sử dụng chỉ cần vài ô nhớ thì điều này gây ra sự lãng phí, còn nếu bạn khai báo ít ô nhớ thì khi người dùng sử dụng nhiều hơn sẽ không đủ vùng nhớ dẫn đến việc chương trình chạy sai. Đối với danh sách liên kết thì khi người dùng cần bao nhiêu chương trình sẽ tự động tìm trong vùng nhớ có đủ ô nhớ để cấp phát hay không, người dùng cần bao nhiêu sẽ cấp bấy nhiêu tránh lãng phí.
• Danh sách liên kết đơn trong lập trình C++ không cần phải có các ô nhớ trống liền kề. Đối với mảng khi khai báo bao nhiêu ô nhớ thì chương trình bắt buộc phải tìm ra vùng nhớ với bấy nhiêu ô nhớ trống liền kề nhau, nếu không liền kề thì sẽ không được cấp phát, điều này cũng gây khó khăn cho quá trình lập trình nếu dung lượng đang sử dụng còn ít.
• Danh sách liên kết có thể thực hiện thao tác thêm hoặc xóa dữ liệu một cách nhanh chóng, nhanh hơn nhiều so với việc thực hiện các thao tác trên mảng. Việc thêm phần tử mới vào danh sách bạn chỉ cần tạo mối liên kết với phần tử đó và gắn kết phần tử đó với phần tử tiếp theo trong danh sách. Tương tự như vậy, muốn xóa phần tử nào trong danh sách các bạn chỉ cần cắt mối liên kết của phần tử đó ra khỏi danh sách.

    I. Các bước để thực hiện được một danh sách liên kết đơn trong lập trình C++

     Bước 1: Khai báo cấu trúc của 1 Node

     Danh sách liên kết là sự kết hợp của nhiều Node lại với nhau, mỗi một Node được cấu thành bởi 2 thành phần chính đó là dữ liệu (Data) và con trỏ để trỏ (pNext) để trỏ đến phần tử kế tiếp.

//1. Khai bao cau truc cua Node
struct Node
{
	int Data;
	Node *pNext;
};
typedef struct Node NODE;

     Trong cấu trúc của Node có chứa con trỏ pNext có thể trỏ đến chính cấu trúc đang được khai báo, do vậy cấu trúc Node là 1 câú trúc tự trỏ.

     Bước 2: Khai báo cấu trúc của danh sách

     Tập hợp nhiều Node lại với nhau và có thứ tự xác định chính là cấu trúc của 1 danh sách, tuy nhiên điều cơ bản là phải có 2 Node cần phải xác định đó là phần tử đầu tiên của danh sách pHead và phần tử cuối cùng của danh sách là pTail. Do vậy, khai báo câú trúc của danh sách chúng ta cần phải khai báo 2 thành phần đó là pHead và pTail.

//2. Khai bao cau truc cua 1 danh sach
struct List
{
	NODE *pHead;
	NODE *pTail;
};
typedef struct List LIST;

      Bước 3: Khởi tạo danh sách

     Nguyên tắc chung khi khai báo một con trỏ thì cần phải gán giá trị ban đầu cho con trỏ là NULL, nếu không thì con trỏ sẽ chưa được khởi tạo, do đó chúng ta cần phải có chương trình khởi tạo danh sách. Mục đích của chương trình này là cho con phần tử pHead và pTail phải được tồn tại.

//3. Khoi tao danh sach
void KhoiTao(LIST &l)
{
	l.pHead=l.pTail=NULL;
}

      Bước 4: Tạo Node

     Bản thân Node là một cấu trúc bao gồm 2 thành phần, do vậy cần thực hiện thao tác đưa dữ liệu vào Data và khởi tạo mối liên kết pNext.

//4. Ham nhap gia tri cho NODE
NODE *GetNode(int x)
{
	NODE *p;
	p=new NODE;
	if(p==NULL)
		cout<<"Khong cap phat duoc con tro p"<<endl;
	else
	{
		p->Data=x;
		p->pNext=NULL;
	}
	return p;
}

     Bước 5: Thêm phần tử vào danh sách

     Việc đưa từng phần tử vào danh sách sẽ được thực hiện theo 2 cách, đưa phần tử mới vào trước phần tử đã có hay đưa phần tử mới vào sau phần tử đã có của danh sách. Việc đưa phần vào trước hoặc sau là do người dùng lựa chọn, và tùy theo nhu cầu của người sử dụng.

//5-1. Ham them node vao sau node dau
void ThemSau(LIST &l,NODE *p)
{
	if(l.pHead==NULL)
		l.pHead=l.pTail=p;
	else
	{
		l.pTail->pNext=p;
		l.pTail=p;
	}
}
//5-2. Ham them node va truoc
void ThemTruoc(LIST &l,NODE *p)
{
	if(l.pHead==NULL)
		l.pHead=l.pTail=p;
	else
	{
		p->pNext=l.pHead;
		l.pHead=p;
	}
}

     Bước 6: Nhập danh sách

     Trong bước này ta thực hiện chức năng ghép nối các bước trên để có được một danh sách hoàn chỉnh. Bạn cần bao nhiêu Node cho danh sách thì bạn khai báo cho chương trình bấy nhiêu và lần lượt ghép các Node lại với nhau để được một danh sách hoàn chỉnh.

//6. Nhap danh sach lien ket
void Nhap(LIST &l,int N)
{
	int i, x;
	NODE *p;
	KhoiTao(l);
	for(i=1;i<=N;i++)
	{
		cout<<"Nhap vao gia tri cua node thu "<<i<<" ";
		cin>>x;
		p=GetNode(x);
		ThemSau(l,p);
	//	ThemTruoc(l,p);
	}
}

     Bước 7: In danh sách

     Giống như mảng, sau khi đã hoàn thành công việc nhập dữ liệu cho danh sách thì chúng ta cần in danh sách ra màn hình để người dùng có thể biết được chương trình đã nhập được những gì. Và nội dung danh sách có đúng như mong muốn hay không.

//7. In danh sach ra man hinh
void Xuat(LIST l)
{
	NODE *p;
	for(p=l.pHead; p!=NULL;p=p->pNext)
		cout<<p->Data<<"   ";
}

     Bước 8: Thực hiện những yêu cầu của chương trình

     Danh sách liên kết chỉ là sự gắn kết của các Node theo một trật tự nhất định. Chúng ta còn thực hiện các yêu cầu khác của chương trình, những yêu cầu đó của chương trình có thể là sắp xếp, chèn thêm phần tử, tìm giá trị lớn nhất hoặc nhiều yêu cầu khác của chương trình.

a. Chương trình tìm giá trị lớn nhất trong danh sách

void TimMAX(LIST l)
{
	NODE *p;
	int max;
	max=l.pHead->Data;
	for(p=l.pHead->pNext;p!=NULL;p=p->pNext)
		if(max < p->Data)
			max=p->Data;
	cout<<"GTLN= "<<max;
}

b. Chương trình sắp xếp danh sách tăng dần

void SapXepTang(LIST &l)
{
	int tam;
	NODE *p, *q;
	for(p=l.pHead; p!=l.pTail; p=p->pNext)
		for(q=p->pNext;q!=NULL;q=q->pNext)
			if( p->Data > q->Data)
			{
				tam=p->Data;
				p->Data=q->Data;
				q->Data=tam;
			}
}

c. Chương trình thêm 1 phần tử mới vào đầu danh sách

void ThemDau(LIST &l,int &N)
{
	int x;
	NODE *p;
	cout<<"Nhap vao phan tu can them"<<endl;
	cin>>x;
	p=GetNode(x);

	p->pNext=l.pHead;
	l.pHead=p;
	N++;
}

d. Chương trình thêm 1 phần tử mới vào cuối danh sách

void ThemCuoi(LIST &l, int &N)
{
	int x;
	NODE *p;
	cout<<"Nhap vao phan tu can them"<<endl;
	cin>>x;
	p=GetNode(x);

	l.pTail->pNext=p;
	l.pTail=p;
	N++;
}

e. Chương trình thêm 1 phần tử mới vào sau 1 phần tử xác định trong danh sách

void ThemSauMotNode(LIST &l,int &N)
{
	int x,t, kt=0;
	NODE *p, *q, *k, *g;
	//Chen Node p vao ngay sau Node q trong danh sach
	cout<<"Nhap phan tu can chen"<<endl;
	cin>>x;
	p=GetNode(x);

	cout<<"Nhap vao phan tu q can tim"<<endl;
	cin>>t;
	q=GetNode(t);

	for(k=l.pHead;k!=NULL;k=k->pNext)
		if(k->Data == q->Data)
			kt=1;
	if(kt==0)
		cout<<"Khong co phan tu can xac dinh vi tri"<<endl;
	else
	{
		for(k=l.pHead;k!=NULL;k=k->pNext)
			if(k->Data == q->Data)
			{
				g=k->pNext;
				k->pNext=p;
				p->pNext=g;
			}
		N++;
	}
}

f. Chương trình xóa phần tử đầu trong danh sách

void XoaDau(LIST &l,int &N)
{
	NODE *p;
	p=l.pHead;

	l.pHead=l.pHead->pNext;
	delete p;
	N--;
}

g. Chương trình xóa phần tử cuối của danh sách

void XoaCuoi(LIST &l, int &N)
{
	NODE *p, *k;
	for(k=l.pHead;k!=NULL;k=k->pNext)
		if(k== l.pTail)
		{
			l.pTail=p;
			l.pTail->pNext=NULL;
			delete k;
			return;
		}
		else
			p=k;
}

h. Chương trình xoá một phần tử nằm sau 1 phần tử xác định trong danh sách

void XoaSau(LIST &l,int &N)
{
	int x;
	NODE *p, *k, *g;

	cout<<"Nhap phan tu danh dau vi tri xoa: "<<endl;
	cin>>x;

	for(k=l.pHead;k!=NULL;k=k->pNext)
		if(k->Data==x)
		{
			g=k->pNext;
			k->pNext=g->pNext;
			delete g;
			N--;
			return;
		}
}

i. Chương trình xóa phần tử bất kỳ trong danh sách

void XoaBatKy(LIST &l, int &N)
{
	int x;
	NODE *k,*p;
	cout<<"Nhap phan tu can xoa: "<<endl;
	cin>>x;

	
	if(l.pHead->Data ==x)
			XoaDau(l,N);
	else if
		(l.pTail->Data ==x)
			XoaCuoi(l,N);
	else
	{
		for(k=l.pHead; k!=NULL;k=k->pNext)
		{
			if(k->Data ==x)
				{
					p->pNext=k->pNext;
					delete k;
					N--;
					return;
				}
			p=k;
		}
	}
}

 

II. Chương trình hoàn chỉnh

#include<iostream>

using namespace std;

//1. Khai bao cau truc cua Node
struct Node
{
	int Data;
	Node *pNext;
};
typedef struct Node NODE;

//2. Khai bao cau truc cua 1 danh sach
struct List
{
	NODE *pHead;
	NODE *pTail;
};
typedef struct List LIST;

//3. Khoi tao danh sach
void KhoiTao(LIST &l)
{
	l.pHead=l.pTail=NULL;
}
//4. Ham nhap gia tri cho NODE
NODE *GetNode(int x)
{
	NODE *p;
	p=new NODE;
	if(p==NULL)
		cout<<"Khong cap phat duoc con tro p"<<endl;
	else
	{
		p->Data=x;
		p->pNext=NULL;
	}
	return p;
}
//5-1. Ham them node vao sau node dau
void ThemSau(LIST &l,NODE *p)
{
	if(l.pHead==NULL)
		l.pHead=l.pTail=p;
	else
	{
		l.pTail->pNext=p;
		l.pTail=p;
	}
}
//5-2. Ham them node va truoc
void ThemTruoc(LIST &l,NODE *p)
{
	if(l.pHead==NULL)
		l.pHead=l.pTail=p;
	else
	{
		p->pNext=l.pHead;
		l.pHead=p;
	}
}

//6. Nhap danh sach lien ket
void Nhap(LIST &l,int N)
{
	int i, x;
	NODE *p;
	KhoiTao(l);
	for(i=1;i<=N;i++)
	{
		cout<<"Nhap vao gia tri cua node thu "<<i<<" ";
		cin>>x;
		p=GetNode(x);
		ThemSau(l,p);
	//	ThemTruoc(l,p);
	}
}
//7. In danh sach ra man hinh
void Xuat(LIST l)
{
	NODE *p;
	for(p=l.pHead; p!=NULL;p=p->pNext)
		cout<<p->Data<<"   ";
}

//Chuong trinh tim gia tri lon nhat trong danh sach
void TimMAX(LIST l)
{
	NODE *p;
	int max;
	max=l.pHead->Data;
	for(p=l.pHead->pNext;p!=NULL;p=p->pNext)
		if(max < p->Data)
			max=p->Data;
	cout<<"GTLN= "<<max;
}

//Chuong trinh sap xep danh sach tang dan
void SapXepTang(LIST &l)
{
	int tam;
	NODE *p, *q;
	for(p=l.pHead; p!=l.pTail; p=p->pNext)
		for(q=p->pNext;q!=NULL;q=q->pNext)
			if( p->Data > q->Data)
			{
				tam=p->Data;
				p->Data=q->Data;
				q->Data=tam;
			}
}

//Chuong trinh them 1 phan tu moi vao dau danh sach
void ThemDau(LIST &l,int &N)
{
	int x;
	NODE *p;
	cout<<"Nhap vao phan tu can them"<<endl;
	cin>>x;
	p=GetNode(x);

	p->pNext=l.pHead;
	l.pHead=p;
	N++;
}

//Chuong trinh them 1 phan tu moi vao cuoi danh sach
void ThemCuoi(LIST &l, int &N)
{
	int x;
	NODE *p;
	cout<<"Nhap vao phan tu can them"<<endl;
	cin>>x;
	p=GetNode(x);

	l.pTail->pNext=p;
	l.pTail=p;
	N++;
}

//Chuong trinh them 1 phan tu moi vao sau 1 phan tu trong danh sach
void ThemSauMotNode(LIST &l,int &N)
{
	int x,t, kt=0;
	NODE *p, *q, *k, *g;
	//Chen Node p vao ngay sau Node q trong danh sach
	cout<<"Nhap phan tu can chen"<<endl;
	cin>>x;
	p=GetNode(x);

	cout<<"Nhap vao phan tu q can tim"<<endl;
	cin>>t;
	q=GetNode(t);

	for(k=l.pHead;k!=NULL;k=k->pNext)
		if(k->Data == q->Data)
			kt=1;
	if(kt==0)
		cout<<"Khong co phan tu can xac dinh vi tri"<<endl;
	else
	{
		for(k=l.pHead;k!=NULL;k=k->pNext)
			if(k->Data == q->Data)
			{
				g=k->pNext;
				k->pNext=p;
				p->pNext=g;
			}
		N++;
	}
}

// Chuong trinh xoa phan tu dau trong danh sach
void XoaDau(LIST &l,int &N)
{
	NODE *p;
	p=l.pHead;

	l.pHead=l.pHead->pNext;
	delete p;
	N--;
}

// Chuong trinh xoa phan tu cuoi trong danh sach
void XoaCuoi(LIST &l, int &N)
{
	NODE *p, *k;
	for(k=l.pHead;k!=NULL;k=k->pNext)
		if(k== l.pTail)
		{
			l.pTail=p;
			l.pTail->pNext=NULL;
			delete k;
			return;
		}
		else
			p=k;
}

// Chuong trinh xoa 1 phan tu sau 1 phan tu xac dinh trong danh sach
void XoaSau(LIST &l,int &N)
{
	int x;
	NODE *p, *k, *g;

	cout<<"Nhap phan tu danh dau vi tri xoa: "<<endl;
	cin>>x;

	for(k=l.pHead;k!=NULL;k=k->pNext)
		if(k->Data==x)
		{
			g=k->pNext;
			k->pNext=g->pNext;
			delete g;
			N--;
			return;
		}
}

//Tim va xoa phan tu trong danh sach
void XoaBatKy(LIST &l, int &N)
{
	int x;
	NODE *k,*p;
	cout<<"Nhap phan tu can xoa: "<<endl;
	cin>>x;

	
	if(l.pHead->Data ==x)
			XoaDau(l,N);
	else if
		(l.pTail->Data ==x)
			XoaCuoi(l,N);
	else
	{
		for(k=l.pHead; k!=NULL;k=k->pNext)
		{
			if(k->Data ==x)
				{
					p->pNext=k->pNext;
					delete k;
					N--;
					return;
				}
			p=k;
		}
	}
}

int main()
{
	LIST l;
	int N, chon;
	do{
	cout<<"Ban can bao nhieu node: ";
	cin>>N;
	}while(N<=0 || N>=100);
	Nhap(l,N);
	cout<<"Danh sach vua nhap"<<endl;
	Xuat(l);

ST:	cout<<"\n---DANH SACH LUA CHON CHUONG TRINH"<<endl;
	cout<<"1. Tim gia tri lon nhat"<<endl;
	cout<<"2. Sap xep danh sach tang dan"<<endl;
	cout<<"3. Chen them 1 phan tu moi vao dau danh sach"<<endl;
	cout<<"4. Chen them 1 phan tu moi vao cuoi danh sach"<<endl;
	cout<<"5. Chen them 1 phan tu vao sau 1 phan tu xac dinh trong danh sach"<<endl;
	cout<<"6. Xoa 1 phan tu moi vao dau danh sach"<<endl;
	cout<<"7. Xoa 1 phan tu moi vao cuoi danh sach"<<endl;
	cout<<"8. Xoa 1 phan tu sau 1 phan tu xac dinh trong danh sach"<<endl;
	cout<<"9. Xoa 1 phan tu theo de bai yeu cau"<<endl;
	cout<<"10. Thoat"<<endl;
	cout<<"BAN CHON CHUC NANG NAO?"<<endl;
	cin>>chon;

	switch(chon)
	{
	case 1: cout<<"\nCHUC NANG TIM GTLN"<<endl;
			TimMAX(l);
			goto LB;
	case 2: cout<<"\nSAP XEP DANH SACH TANG DAN"<<endl;
			SapXepTang(l);
			cout<<"DANH SACH SAU KHI SAP XEP"<<endl;
			Xuat(l);
			goto LB;
	case 3: cout<<"\nTHEM PHAN TU MOI VAO DAU DANH SACH"<<endl;
			ThemDau(l,N);
			cout<<"Danh sach sau khi them"<<endl;
			Xuat(l);
			goto LB;
	case 4: cout<<"\nTHEM PHAN TU MOI VAO CUOI DANH SACH"<<endl;
			ThemCuoi(l,N);
			cout<<"Danh sach sau khi them"<<endl;
			Xuat(l);
			goto LB;
	case 5: cout<<"\nTHEM PHAN TU MOI VAO SAU 1 PHAN TU XAC DINH TRONG DANH SACH"<<endl;
			ThemSauMotNode(l,N);
			cout<<"Danh sach sau khi them"<<endl;
			Xuat(l);
			goto LB;
	case 6: cout<<"\nXOA PHAN TU DAU TRONG DANH SACH"<<endl;
			XoaDau(l,N);
			cout<<"Danh sach sau khi xoa"<<endl;
			Xuat(l);
			goto LB;
	case 7: cout<<"\nXOA PHAN TU CUOI TRONG DANH SACH"<<endl;
			XoaCuoi(l,N);
			cout<<"Danh sach sau khi xoa"<<endl;
			Xuat(l);
			goto LB;
	case 8: cout<<"\nXOA PHAN TU SAU MOT PHAN TU TRONG DANH SACH"<<endl;
			XoaSau(l,N);
			cout<<"Danh sach sau khi xoa"<<endl;
			Xuat(l);
			goto LB;
	case 9: cout<<"\nXOA PHAN TU BAT KY TRONG DANH SACH"<<endl;
			XoaBatKy(l,N);
			cout<<"Danh sach sau khi xoa"<<endl;
			Xuat(l);
			goto LB;
	case 10: exit(0);
	}

//Doan chuong trinh kiem tra co muon thuc hien lai khong?
char kt;
LB: cout<<"\nBAN MUON LAM LAI KHONG Y/N"<<endl;
	cin>>kt;
	if(kt=='Y' || kt=='y')
	{
		system("cls");
		Xuat(l);
		goto ST;
	}
	else if(kt=='n' ||  kt=='N')
		exit(0);
	else
	{
		cout<<"Ban nhap sai";
		goto LB;
	}

	cout<<endl;
	system("pause");
}

III. Video hướng dẫn danh sách liên kết đơn

Video phần 1

Video phần 2

Video phần 3

Video phần 4

Video phần 5

Chúc các bạn hoàn thành tốt ngôn ngữ lập trình C++