---
# System prepended metadata

title: 'Chương 3: Cấu trúc dữ liệu động'

---

![](https://i.redd.it/2npc5wdlyu771.jpg)
[toc]
## Danh sách liên kết đơn
### Khái niệm
- Danh sách liên kết đơn là tập hợp tuyến tính các phần tử và dữ liệu, mà giữa chúng có dự liên kết với nhau thông qua địa chỉ.
- Cách hoạt động của danh sách liên kết là 1 node trong đó sẽ chứa giá trị và địa chỉ trỏ đến node tiếp theo, node cuối cùng có địa chỉ trỏ đến null.

Các thao tác của danh sách liên kết bao gồm:
- Khởi tạo
- Thêm node
- Xoá node
- Duyệt danh sách liên kết
- Truy xuất bằng chỉ mục

### Ví dụ:
[Visualgo](https://visualgo.net/en/list)

### Cài đặt
**1 node**
```cpp=
struct Node{
    int data;
    Node *next;
};
```

**Danh sách liên kết**
```cpp=
struct SinglyLinkedList{
    Node* head;
    Node* tail;
};
```

### Khởi tạo
**Khởi tạo node**
```cpp=
struct Node{
    int data;
    Node *next;
    Node(int d){
        data = d;
        next = NULL;
    }
};
```

**Khởi tạo danh sách**
```cpp=
struct SinglyLinkedList{
    Node* head;
    Node* tail;
    SinglyLinkedList(){
        head = NULL;
        tail = NULL;
    }
};
```

**Destructor**
```cpp
~SinglyLinkedList(){
    Node* cur = head;
    while(cur){
        Node* nxt = cur->next;
        delete cur;
        cur = nxt;
    }
    head = tail = nullptr;
}
```

### Duyệt danh sách
```cpp=
void traverse(const SinglyLinkedList& root){
    Node* node = root.head;
    while(node != NULL){
        node = node -> next;
    }
}
```

**Tìm kiếm phần tử**
```cpp=
Node* search(const SinglyLinkedList& root, int x){
    Node* node = root.head;
    while(node != NULL){
        if(node -> data == x)
            return node;
        node = node -> next;
    }
    return NULL;
}
```

**Truy xuất phần tử**
```cpp=
Node* nodeAt(const SinglyLinkedList& root, int index){
    Node* node = root.head;
    int count = 0;
    while(node != NULL){
        if(count == index)
            return node;
        count++;
        node = node -> next;
    }
    return NULL;
}
```
### Chèn phần tử
**Chèn đầu**
```cpp=
void pushFront(SinglyLinkedList& root, int x){
    Node* node = new Node(x);
    if(root.head == NULL)
        root.head = root.tail = node;
    else{
        node -> next = root.head;
        root.head = node;
    }
}
```

**Chèn cuối**
```cpp=
void pushBack(SinglyLinkedList& root, int x){
    Node* node = new Node(x);
    if(root.head == NULL)
        root.head = root.tail = node;
    else{
        root.tail -> next = node;
        root.tail = node;
    }
}
```

**Chèn vào một sau một node cho trước**
```cpp=
void insert(Node* prev, int x){
    if(prev == NULL)
        return;
    Node* node = new Node(x);
    node -> next = prev -> next;
    prev -> next = node;
}
```
### Xoá node
```cpp=
void eraseNode(SinglyLinkedList& root, Node* x){
    if(root.head == NULL || x == NULL) return;

    if(root.head == x){
        root.head = root.head->next;
        if(root.tail == x) root.tail = NULL; 
        delete x;
        return;
    }


    Node* prev = root.head;
    while(prev->next != NULL && prev->next != x){
        prev = prev->next;
    }
    if(prev->next == x){
        prev->next = x->next;
        if(root.tail == x) root.tail = prev; 
        delete x;
    }
}
```

## Stack
### Khái niệm
Là một cấu trúc dữ liệu hoạt động theo nguyên tắc **Last In, First Out (LIFO)**. Phần tử cuối cùng được thêm vào stack sẽ là phần tử đứng đầu và là phần tử bị xoá đầu tiên.

Các thao tác trên stack là:
- push (thêm phần tử)
- pop (xoá phần tử đầu)
- top (giá trị phần tử đứng đầu)
- empty (kiểm tra stack có rỗng hay không)
- size (chiều dài của stack)
![image alt](https://hackmd.io/_uploads/rJKgK5e_h.png)


### Ví dụ:
[Visualgo](https://visualgo.net/en/list)

### Cài đặt
Trong thư viện chuẩn của C++, ta có thể sử dụng `std::stack` để khai báo cấu trúc stack có sẵn các thao tác.

## Queue
### Khái niệm
Là một cấu trúc dữ liệu hoạt động theo nguyên tắc **First In, First Out (FIFO)**. Phần tử đầu tiên được thêm vào queue sẽ là phần tử đứng đầu và là phần tử bị xoá đầu tiên.

Các thao tác trên queue là:
- push (thêm phần tử)
- pop (xoá phần tử đầu)
- front (giá trị phần tử đứng đầu)
- empty (kiểm tra queue có rỗng hay không)
- size (chiều dài của queue)


### Ví dụ:
[Visualgo](https://visualgo.net/en/list)

### Cài đặt
Trong thư viện chuẩn của C++, ta có thể sử dụng `std::queue` để khai báo cấu trúc queue có sẵn các thao tác.