---
tags: giáo án
---

[TOC]

# Linked list
- Danh sách liên kết (linked list) được dùng để lưu trữ các phần tử có cùng kiểu giá trị.
- Các phần tử trong danh sách liên kết có thể nằm ở các vị trí khác nhau trong bộ nhớ (khác mảng).
- Mỗi phần tử trong danh sách liên kết (node) gồm:
- data: lưu trữ dữ liệu.
- next: con trỏ liên kết chỉ đến phần tử tiếp theo trong danh sách liên kết.

# Các thao tác cơ bản trên danh sách liên kết
## Duyệt danh sách liên kết
- Duyệt từ phần tử đầu tiên "head", di chuyển đến các phần tử khác trên danh sách liên kết dựa vào biến con trỏ "next".

void move(Node* head){
    Node* current = head;
    while(current != NULL){
    current = current->next;
    }
}

## Truy cập phần tử trong danh sách liên kết
- Để truy cập phần tử thứ **p** trong danh sách liên kết, ta cần phải di chuyển từ phần tử đầu tiên cho đến phần tử thứ **p**.

Node* element(Node* head, p){
    Node* current = head;
    int index = 0;
    while(index < p){
        index += 1;
        current = current->next;
    }
    return current;
}
    

## Chèn một phần tử vào danh sách liên kết
- Để chèn một phần tử vào danh sách liên kết, cần tiến hành hai bước cơ bản:
- Tạo một phần tử mới chứa giá trị x.
- Gán giá trị con tỏ next của phần tử thứ (p-1) và phần tử mới như hình bên dưới.
## Xóa một phần tử khỏi danh sách liên kết
- Để xóa một phần tử tại vị trí p khỏi danh sách liên kết, chúng ta thay đổi giá trị con trỏ liên kết next của phần tử thứ p-1. Sau đó xóa phần tử thứ p ra khỏi bộ nhớ.

## Danh sách liên kết đôi
- Việc duyệt danh sách liên kết đơn chỉ thực hiện được theo một chiều. Danh sách liên kết đôi là mở rộng của danh sách liên kết đơn, trong đó mỗi phần tử có hai con trỏ liên kết:
- previous: trỏ đến phần tử phía trước nó trong danh sách
- next: trỏ đến phần tử tiếp theo trong danh sách
- Ví dụ sử dụng danh sách liên kết đôi lưu trữ dãy A, B, C, D:
- Danh sách liên kết đồi thường được sử dụng trong các bài toán cần duyệt trên danh sách theo cả hai chiều.

# So sánh linkedlist và mảng: