Bài 21.726 phút đọc

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

Sau bài này bạn sẽ làm được

Cài thêm và xóa cho danh sách đôi với đủ bốn con trỏ
Xóa một nút đã biết địa chỉ trong O(1)
Giải thích đánh đổi bộ nhớ so với danh sách đơn
Hiểu mẫu nhúng list_head và macro container_of

Thêm một con trỏ lùi vào mỗi nút thì xóa nút đã biết địa chỉ trở thành O(1), và duyệt được cả hai chiều. Cái giá là tám byte mỗi nút và bốn con trỏ phải cập nhật đúng ở mỗi thao tác.

#Khai báo và bất biến

dlist.h

#ifndef DLIST_H
#define DLIST_H

#include <stddef.h>

typedef struct DNode {
    int           data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

/* Bất biến của DList:
     1. head == NULL  khi và chỉ khi  size == 0
     2. tail == NULL  khi và chỉ khi  head == NULL
     3. head != NULL  thì  head->prev == NULL
     4. tail != NULL  thì  tail->next == NULL
     5. với mọi nút p có p->next != NULL: p->next->prev == p
     6. size == số nút đi được từ head theo next                  */
typedef struct {
    DNode *head;
    DNode *tail;
    size_t size;
} DList;

void   dlist_khoi_tao(DList *l);
void   dlist_huy(DList *l);
int    dlist_them_dau(DList *l, int data);
int    dlist_them_cuoi(DList *l, int data);
int    dlist_chen_truoc(DList *l, DNode *moc, int data);
int    dlist_xoa(DList *l, DNode *n);
DNode *dlist_tim(const DList *l, int data);
void   dlist_in_xuoi(const DList *l);
void   dlist_in_nguoc(const DList *l);

#endif

Mỗi nút giữ cả prev và next. Bất biến số 5 nói hai chiều luôn khớp nhau.

Bất biến số 5 là bất biến quan trọng nhất và cũng dễ vỡ nhất. Nó nói rằng đi tiến rồi đi lùi thì quay về đúng chỗ cũ. Mọi lỗi của danh sách đôi đều là vi phạm bất biến này ở đâu đó.

	Danh sách đơn	Danh sách đôi
Bộ nhớ mỗi nút	16 byte	24 byte
Con trỏ phải sửa khi chèn	2	4
Con trỏ phải sửa khi xóa	1	2
Xóa nút đã có con trỏ	O(n)	O(1)
Xóa cuối	O(n)	O(1)
Duyệt ngược	Không được	O(n)
Số bất biến phải giữ	4	6

#Thêm phần tử

dlist.c

#include <stdio.h>
#include <stdlib.h>

#include "dlist.h"

void dlist_khoi_tao(DList *l)
{
    l->head = NULL;
    l->tail = NULL;
    l->size = 0;
}

static DNode *dnode_tao(int data)
{
    DNode *n = malloc(sizeof *n);

    if (n == NULL) return NULL;

    n->data = data;
    n->prev = NULL;
    n->next = NULL;

    return n;
}

int dlist_them_dau(DList *l, int data)
{
    DNode *n = dnode_tao(data);

    if (n == NULL) return -1;

    n->next = l->head;

    if (l->head != NULL) l->head->prev = n;      /* chiều ngược của bất biến 5 */
    else                 l->tail       = n;      /* danh sách trước đó rỗng */

    l->head = n;
    ++l->size;

    return 0;
}

int dlist_them_cuoi(DList *l, int data)
{
    DNode *n = dnode_tao(data);

    if (n == NULL) return -1;

    n->prev = l->tail;

    if (l->tail != NULL) l->tail->next = n;
    else                 l->head       = n;

    l->tail = n;
    ++l->size;

    return 0;
}

Chèn trước một nút đã biết

dlist.c (tiếp)

/* Chèn một nút mới ngay TRƯỚC nút moc. O(1).
   moc bằng NULL nghĩa là chèn vào cuối. */
int dlist_chen_truoc(DList *l, DNode *moc, int data)
{
    if (moc == NULL) return dlist_them_cuoi(l, data);
    if (moc == l->head) return dlist_them_dau(l, data);

    DNode *n = dnode_tao(data);

    if (n == NULL) return -1;

    /* Bốn con trỏ, đặt theo thứ tự từ nút mới ra ngoài */
    n->prev = moc->prev;
    n->next = moc;

    moc->prev->next = n;
    moc->prev       = n;

    ++l->size;

    return 0;
}

Thứ tự bốn phép gán rất quan trọng

Sửa moc->prev trước

moc->prev = n;              /* mất địa chỉ nút đứng trước moc */
n->prev   = moc->prev;      /* giờ n->prev chính là n */
n->next   = moc;
moc->prev->next = n;        /* ghi vào n->next, sai hoàn toàn */

Đọc hết giá trị cũ rồi mới ghi đè

n->prev = moc->prev;        /* đọc giá trị cũ khi nó còn nguyên */
n->next = moc;

moc->prev->next = n;        /* vẫn dùng giá trị cũ */
moc->prev       = n;        /* ghi đè sau cùng */

Quy tắc ở Bài 21.3 lặp lại nguyên vẹn: đọc mọi thứ mình cần trước, ghi đè sau. Với bốn con trỏ thì quy tắc này còn quan trọng hơn.

#Xóa nút đã có con trỏ, O(1)

dlist.c (tiếp)

/* Xóa nút n khỏi danh sách. O(1), không cần duyệt tìm nút trước.
   n phải thật sự thuộc l, hàm không kiểm được điều đó. */
int dlist_xoa(DList *l, DNode *n)
{
    if (l == NULL || n == NULL) return -1;

    if (n->prev != NULL) n->prev->next = n->next;
    else                 l->head       = n->next;      /* n là nút đầu */

    if (n->next != NULL) n->next->prev = n->prev;
    else                 l->tail       = n->prev;      /* n là nút cuối */

    free(n);
    --l->size;

    return 0;
}

Bảy dòng, và nó xử lý đủ bốn trường hợp: nút giữa, nút đầu, nút cuối, và nút duy nhất. Với danh sách đơn thì cùng chức năng này cần một vòng lặp O(n) để tìm nút đứng trước.

Trường hợp	n->prev	n->next	Nhánh nào chạy
Nút giữa	khác NULL	khác NULL	Cả hai nhánh else, không đụng head và tail
Nút đầu	NULL	khác NULL	head lùi về n->next
Nút cuối	khác NULL	NULL	tail lùi về n->prev
Nút duy nhất	NULL	NULL	head và tail cùng thành NULL

Hàm không kiểm được nút có thuộc danh sách này không

DList a, b;

dlist_khoi_tao(&a);
dlist_khoi_tao(&b);
dlist_them_cuoi(&a, 10);
dlist_them_cuoi(&b, 20);

DNode *n = a.head;

dlist_xoa(&b, n);      /* SAI: b.size giảm, nhưng nút thuộc a */

Kết quả là b.size thành số âm rất lớn vì size_t không dấu, còn a giữ con trỏ treo. Đây là hợp đồng người gọi phải tự giữ. Trong bản gỡ lỗi có thể thêm một trường DList *chu vào mỗi nút để bắt lỗi này.

main.c

#include <stdio.h>

#include "dlist.h"

int main(void)
{
    DList l;

    dlist_khoi_tao(&l);

    for (int i = 1; i <= 5; ++i)
        if (dlist_them_cuoi(&l, i * 10) != 0) { dlist_huy(&l); return 1; }

    dlist_in_xuoi(&l);
    dlist_in_nguoc(&l);

    DNode *n = dlist_tim(&l, 30);

    if (n != NULL) dlist_xoa(&l, n);         /* O(1), không duyệt lại */

    dlist_in_xuoi(&l);

    dlist_xoa(&l, l.head);                   /* xóa đầu */
    dlist_xoa(&l, l.tail);                   /* xóa cuối, cũng O(1) */

    dlist_in_xuoi(&l);
    dlist_huy(&l);

    return 0;
}

terminal

gcc -std=c17 -Wall -Wextra -g dlist.c main.c -o t && ./t

xuoi : [10, 20, 30, 40, 50]  (size = 5)
nguoc: [50, 40, 30, 20, 10]
xuoi : [10, 20, 40, 50]  (size = 4)
xuoi : [20, 40]  (size = 2)

# Valgrind chạy trên bản không bật sanitizer

valgrind --leak-check=full ./t

All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts

#Duyệt ngược

dlist.c (tiếp)

void dlist_in_xuoi(const DList *l)
{
    printf("xuoi : [");

    for (const DNode *p = l->head; p != NULL; p = p->next) {
        printf("%d", p->data);

        if (p->next != NULL) printf(", ");
    }

    printf("]  (size = %zu)\n", l->size);
}

void dlist_in_nguoc(const DList *l)
{
    printf("nguoc: [");

    for (const DNode *p = l->tail; p != NULL; p = p->prev) {
        printf("%d", p->data);

        if (p->prev != NULL) printf(", ");
    }

    printf("]\n");
}

Kiểm tra bất biến 5 bằng cách duyệt hai chiều

/* Duyệt xuôi rồi duyệt ngược, hai dãy phải là đảo của nhau,
   và số nút đếm được phải bằng nhau. */
void dlist_kiem_tra(const DList *l)
{
    assert((l->head == NULL) == (l->size == 0));
    assert((l->tail == NULL) == (l->head == NULL));

    if (l->head != NULL) assert(l->head->prev == NULL);
    if (l->tail != NULL) assert(l->tail->next == NULL);

    size_t xuoi = 0;

    for (const DNode *p = l->head; p != NULL; p = p->next) {
        ++xuoi;
        assert(xuoi <= l->size);

        if (p->next != NULL) assert(p->next->prev == p);   /* bất biến 5 */
    }

    size_t nguoc = 0;

    for (const DNode *p = l->tail; p != NULL; p = p->prev) ++nguoc;

    assert(xuoi == l->size);
    assert(nguoc == l->size);
}

#Nút canh để bỏ mọi trường hợp riêng

Nút canh

Một nút giả không mang dữ liệu, luôn tồn tại, đứng làm đầu và cuối cùng lúc. Danh sách trở thành vòng khép kín quanh nút này, nên không bao giờ có con trỏ NULL, và mọi trường hợp riêng biến mất.

dlist-canh.h

typedef struct DNode {
    int           data;
    struct DNode *prev, *next;
} DNode;

typedef struct {
    DNode  canh;      /* nút giả, nằm ngay trong struct, không cấp phát riêng */
    size_t size;
} DListC;

void dlistc_khoi_tao(DListC *l)
{
    l->canh.prev = &l->canh;      /* trỏ về chính nó */
    l->canh.next = &l->canh;
    l->size      = 0;
}

/* Danh sách rỗng: canh.next == &canh
   Nút đầu       : l->canh.next
   Nút cuối      : l->canh.prev                             */

Không có nút canh

/* Bản có NULL: bốn nhánh if */
int dlist_xoa(DList *l, DNode *n)
{
    if (n->prev != NULL) n->prev->next = n->next;
    else                 l->head       = n->next;

    if (n->next != NULL) n->next->prev = n->prev;
    else                 l->tail       = n->prev;

    free(n);
    --l->size;

    return 0;
}

Có nút canh

/* Bản có nút canh: không nhánh nào cả */
void dlistc_xoa(DListC *l, DNode *n)
{
    n->prev->next = n->next;      /* n->prev luôn tồn tại, cùng lắm là canh */
    n->next->prev = n->prev;

    free(n);
    --l->size;
}

void dlistc_chen_truoc(DListC *l, DNode *moc, DNode *n)
{
    n->prev = moc->prev;
    n->next = moc;

    moc->prev->next = n;
    moc->prev       = n;

    ++l->size;
}

Duyệt với nút canh

for (DNode *p = l->canh.next; p != &l->canh; p = p->next)
    printf("%d ", p->data);

Điều kiện dừng đổi từ p != NULL thành p != &l->canh. Đúng như danh sách vòng ở Bài 21.8, và đó không phải trùng hợp: danh sách có nút canh là một danh sách vòng.

	Không nút canh	Có nút canh
Số nhánh trong hàm xóa	4	0
Số nhánh trong hàm chèn	3	0
Bộ nhớ phụ	0	24 byte cho cả danh sách
Nút đầu	l->head	l->canh.next
Kiểm tra rỗng	head == NULL	canh.next == &canh
Dễ đọc với người mới	Có	Cần làm quen

#Mẫu list_head của nhân Linux

Cả hai bản trên đều nhúng dữ liệu vào nút. Muốn danh sách chứa kiểu khác thì phải viết lại toàn bộ. Nhân Linux lật ngược quan hệ đó: nhúng nút vào dữ liệu.

Kiểu nhân Linux

#include <stddef.h>

struct list_head {
    struct list_head *prev, *next;
};

/* Kiểu của bạn nhúng một list_head vào bên trong */
typedef struct {
    char             ten[64];
    int              tuoi;
    struct list_head lien_ket;      /* nút danh sách nằm ngay đây */
} Nguoi;

/* Từ con trỏ tới trường lien_ket, lấy lại con trỏ tới cả struct Nguoi */
#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

#define nguoi_tu_lien_ket(p)  container_of(p, Nguoi, lien_ket)

container_of hoạt động thế nào

offsetof(Nguoi, lien_ket) cho biết trường lien_ket nằm cách đầu struct bao nhiêu byte, ở đây là 68 sau khi tính đệm. Có địa chỉ của trường thì trừ đi 68 là ra địa chỉ của cả struct. Ép về char * để phép trừ tính theo byte, đúng như Bài 12.4.

Nguoi n = { "An", 20, { NULL, NULL } };

struct list_head *p = &n.lien_ket;

Nguoi *lay_lai = container_of(p, Nguoi, lien_ket);

/* lay_lai == &n */

dung-list-head.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "list-head.h"

int main(void)
{
    struct list_head danh_sach;

    INIT_LIST_HEAD(&danh_sach);

    const char *ten[] = { "An", "Binh", "Cuong" };

    for (int i = 0; i < 3; ++i) {
        Nguoi *n = malloc(sizeof *n);

        if (n == NULL) return 1;

        snprintf(n->ten, sizeof n->ten, "%s", ten[i]);
        n->tuoi = 20 + i;

        list_them_cuoi(&n->lien_ket, &danh_sach);
    }

    struct list_head *p;

    for (p = danh_sach.next; p != &danh_sach; p = p->next) {
        Nguoi *n = nguoi_tu_lien_ket(p);

        printf("%-8s %d\n", n->ten, n->tuoi);
    }

    /* Hủy: phải lưu next trước vì free làm p treo */
    for (p = danh_sach.next; p != &danh_sach; ) {
        struct list_head *ke = p->next;

        free(nguoi_tu_lien_ket(p));
        p = ke;
    }

    return 0;
}

terminal

gcc -std=c17 -Wall -Wextra -g dung-list-head.c -o t && ./t

An       20
Binh     21
Cuong    22

Tự làm thử

Cài DList đầy đủ với sáu bất biến và hàm dlist_kiem_tra duyệt hai chiều.
Cài dlist_xoa rồi thử đủ bốn trường hợp: nút giữa, nút đầu, nút cuối, nút duy nhất. Gọi hàm kiểm tra sau mỗi lần.
Cài lại danh sách đôi dùng nút canh, rồi đếm số nhánh if của hai bản và so sánh.
Cài container_of và kiểm rằng nó trả về đúng địa chỉ struct với ít nhất hai kiểu khác nhau.
Cho một struct nằm trong hai danh sách cùng lúc bằng cách nhúng hai trường list_head, ví dụ danh sách theo tên và danh sách theo tuổi.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

Danh sách đôi thêm trường prev, nhờ đó xóa nút đã biết địa chỉ và xóa cuối đều thành O(1).
Bất biến quan trọng nhất là p->next->prev == p. Mọi lỗi của danh sách đôi đều là vi phạm nó.
Mọi thao tác phải đọc hết giá trị con trỏ cũ trước, ghi đè sau, vì có tới bốn con trỏ liên quan.
Nút canh biến danh sách thành vòng khép kín và xóa sạch mọi nhánh xử lý riêng, đổi lại tốn thêm một nút giả cho cả danh sách.
Mẫu list_head nhúng nút vào dữ liệu thay vì ngược lại, cho một cài đặt dùng được với mọi kiểu và một struct nằm được trong nhiều danh sách.