โปรแกรม C++ เพื่อใช้งานรายการที่เชื่อมโยงเป็นสองเท่า

รายการที่เชื่อมโยงแบบทวีคูณเป็นโครงสร้างข้อมูลประเภทหนึ่งที่ประกอบด้วยโหนดที่สร้างขึ้นโดยใช้โครงสร้างการอ้างอิงตนเอง แต่ละโหนดเหล่านี้ประกอบด้วยสามส่วน ได้แก่ ข้อมูลและการอ้างอิงไปยังโหนดรายการถัดไป และการอ้างอิงไปยังโหนดรายการก่อนหน้า

จำเป็นต้องอ้างอิงถึงโหนดรายการแรกเท่านั้นเพื่อเข้าถึงรายการที่เชื่อมโยงทั้งหมด นี้เรียกว่าหัว โหนดสุดท้ายในรายการชี้ไปที่ไม่มีอะไรเลย ดังนั้นจึงเก็บค่า NULL ไว้ในส่วนนั้น นอกจากนี้ รายการที่เชื่อมโยงแบบทวีคูณสามารถข้ามไปได้ทั้งสองทิศทาง เนื่องจากแต่ละโหนดจะชี้ไปยังโหนดก่อนหน้าและโหนดถัดไป

มีโปรแกรมสำหรับใช้งานรายการเชื่อมโยงแบบทวีคูณดังนี้

ตัวอย่าง

#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;
}

ผลลัพธ์

The doubly linked list is: 9 2 7 1 3

ในโปรแกรมข้างต้น โครงสร้างโหนดจะสร้างโหนดรายการที่มีการเชื่อมโยงแบบทวีคูณ ประกอบด้วยข้อมูลและตัวชี้ไปยังโหนดรายการที่เชื่อมโยงถัดไปและก่อนหน้า ได้ดังนี้

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

ฟังก์ชัน insert() แทรกข้อมูลลงในจุดเริ่มต้นของรายการที่เชื่อมโยงเป็นสองเท่า มันสร้างโหนดใหม่และแทรกตัวเลขในฟิลด์ข้อมูลของโหนดใหม่ จากนั้นตัวชี้ก่อนหน้าในโหนดใหม่จะชี้ไปที่ NULL เมื่อป้อนไว้ที่จุดเริ่มต้น และตัวชี้ถัดไปจะชี้ไปที่ส่วนหัว ถ้า head ไม่เป็น NULL ให้ prev pointer ของ head ชี้ไปที่ newnode ในที่สุดส่วนหัวก็คือโหนดใหม่นั่นคือรายการที่เชื่อมโยงเริ่มต้นจากที่นั่น ด้านล่างนี้

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;
}

ฟังก์ชั่น display() แสดงรายการที่เชื่อมโยงเป็นสองเท่าทั้งหมด ptr แรกชี้ไปที่หัว จากนั้นจะส่งต่อไปยังโหนดถัดไปอย่างต่อเนื่องจนกว่าจะพิมพ์ค่าข้อมูลทั้งหมดของโหนด ด้านล่างนี้

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

ในฟังก์ชัน main() ค่าต่าง ๆ แรกจะถูกแทรกลงในรายการที่เชื่อมโยงเป็นสองเท่าโดยการเรียก insert() จากนั้นแสดงรายการที่เชื่อมโยงแบบทวีคูณ ด้านล่างนี้

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