# Danh sách liên kết đơn C++
## Trình bày: Lê Minh Trí
- **Định nghĩa:** **Danh sách liên kết đơn (Single Linked List)** là một cấu trúc dữ liệu động, nó là một **danh sách mà mỗi phần tử đều liên kết với phần tử đúng sau nó trong danh sách**. Mỗi phần tử (được gọi là một node hay nút) trong danh sách liên kết đơn là một cấu trúc có hai thành phần:
- **Thành phần dữ liệu:** lưu thông tin về bản thân phần tử đó.
- **Thành phần liên kết:** ***lưu địa chỉ phần tử đứng sau trong danh sách***, nếu phần tử đó là phần tử cuối cùng thì thành phần này bằng **NULL**.
- **Cấu trúc dữ liệu của danh sách liên kết đơn:**
- **Khai báo danh sách liên kết đơn dùng 2 con trỏ:**
```cpp=
// Định nghĩa cấu trúc của 1 node
struct node {
// info chứ dữ liệu
KDL info;
// con trỏ pNext giữ địa chỉ node kế tiếp
struct node *pNext;
};
typedef struct node NODE;
// Định nghĩa cấu trúc danh sách List
struct list {
// Con trỏ pHead giữ địa chỉ node đầu tiên
NODE *pHead;
// Con trỏ pTail giữ địa chỉ node cuối cùng
NODE *pTail;
};
typedef struct list LIST;
```
- **Khai báo danh sách liên kết đơn dùng 1 con trỏ:**
```cpp=
// Định nghĩa cấu trúc của 1 node
struct node {
// info chứa dữ liệu
KDL info;
// Con trỏ pNext giữ địa chỉ ô nhớ của node kế tiếp
struct node *pNext;
};
typedef struct node NODE;
// ĐỊnh nghĩa LIST là kiểu dữ liệu chứa địa chỉ ô nhớ đầu tiên (pHead) của node
typedef NODE* LIST;
```
- **Khởi tạo danh sách liên kết đơn:** là tạo ra danh sách rỗng không chứ node nào hết.
- **Khởi tạo danh sách liên kêt đơn dùng 2 con trỏ:**
```cpp=
void Init(LIST &l) {
l.pHead = NULL;
l.pTail = NULL;
}
```
- **Khởi tạo danh sách liên kết đơn dùng 1 con trỏ:**
```cpp=
void Init(LIST &l) {
l = NULL;
}
```
- **Kiểm tra danh sách liên kết đơn rỗng:** là hàm kiểm tra khi danh sách rỗng thì trả về giá trị 1 ngược lại trả về giá trị 0.
- **Hàm kiểm tra danh sách liên kết đơn rỗng dùng 2 con trỏ:**
```cpp=
int IsEmpty(LIST &l) {
// Mảng rỗng không có phần tử do đó pHead mang giá trị NULL
if (l.pHead == NULL)
return 1;
return 0;
}
```
- **Hàm kiểm tra danh sách liên kết đơn rỗng dùng 1 con trỏ:**
```cpp=
int IsEmpty(LIST &l) {
// Mảng rỗng không có phần tử do đó l mang giá trị NULL
if (l==NULL) return 1;
return 0;
}
```
- **Tạo node cho danh sách liên kết đơn:** là xin cấp phát bộ nhớ có kích thước của 1 node để chứa dữ liệu cho trước.
- **Định nghĩa hàm trừu tượng:**
```cpp=
NODE* GetNode(KDL x) {
NODE *p = new NODE;
if (p == NULL) return NULL;
p->info = x;
p->pNext = NULL;
// Trả về địa chỉ của Node mới được tạo
return p;
}
```
- **Thêm một node vào cuối danh sách liên kết đơn:** là gắn node đó vào cuối danh sách.
- **Hàm thêm một node vào cuối danh sách liên kết đơn dùng 2 con trỏ:**
```cpp=
void AddTail(LIST &l, NODE *p) {
if (l.pHead==NULL) {
l.pHead = l.pTail = p;
}
else {
l.pTail->pNext = p;
l.pTail = p;
}
}
```
- **Hàm thêm một node vào cuối danh sách liên kết đơn dùng 1 con trỏ:**
```cpp=
void AddTail(LIST &l, NODE *p) {
if(l == NULL)
l = p;
else {
//Tạo biến con trỏ chứa địa chỉ ô nhớ đầu tiên của list
NODE *q = l;
//Tìm địa chỉ node cuối
while(q->pNext != NULL) {
q = q->pNext;
}
q->pNext = p;
}
}
```
- **Thêm một node vào đầu danh sách liên kết đơn: là gắn node đó vào đầu danh sách.**
- **Hàm thêm một node vào đầu danh sách liên kết dùng 2 con trỏ:**
```cpp=
void AddHead(LIST &l,NODE *p) {
if(l.pHead == NULL)
l.pHead=l.pTail=p;
else {
p->pNext = l.pHead;
l.pHead = p;
}
}
```
- **Hàm thêm node vào đầu danh sách liên kết dùng 1 con trỏ:**
```cpp=
void AddHead(LIST &l,NODE *p) {
if(l == NULL){
l=p;
}
else {
p->pNext = l;
l=p;
}
}
```
- **Thêm một node vào cuối một node bất kỳ trong danh sách liên kết:**
- **Định nghĩa hàm dùng 2 con trỏ:**
```cpp=
void InsertAfterNode(LIST &l,NODE *p,NODE *q) {
if(p != NULL){
q->pNext = p->pNext;
p->pNext = q;
if(l.pTail == p){
AddTail(l,q);
}
} else AddHead(l,q);
}
```
- **Định nghĩa hàm dùng 1 con trỏ:**
```cpp=
void InsertAfterNode(LIST &l,NODE *p,NODE *q) {
if(p != NULL){
q->pNext = p->pNext;
p->pNext = q;
NODE *t=l;
while(t->pNext != NULL){
t=t->pNext;
}
if(t == p){
AddTail(l,q);
}
} else AddHead(l,q);
}
```
- **Nhập từ bàn phím danh sách liên kết đơn:** là lần lượt nhập thông tin từng node từ bàn phím.
- **Định nghĩa hàm:**
```cpp=
void Input(LIST &l)
{
int n;
cout<<"Nhap so phan tu: ";
cin>>n;
// Gọi hàm khởi tạo danh sách rỗng
Init(l);
for(int i = 1; i<=n ; i++){
KDL x;
Nhap(x);
// Gọi hàm GetNode để lưu thông tin vào node và trả về địa chỉ của node mới
NODE *p = GetNode(x);
if(p != NULL) AddTail(l, p);
}
}
```
- **Duyệt tuần tự danh sách liên kết đơn:** là duyệt qua tất cả các node trong dach sách 1 lần.
- **Định nghĩa hàm trừu tượng dùng 2 con trỏ:**
```cpp=
KDL <Tên hàm>(LIST l) {
...
NODE *p = l.pHead;
while(p != NULL){
p=p->pNext;
}
...
}
```
- **Định nghĩa hàm trừu tượng dùng 1 con trỏ:**
```cpp=
KDL <Tên hàm>(LIST l) {
...
NODE *p = l;
while(p != NULL){
p=p->pNext;
}
...
}
```
- **Xoá node ở đầu danh sách:** là hàm xoá node đầu tiên trong danh sách liên kết đơn, trả về 1 nếu xoá thành công, trả về không nếu không thể xoá.
- **Định nghĩa hàm xoá node ở đầu danh sách liên kết dùng 2 con trỏ:**
```cpp=
int RemoveHead(LIST &l, int &x) {
if(l.pHead != NULL){
NODE *p = l.pHead;
// Lưu lại data khi cần dùng
x= p->info;
l.pHead = p->pNext;
delete p;
if(l.pHead == NULL){
l.pTail = NULL;
}
return 1;
}
return 0;
}
```
- **Định nghĩa hàm xoá node ở đầu danh sách liên kết đơn dùng 1 con trỏ:**
```cpp=
int RemoveHead(LIST &l, int &x) {
if(l != NULL){
NODE *p = l;
// Lưu lại data khi cần dùng
x= p->info;
l = p->pNext;
delete p;
return 1;
}
return 0;
```
- **Định nghĩa hàm xoá node ở sau một node bất kì trong danh sách:**
```cpp=
int RemoveNode(LIST &l,NODE *p, int &x) {
if(p != NULL){
NODE *q=p->pNext;
if(q != NULL){
if(l.pTail ==q){
l.pTail = p;
p->pNext = q->pNext;
x= q->info;
delete q;
return 1;
}
return 0;
}
return 0;
}
```
Sign in with Wallet
Connect another wallet