Chèn Node vào danh sách liên kết đôi

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách chèn Node vào danh sách liên kết đôi. Đây làm một bước khá quan trọng trong việc thêm dữ liệu vào danh sách.

Chúng ta sẽ cùng nhau tìm hiểu hai cách thêm Node vào danh sách liên kết đôi

  • Thêm Node vào đầu danh sách.
  • Thêm Node vào cuối danh sách.

1. Thêm Node vào đầu danh sách

Trong phần này chúng ta sẽ thêm Node vào đầu danh sách (insertFirst). Về cơ bản thì nó tương tự như danh sách liên kết đơn, cùng mình tìm hiểu xem cách thêm nó như thế nào nhé.

dslk doi 4 PNG

Đầu tiên ta sử dụng hàm CreateNode() để tạo một Node mới newNode.

Bài viết này được đăng tại [kiso.vn]

Tiếp đến ta xét điều kiện, nếu danh sách rỗng thì newNode vừa là Node đầu và Node cuối: head = newNode và tail = newNode. Nếu trong danh sách có phần tử thì ta thực hiện chèn vào đầu danh sách bằng cách:

  • Thiết lập con trỏ prev của head trỏ đến newNode: head -> prev = newNode
  • Thiết lập con trỏ next của newNode trỏ đến head: newNode -> next = head
  • Dịch chuyển Node head về newNode, vì head luôn luôn quản lý Node đầu tiên trong danh sách: head = newNode
/* thêm node vào đầu danh sách */
void InsertAtHead(int x) {
  //sử dụng hàm tạo Node tạo một Node mới
    struct Node* newNode = CreateNode(x);
   //nếu danh sách rỗng thì node chèn vào vừa là node đầu vừa là node cuối
    if(head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }
    //Nếu danh sách không rỗng thì, dịch chuyển Node head về node mới chèn, và cho con trỏ của newNode trỏ đến Node head
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
}

2. Thêm Node vào cuối danh sách

Trong phần này chúng ta sẽ thực hiện chèn Node vào cuối danh sách, đây là cách thường được sử dụng rất nhiều.

dslk doi 5 PNG

Tương tự như thêm Node vào đầu danh sách, ta sử dụng hàm CreateNode() để tạo một Node mới newNode.

Sau đó cũng xét điều kiện, nếu danh sách rỗng thì newNode vừa là head vừa là tail. Nếu danh sách có phần tử thì ta thực hiện:

  • Thiết lập con trỏ next của tail trỏ đến newNode.
  • Thiết lập con trỏ prev của newNode trỏ đến tail.
  • Dịch chuyển tail về newNode, vì tail luôn luôn quản lý Node cuối cùng.
/* thêm node vào cuối danh sách */
void InsertLast(int x) {
  //sử dụng hàm tạo Node để tạo node mới newNode
    struct Node* newNode = CreateNode(x);
    //Nếu danh sách rỗng thì newNode vừa là node đầu vừa là node cuối
    if(head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }
    //Nếu danh sách có phần tử thì, 
    tail->next = newNode;// con trỏ next của tail trỏ đến newNode
    newNode->prev = tail;// con trỏ prev của newNode trỏ đến tail
    tail = newNode;//dịch chuyển tail về newNode, vì tail luôn luôn quản lý phần tử cuối cùng trong danh sách
}

3. Ví dụ thêm Node vào danh sách liên kết đôi

Trong ví dụ này chúng ta sẽ thực hiện một chương trình tạo một danh sách liên kết đôi với các thao tác: tạo, thêm vào đầu, thêm vào cuối, duyệt danh sách theo hai chiều.

Đầu tiên ta cần tạo cấu trúc dữ liệu cho danh sách liên kết đôi.

/* tạo cấu trúc node */
struct Node  {
    int data;
    struct Node* next;
    struct Node* prev;
};

struct Node *head, *tail; // Khởi tạo Node head global của dslk đôi.
 
