Danh sách liên kết – Link List

Danh sách liên kết

Định nghĩa:

Danh sách tuyến tính (Linear List) là 1 dãy gồm 0 hoặc nhiều phần tử có cùng kiểu dữ liệu.(a1,a2,…an) ,n≥0
– ai : là phần tử thức i của danh sách
– a1 là phần tử đầu tiên và an là phần tử cuối cùng của danh sách.
– n : là độ dài của danh sách (n = 0, ta có danh sách rỗng (empty List)).

Cách cài đặt danh sách tuyến tính

Biểu diễn dưới dạng mảng

Tất cả các phần tử của danh sách tuyến tính được lưu vào các ô liên tiếp của mảng.
Danh sách sẽ là cấu trúc gồm 2 thành phần:
– Thành phần 1 : là mảng các phần tử
– Thành phần 2 : là vị trí của phần tử cuối cùng hoặc phần tử đầu tiên trong danh sách.
Ưu điểm:
– Cách biểu diễn này rất tiện cho việc truy xuất đến các phần tử trong danh sách
Nhược điểm:
– Do lưu trữ bằng mảng nên cần fix trước số lượng phần tử cho mảng. Điều này dẫn đến lãng phí bộ nhớ.
– Các thao tác chèn,sửa xóa một phần tử vào danh sách được thực hiện chậm.

Danh sách móc nối

– Danh sách móc nối đơn (Single Linked List)
– Danh sách móc nối vòng (Circular Linked List)
– Danh sách móc nối kép (Double Linked List)
Ưu điểm:
– Vì các nút trong dslk là cấp phát động nên không sợ thiếu hay lãng phí bộ nhớ
– Các thao tác chèn,xóa thực hiện dễ dàng hơn trên mảng
– Với những bản ghi lớn, thực hiện việc di chuyển con trỏ là nhanh hơn nhiều so với việc thực hiện di chuyển các phần tử của danh sách.
Nhược điểm:
– Dùng con trỏ đòi hỏi bộ nhớ phụ
– Dslk không cho phép truy nhập trực tiếp
– Tốn thời gian cho việc duyệt và biến đổi con trỏ
– Lập trình với con trỏ rất dễ nhầm.

Danh sách liên kết đơn (Single Link List)

Định nghĩa

Danh sách liên kết đơn bao gồm các nút (node), các node được liên kết với nhau theo 1 chiều. Mỗi nút là 1 bản ghi gồm có 2 trường:
– Trường thứ nhất chứa dữ liệu của nút đó
– Trường thứ hai chứa liên kết (con trỏ) tới nút tiếp theo ( hay trường thứ 2 chứa địa chỉ của nút kế tiếp).

Danh sách liên kết đơn - Single Linked List
Danh sách liên kết đơn – Single Linked List

– Nút đầu tiên của danh sách liên kết đơn được trỏ tới bởi con trỏ pHead ( được gọi là địa chỉ của danh sách liên kết.
– Thành phần con trỏ của nút cuối trong danh sách liên kết trỏ tới NULL.

Phép toán trên danh sách liên kết đơn

  • Khai báo danh sách liên kết đơn ( mỗi nút chứa giá trị số nguyên và con trỏ trỏ tới nút kế tiếp)
struct Node 
{
    int n;
    Node *pNext;
};
struct SLL
{
    Node *pHead, *pTail;
};
  • Khởi tạo danh sách liên kết đơn
void initSLL(SLL *list)
{
    list->pHead = list->pTail = NULL;
}
  • Kiểm tra danh sách liên kết đơn rỗng
bool isSLLEmpty(SLL list)
{
    if (!list.pHead)
    {
        return true;
    }
    return false;
}
  • In danh sách ra màn hình
void viewSLL(SLL list)
{
    Node *pNode;
    if (isSLLEmpty(list))
    {
        printf("Single link list is empty\n");
    }
    else
    {
        pNode = list.pHead;
        while (pNode)
        {
            printf("%d\n", pNode->n);
            pNode = pNode->pNext;
        }
    }
}
  • Tạo một nút mới
Node *newNode(int k)
{
    Node *pNode;
    pNode = (Node*)malloc(1 * sizeof(Node));
    if (!pNode)
    {
        return NULL;
    }
    pNode->n = k;
    pNode->pNext = NULL;
    return pNode;
}
  • Chèn nút vào đầu danh sách
Chèn vào đầu danh sách
Chèn vào đầu danh sách
bool insertHead(SLL *list, Node *node)
{
    if (!node)
    {
        return false;
    }
    node->pNext = list->pHead;
    list->pHead = node;
    if (!list->pTail)
    {
        list->pTail = node;
    }
    return true;
}
  • Chèn nút vào cuối danh sách
Chèn vào cuối danh sách
Chèn vào cuối danh sách
bool insertTail(SLL *list, Node *node)
{
    if (!node)
    {
        return false;
    }
    if (!list->pHead)
    {
        list->pHead = list->pTail = node;
    }
    else
    {
        list->pTail->pNext = node;
        list->pTail = node;
    }
    return true;
}
  • Xóa nút ở đầu danh sách
Xóa nút đầu danh sách
Xóa nút đầu danh sách
void delHead(SLL *list)
{
    Node *pNode;
    pNode = list->pHead;
    if (pNode)
    {
        list->pHead = pNode->pNext;
        pNode->pNext = NULL;
        free(pNode);
        if (!list->pHead)
        {
            list->pTail = NULL;
        }
    }
}
  • Xóa nút ở cuối danh sách
Xóa nút cuối danh sách
Xóa nút cuối danh sách
void delTail(SLL *list)
{
    Node *pNode;
    pNode = list->pHead;
    if (!pNode)
    {
        return;
    }
    if (list->pHead == list->pTail)
    {
        list->pHead = list->pTail = NULL;
        free(pNode);
        return;
    }
    while (pNode->pNext != list->pTail)
    {
        pNode = pNode->pNext;
    }
    pNode->pNext = NULL;
    free(list->pTail);
    list->pTail = pNode;
}
  • Xóa danh sách liên kết
void delList(SLL *list)
{
    while (!isSLLEmpty(*list))
    {
        delTail(list);
    }
}

Danh sách liên kết kép ( Double Linked List)

Định nghĩa

Danh sách liên kết đôi gồm các nút liên kết với nhau theo 2 chiều. Mỗi nút là 1 bản ghi gồm có 3 trường:
– Trường thứ nhất chứa dữ liệu của nút.
– Trường thứ hai chứa liên kết (con trỏ) tới nút liền sau nó.
– Trường thứ ba chứa liên kết (con trỏ) tới nút liền trước nó.

Danh sách liên kết đôi
Danh sách liên kết đôi

Phép toán trên danh sách liên kết đôi

  • Khai báo danh sách liên kết đôi( mỗi nút chứa giá trị số nguyên và con trỏ trỏ tới nút kế tiếp và con trỏ tới nút trước đó)
struct Node
{
    int n;
    Node *pPrev;
    Node *pNext;
};

struct DLL
{
    Node *pHead, *pTail;
};
  • Khởi tạo danh sách liên kết đôi
void initDLL(DLL *list)
{
    list->pHead = list->pTail = NULL;
}
  • Kiểm tra danh sách liên kết đôi rỗng
bool isDLLEmpty(DLL list)
{
    if (!list.pHead)
    {
        return true;
    }
    return false;
}
  • In danh sách ra màn hình
void viewDLL(DLL list)
{
    Node *pNode;
    if (isDLLEmpty(list))
    {
        printf("Double link list is empty\n");
    }
    else
    {
        pNode = list.pHead;
        while (pNode)
        {
            printf("%d\n", pNode->n);
            pNode = pNode->pNext;
        }
    }
}
  • Tạo một nút mới
Node *newNode(int k)
{
    Node *pNode;
    pNode = (Node*)malloc(1 * sizeof(Node));
    if (!pNode)
    {
        return NULL;
    }
    pNode->n = k;
    pNode->pPrev = pNode->pNext = NULL;
    return pNode;
}
  • Chèn nút vào đầu danh sách
Chèn phần tử vào đầu danh sách
Chèn phần tử vào đầu danh sách
bool insertHead(DLL *list, Node *node)
{
    if (!node)
    {
        return false;
    }
    if (!list->pHead)
    {
        list->pHead = list->pTail = node;
    }
    else
    {
        list->pHead->pPrev = node;
        node->pNext = list->pHead;
        list->pHead = node;
    }
    return true;
}
  • Chèn nút vào cuối danh sách
Chèn nút vào cuối danh sách
Chèn nút vào cuối danh sách
bool insertTail(DLL *list, Node *node)
{
    if (!node)
    {
        return false;
    }
    if (!list->pHead)
    {
        list->pHead = list->pTail = node;
    }
    else
    {
        list->pTail->pNext = node;
        node->pPrev = list->pTail;
        list->pTail = node;
    }
    return true;
}
  • Xóa nút ở đầu danh sách
Xóa nút ở đầu danh sách
Xóa nút ở đầu danh sách
void delHead(DLL *list)
{
    Node *pNode;
    pNode = list->pHead;
    if (pNode)
    {
        if (list->pHead == list->pTail)
        {
            list->pHead = list->pTail = NULL;
            free(pNode);
        }
        else
        {
            list->pHead->pNext->pPrev = NULL;
            list->pHead = list->pHead->pNext;
            free(pNode);
        } 
    }
}
  • Xóa nút ở cuối danh sách
Xóa nút ở cuối danh sách
Xóa nút ở cuối danh sách
void delTail(DLL *list)
{
    Node *pNode;
    pNode = list->pTail;
    if (pNode)
    {
        if (list->pHead == list->pTail)
        {
            list->pHead = list->pTail = NULL;
            free(pNode);
        }
        else
        {
            list->pTail->pPrev->pNext = NULL;
            list->pTail = list->pTail->pPrev;
            free(pNode);
        }
    }
}
  • Xóa danh sách liên kết đôi
void delList(DLL *list)
{
    while(!isDLLEmpty(*list))
    {
        delHead(list);
    }
}

Bài tập

Biểu diễn stack bằng danh sách liên kết đơn

Đếm và phân loại số lượng kí tự

Biểu diễn đa thức bằng danh sách liên kết