Chương trình C ++ để triển khai danh sách được liên kết kép

Danh sách liên kết đôi là một loại cấu trúc dữ liệu được tạo thành từ các nút được tạo bằng cách sử dụng cấu trúc tự tham chiếu. Mỗi nút này chứa ba phần, đó là dữ liệu và tham chiếu đến nút danh sách tiếp theo và tham chiếu đến nút danh sách trước đó.

Chỉ cần tham chiếu đến nút danh sách đầu tiên để truy cập toàn bộ danh sách được liên kết. Đây được gọi là người đứng đầu. Nút cuối cùng trong danh sách trỏ đến không có gì để nó lưu trữ NULL trong phần đó. Ngoài ra, danh sách được liên kết kép có thể được duyệt theo cả hai hướng khi mỗi nút trỏ đến nút trước đó và nút tiếp theo của nó.

Một chương trình để triển khai danh sách liên kết kép được đưa ra như sau.

Ví dụ

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *prev;
   struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
   struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
   newnode->data = newdata;
   newnode->prev = NULL;
   newnode->next = head;
   if(head != NULL)
   head->prev = newnode ;
   head = newnode;
}
void display() {
   struct Node* ptr;
   ptr = head;
   while(ptr != NULL) {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   }
}
int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   insert(9);
   cout<<"The doubly linked list is: ";
   display();
   return 0;
}

đầu ra

The doubly linked list is: 9 2 7 1 3

Trong chương trình trên, Node cấu trúc tạo thành nút danh sách được liên kết kép. Nó chứa dữ liệu và một con trỏ đến nút danh sách liên kết tiếp theo và trước đó. Điều này được đưa ra như sau.

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

Hàm insert () chèn dữ liệu vào đầu danh sách được liên kết kép. Nó tạo một newnode và chèn số vào trường dữ liệu của newnode. Sau đó, con trỏ hiện tại trong newnode trỏ đến NULL khi nó được nhập ở đầu và con trỏ tiếp theo trỏ đến phần đầu. Nếu phần đầu không phải là NULL thì con trỏ của phần đầu sẽ trỏ đến nút mới. Cuối cùng, phần đầu là newnode, tức là danh sách được liên kết bắt đầu từ đó. Điều này được đưa ra bên dưới.

void insert(int newdata) {
   struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
   newnode->data = newdata;
   newnode->prev = NULL;
   newnode->next = head;
   if(head != NULL)
   head->prev = newnode ;
   head = newnode;
}

Hàm display () hiển thị toàn bộ danh sách được liên kết kép. Ptr đầu tiên chỉ vào đầu. Sau đó, nó liên tục được chuyển tiếp đến nút tiếp theo cho đến khi tất cả các giá trị dữ liệu của các nút được in ra. Điều này được đưa ra bên dưới.

void display() {
   struct Node* ptr;
   ptr = head;
   while(ptr != NULL) {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   }
}

Trong hàm main (), các giá trị khác nhau đầu tiên được chèn vào danh sách liên kết kép bằng cách gọi insert (). Sau đó, danh sách liên kết kép được hiển thị. Điều này được đưa ra bên dưới.

int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   insert(9);
   cout<<"The doubly linked list is: ";
   display();
   return 0;
}