이중 연결 목록을 구현하는 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

위의 프로그램에서 Node 구조체는 이중 연결 리스트 노드를 형성합니다. 여기에는 데이터와 다음 및 이전 연결 목록 노드에 대한 포인터가 포함됩니다. 이것은 다음과 같이 주어집니다.

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

insert() 함수는 이중 연결 목록의 시작 부분에 데이터를 삽입합니다. newnode를 생성하고 newnode의 데이터 필드에 숫자를 삽입합니다. 그런 다음 newnode의 prev 포인터는 처음에 입력된 NULL을 가리키고 다음 포인터는 헤드를 가리킵니다. 헤드가 NULL이 아니면 헤드의 이전 포인터가 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;
}