Rate this post

Linked list là một cấu trúc dữ liệu liên kết, mỗi phần tử trong danh sách được gọi là một node và bao gồm hai thành phần chính: dữ liệu và con trỏ. Con trỏ trỏ đến phần tử tiếp theo trong danh sách. Điểm mạnh của linked list là nó cho phép chúng ta thêm và xóa phần tử một cách dễ dàng và linh hoạt, nhưng điểm yếu là tìm kiếm một phần tử cần phải duyệt từ đầu đến cuối danh sách.

Các bài viết liên quan;

Ví dụ về linked list trong C++:

Copy code#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node* next;
};

void push(Node** head, int newData)
{
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = (*head);
    (*head) = newNode;
}

void insertAfter(Node* prevNode, int newData)
{
    if (prevNode == NULL)
    {
        cout << "Previous node cannot be NULL";
        return;
    }
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

void append(Node** head, int newData)
{
    Node* newNode = new Node();
    Node* last = *head;
    newNode->data = newData;
    newNode->next = NULL;
    if (*head == NULL)
    {
        *head = newNode;
        return;
    }
    while (last->next != NULL)
        last = last->next;
    last->next = newNode;
    return;
}

void printList(Node* node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}

int main()
{
    Node* head = NULL;
    append(&head, 6);
    push(&head, 7);
    push(&head, 1);
    append(&head, 4);
    insertAfter(head->next, 8);
    cout << "Created Linked List: ";
    printList(head);
    return 0;
}

Không giống với mảng, linked list không có kích thước cố định, chúng ta có thể thêm hoặc xóa phần tử một cách linh hoạt. Các thao tác thông dụng trong linked list bao gồm: push (thêm phần tử vào đầu), insertAfter (thêm phần tử sau một phần tử nhất định), append (thêm phần tử vào cuối) và deleteNode (xóa phần tử).

Ngoài ra, linked list còn có một số loại khác như doubly linked list (có con trỏ trỏ đến phần tử trước và phần tử sau), circular linked list (con trỏ cuối cùng trỏ về phần tử đầu tiên) và singly linked list (chỉ có con trỏ trỏ đến phần tử tiếp theo).

Tại sao nên sử dụng linked list

Có một số lý do tại sao nên sử dụng linked list:

Linked list cho phép thêm hoặc xóa phần tử một cách linh hoạt, không cần phải cấp phát và hủy bộ nhớ như mảng.
Linked list có thể mở rộng hoặc thu hẹp dễ dàng mà không cần phải quan tâm đến việc cấp phát và hủy bộ nhớ.
Linked list không cần phải duyệt tất cả các phần tử để tìm một phần tử cụ thể như trong mảng, chỉ cần duyệt từ phần tử đầu tiên đến khi tìm thấy.
Linked list có thể được sử dụng để thực hiện các thao tác trên các phần tử liên tiếp như xóa hoặc thêm một phần tử giữa hai phần tử khác nhau.
Linked list có thể được sử dụng để thực hiện các thao tác trên dữ liệu liên tiếp, ví dụ như thao tác trên các phần tử trong một stack hoặc queue.
Linked list có thể được sử dụng để thực hiện các thao tác trên các phần tử liên tiếp như xóa hoặc thêm một phần tử giữa hai phần tử khác nhau.
Linked list có thể được sử dụng để thực hiện các thao tác trên dữ liệu liên tiếp, ví dụ như thao tác trên các phần tử trong một stack hoặc queue.
Linked list có thể được sử dụng để thực hiện các thao tác trên các dữ liệu có kích thước lớn, vì nó không cần phải cấp phát bộ nhớ cho toàn bộ dữ liệu trước khi sử dụng.
Linked list có thể được sử dụng để thực hiện các thuật toán đệ quy, vì nó cho phép chúng ta lưu trữ và truy xuất các phần tử liên tiếp một cách dễ dàng.
Linked list có thể được sử dụng để thực hiện các thao tác trên dữ liệu có kích thước lớn, vì nó không cần phải cấp phát bộ nhớ cho toàn bộ dữ liệu trước khi sử dụng.

C/C++

linked list trong c++

Tại sao nên sử dụng linked list

Trả lời Hủy