/* tạo node mới */
struct Node* CreateNode(int x) {
    struct Node* newNode
        = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

Tiếp đến ta viết hàm tạo Node CreateNode().

/* tạo node mới */
struct Node* CreateNode(int x) {
    struct Node* newNode
        = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

Để kiểm tra được kết quả của chương trình ta cần một hàm duyệt danh sách: duyệt từ đầu đến cuối (Print()) và duyệt từ cuối về đầu (ReversePrint()).

/* hiển thị từ cuối về đầu */
void ReversePrint() {
    struct Node* temp = tail;
    if(temp == NULL) return; // empty list, exit
    // Traversing backward using prev pointer
    printf("nCuối về đầu: ");
    while(temp != NULL) {
        printf("%d ",temp->data);
        temp = temp->prev;
    }
    printf("n");
}
/* thêm node vào đầu danh sách */
void InsertFirst(int x) {
  //sử dụng hàm tạo Node tạo một Node mới
    struct Node* newNode = CreateNode(x);
   //nếu danh sách rỗng thì node chèn vào vừa là node đầu vừa là node cuối
    if(head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }
    //Nếu danh sách không rỗng thì, dịch chuyển Node head về node mới chèn, và cho con trỏ của newNode trỏ đến Node head
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
}

Và cuối cùng là hai cách thêm Node vào danh sách mà ta đã tìm hiểu ở trên.

/* thêm node vào đầu danh sách */
void InsertFirst(int x) {
  //sử dụng hàm tạo Node tạo một Node mới
    struct Node* newNode = CreateNode(x);
   //nếu danh sách rỗng thì node chèn vào vừa là node đầu vừa là node cuối
    if(head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }
    //Nếu danh sách không rỗng thì, dịch chuyển Node head về node mới chèn, và cho con trỏ của newNode trỏ đến Node head
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
}
/* thêm node vào cuối danh sách */
void InsertLast(int x) {
  //sử dụng hàm tạo Node để tạo node mới newNode
    struct Node* newNode = CreateNode(x);
    //Nếu danh sách rỗng thì newNode vừa là node đầu vừa là node cuối
    if(head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }
    //Nếu danh sách có phần tử thì, 
    tail->next = newNode;// con trỏ next của tail trỏ đến newNode
    newNode->prev = tail;// con trỏ prev của newNode trỏ đến tail
    tail = newNode;//dịch chuyển tail về newNode, vì tail luôn luôn quản lý phần tử cuối cùng trong danh sách
}

Full code:

#include <iostream>
using namespace std;
/* tạo cấu trúc node */
struct Node  {
    int data;
    struct Node* next;
    struct Node* prev;
};

struct Node *head, *tail; // Khởi tạo Node head global của dslk đôi.
 
/* tạo node mới */
struct Node* CreateNode(int x) {
    struct Node* newNode
        = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = x;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}
/* hiển thị từ đầu đến cuối */
void Print() {
    struct Node* temp = head;
    printf("nĐầu đến cuối: ");
    while(temp != NULL) {
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("n");
}
 
/* hiển thị từ cuối về đầu */
void ReversePrint() {
    struct Node* temp = tail;
    if(temp == NULL) return; // empty list, exit
    // Traversing backward using prev pointer
    printf("nCuối về đầu: ");
    while(temp != NULL) {
        printf("%d ",temp->data);
        temp = temp->prev;
    }
    printf("n");
}
/* thêm node vào đầu danh sách */
void InsertFirst(int x) {
  //sử dụng hàm tạo Node tạo một Node mới
    struct Node* newNode = CreateNode(x);
   //nếu danh sách rỗng thì node chèn vào vừa là node đầu vừa là node cuối
    if(head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }
    //Nếu danh sách không rỗng thì, dịch chuyển Node head về node mới chèn, và cho con trỏ của newNode trỏ đến Node head
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
}
/* thêm node vào cuối danh sách */
void InsertLast(int x) {
  //sử dụng hàm tạo Node để tạo node mới newNode
    struct Node* newNode = CreateNode(x);
    //Nếu danh sách rỗng thì newNode vừa là node đầu vừa là node cuối
    if(head == NULL) {
        head = newNode;
        tail = newNode;
        return;
    }
    //Nếu danh sách có phần tử thì, 
    tail->next = newNode;// con trỏ next của tail trỏ đến newNode
    newNode->prev = tail;// con trỏ prev của newNode trỏ đến tail
    tail = newNode;//dịch chuyển tail về newNode, vì tail luôn luôn quản lý phần tử cuối cùng trong danh sách
}
int main() {
 
    head = NULL;
 //gọi hàm thêm node vào đầu danh sách
    
    InsertFirst(2);
    InsertFirst(3);
    InsertFirst(4);
    cout<<"Danh sách sau khi thêm node vào đầu: n";
    Print();
    ReversePrint(); 
    cout<<"n----------end--------------n";
 //gọi hàm thêm node vào cuối danh sách
    InsertLast(5);
    InsertLast(6);
    InsertLast(7);
    cout<<"Danh sách sau khi thêm node vào cuối: n";
    Print(); 
    ReversePrint();
    
    cout<<"n---------------------------------------n";
    cout<<"Chương trình này được đăng tại kiso.vn";
}

Kết quả:

dslk doi 6 PNG

4. Kết luận

Như vậy là chúng ta đã tìm hiểu xong hai cách thêm Node vào danh sách liên kết đôi đó là thêm vào đầu danh sách và thêm vào cuối danh sách. Cũng như thực hiện chương trình thêm Node vào danh sách trong C++. Ở bài tiếp theo mình sẽ hướng dẫn các bạn cách xóa Node trong danh sách liên kết đôi, hãy chú ý theo dõi nhé !!!

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *