XEM BÀI VIẾT THEO TỪ KHÓA
angular aspnetcore bkap books csharp eclipse frontend giai-thuat java jsp labguides laravel mongodb nosql opencv oracle php postgresql project python restful review servlet slides sql webapi webservice website xml xsd xslt
CÔNG NGHỆ THÔNG TIN >> SINH VIÊN BKAP

Tìm hiểu danh sách liên kết kép-Double Linked List [Cấu trúc dữ liệu và giải thuật]

Đăng lúc: 07:07 PM - 10/07/2023 bởi Charles Chung - 1566

Nếu bạn đã đọc bài viết về "Tìm hiểu danh sách liên kết đơn" thì có thể thấy việc tổ chức dạng danh sách tiện lợi hơn rất nhiều so với dùng mảng. Tuy nhiên, danh sách liên kết đơn vẫn có nhược điểm là chỉ có thể duyệt từ đầu đến cuối. Vì vậy, một số thao tác sẽ rất khó cài đặt trên nó. Danh sách liên kết kép có thể khắc phục nhược điểm này.

1. Danh sách liên kết kép là gì?

Danh sách liên kết đôi (Double Linked List) là một tập hợp các Node được phân bố động, mà cấu trúc mỗi Node bao gồm:

  • Dữ liệu (data).
  • Một con trỏ next sẽ trỏ đến phần tử kế tiếp của danh sách liên kết đó, nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử cuối cùng của danh sách.
  • Một con trỏ pre sẽ trỏ đến phần tử trước của danh sách liên kết đó, nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử đầu tiên của danh sách.

Hình ảnh minh họa 1 node

alt text

Hình ảnh minh họa 1 danh sách

alt text

2. Các thao tác trên danh sách liên kết kép

Định nghĩa cấu trúc danh sách liên kết kép

typedef struct DLL{
    int data;
    struct DLL* next;
    struct DLL* pre;
} NodeD;

Hàm tạo một nút mới

NodeD* create(int value)
{
    NodeD* temp=malloc(sizeof(struct DLL));
    temp->data=value;
    temp->next=NULL;
    temp->pre=NULL;
    return temp;
}

Hàm chèn một nút vào cuối danh sách

NodeD* addToEnd(NodeD* head, int value){
    NodeD *temp,*p;
    temp=create(value);
    if(head==NULL)
        head=temp;
    else{
        p=head;
        while(p->next!=NULL)
        {
            p=p->next;
        }
        p->next=temp;
        temp->pre=p;
    }
  return head;
}

Hàm chèn một nút vào đầu danh sách

NodeD* addToHead(NodeD* head, int value){
    NodeD *temp;
    temp=create(value);
    if(head==NULL)
        head=temp;
    else{
        temp->next=head;
        head=temp;
    }
  return head;
}

Hàm chèn một nút vào vị trí chỉ định

NodeD* addAt(NodeD* head, int value, int position){
    if(position == 0 || head == NULL){
        head = addToHead(head, value);
    }else{
        int k = 1;
        NodeD* p = head;
        while(p != NULL && k != position){
            p = p->next;
            ++k;
        }
         if(k != position){
            head = addToEnd(head, value);
            // printf("Vi tri chen vuot qua vi tri cuoi cung!\n");
        }else{
            NodeD* temp = create(value);
            temp->next = p->next;
            temp->pre = p;
            p->next = temp;
        }
    }
    return head;
}

Hàm xóa một nút ở đầu danh sách

NodeD* deleteHead(NodeD* head){
    if(head == NULL){
        printf("\nCha co gi de xoa het!");
    }else{
        head = head->next;
        head->pre=NULL;
    }
    return head;
}

Hàm xóa một nút ở cuối danh sách

NodeD* deleteEnd(NodeD* head){
    if (head == NULL || head->next == NULL){
         return deleteHead(head);
    }
    NodeD* p = head;
    while(p->next->next != NULL){
        p = p->next;
    }
    p->next = NULL;
    return head;
}

Hàm xóa một nút ở vị trí chỉ định

NodeD* deleteAt(NodeD* head, int position){
    if(position == 0 || head == NULL || head->next == NULL){
        head = deleteHead(head);
    }else{
        int k = 1;
        NodeD* p = head;
        while(p->next->next != NULL && k != position){
            p = p->next;
            ++k;
        }
 
        if(k != position){
            head = deleteEnd(head);
        }else{
            NodeD* temp=p->next->next;
            p->next = temp;
            temp->pre=p;
        }
    }
    return head;
}

Hàm duyệt danh sách

void traverser(NodeD* head){
    printf("\n");
    while(head->pre!=NULL)
        head=head->pre;
    for(NodeD* p = head; p != NULL; p = p->next){
        printf("%5d", p->data);
    }
}

Chương trình test

void main()
{
    printf("Danh sach lien ket kep");
    NodeD* head=NULL;
    for(int i=1;i<=10;i++){
        head=addToHead(head,i);
    }
    head=addAt(head,100,5);
    head=deleteHead(head);
    traverser(head);
    getch();
}

Kết quả

alt text

thay lời cảm ơn!

QUẢNG CÁO - TIẾP THỊ