Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++의 이중 연결 순환 목록

<시간/>

순환 연결 목록은 첫 번째 요소가 마지막 요소를 가리키고 마지막 요소가 첫 번째 요소를 가리키는 연결 목록의 변형입니다. 단일 연결 목록과 이중 연결 목록 모두 순환 연결 목록으로 만들 수 있습니다.

이중 연결 리스트에서 마지막 노드의 다음 포인터는 첫 번째 노드를 가리키고 첫 번째 노드의 이전 포인터는 마지막 노드를 가리켜 양방향으로 원형을 만듭니다.

C++의 이중 연결 순환 목록

위의 그림에 따라 다음은 고려해야 할 중요한 사항입니다.

  • 마지막 링크의 다음 링크는 이중 연결 목록에서 목록의 첫 번째 링크를 가리킵니다.

  • 첫 번째 링크의 이전은 이중 연결 목록의 마지막을 가리킵니다.

알고리즘

displayForward():
Begin
      ptr := head
   while ptr := null, do
      print ptr ->key, ptr ->data
      ptr := ptr -> next
   done
End
displayBackward():
Begin
   ptr := last
   while ptr := null, do
      print ptr ->key, ptr ->data
      ptr := ptr -> prev
   done
End
insertFirst(key, data):
Begin
   create new node with key and data
   if list is empty, then
      last := node
   else
      head -> prev := node
   end if
   node -> next := head
   head := node
End
insertLast (key, data):
Begin
   create new node with key and data
   if list is empty, then
      last := node
   else
      last -> next := node
      node -> prev:= last
   end if
   last := node
End
insertAfter(key, newKey, data):
Begin
   current := head
   if head is null, then return false
   while key of current is not key, do
      if current -> next is not null, then
         return false
      else
         current := next of current
      end if
   done
   create new node with newKey and data
   if current = last, then
      next of node := null
      last := node
   else
      next of node := next of current
      prev of next of current := node
   end if
   prev of node := current
   next of current := node
   return true;
End
deleteFirst():
Begin
   tempNode := head
   if next of head is null, then
      last := null
   else
      prev of next of head := null
   end if
   head := next of head
   return tempNode
End
deleteLast():
Begin
   tempNode := last
   if next of head is null, then
      head := null
   else
      next of prev of last := null
   end if
   last := prev of last
   return tempNode
End
deleteNode(key):
Begin
   curr := head and prev := null
   if head is null, then
      return null
   end if
   while key of currr is not same as key, do
      if next of curr is null, then
         return null
      else
         prev := curr
         curr := next of curr
      end if
   done
   if curr is head, then head := next of head, otherwise next of prev of curr = next of curr
   if curr is last, then last := prev of curr, otherwise prev of next of curr = prev of curr
   return curr
End

예시

#include <iostream<
using namespace std;
class node {
   public:
      int data;
      int key;
      node *next;
   node *prev;
};
//this link always point to first Link
node *head = NULL;
//this link always point to last Link
node *last = NULL;
node *current = NULL;
//is list empty
bool isEmpty() {
   return head == NULL;
}
int length() {
   int length = 0;
   node *current;
   for(current = head; current != NULL; current = current->next){
      length++;
   }
   return length;
}
//display the list in from first to last
void displayForward() {
   //start from the beginning
   node *ptr = head;
   //navigate till the end of the list
   printf("\n[ ");
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
   printf(" ]");
}
//display the list from last to first
void displayBackward() {
   //start from the last
   node *ptr = last;
   //navigate till the start of the list
   printf("\n[ ");
   while(ptr != NULL) {
      //print data
      printf("(%d,%d) ",ptr->key,ptr->data);
      //move to next item
      ptr = ptr ->prev;
   }
}
//insert link at the first location
void insertFirst(int key, int data) {
   //create a link
   node *link = new node();
   link->key = key;
   link->data = data;
   if(isEmpty()) {
      //make it the last link
      last = link;
   }
   else {
      //update first prev link
      head->prev = link;
   }
   //point it to old first link
   link->next = head;
   //point first to new first link
   head = link;
}
//insert link at the last location
void insertLast(int key, int data) {
   //create a link
   node *link = new node();
   link->key = key;
   link->data = data;
   if(isEmpty()) {
      //make it the last link
      last = link;
   }
   else {
      //make link a new last link
      last->next = link;
      //mark old last node as prev of new link
      link->prev = last;
   }
   //point last to new last node
   last = link;
}
//delete first item
node* deleteFirst() {
   //save reference to first link
   node *tempLink = head;
   //if only one link
   if(head->next == NULL){
      last = NULL;
   }
   else {
      head->next->prev = NULL;
   }
   head = head->next;
   //return the deleted link
   return tempLink;
}
//delete link at the last location
node* deleteLast() {
   //save reference to last link
   node *tempLink = last;
   //if only one link
   if(head->next == NULL) {
      head = NULL;
   }
   else {
      last->prev->next = NULL;
   }
   last = last->prev;
   //return the deleted link
   return tempLink;
}
//delete a link with given key
node* del(int key) {
   //start from the first link
   node* current = head;
   node* previous = NULL;
   //if list is empty
   if(head == NULL) {
      return NULL;
   }
   //navigate through list
   while(current->key != key) {
      //if it is last node
      if(current->next == NULL) {
         return NULL;
      }
      else {
         //store reference to current link
         previous = current;
         //move to next link
         current = current->next;
      }
   }
   //found a match, update the link
   if(current == head) {
      //change first to point to next link
      head = head->next;
   }
   else {
      //bypass the current link
      current->prev->next = current->next;
   }
   if(current == last) {
      //change last to point to prev link
      last = current->prev;
   }
   else {
      current->next->prev = current->prev;
   }
   return current;
}
bool insertAfter(int key, int newKey, int data) {
   //start from the first link
   node *current = head;
   //if list is empty
   if(head == NULL) {
      return false;
   }
   //navigate through list
   while(current->key != key) {
      //if it is last node
      if(current->next == NULL) {
         return false;
      }
      else {
         //move to next link
         current = current->next;
      }
   }
   //create a link
   node *newLink = new node();
   newLink->key = newKey;
   newLink->data = data;
   if(current == last) {
      newLink->next = NULL;
      last = newLink;
   }
   else {
      newLink->next = current->next;
      current->next->prev = newLink;
   }
   newLink->prev = current;
   current->next = newLink;
   return true;
}
main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   printf("\nList (First to Last): ");
   displayForward();
   printf("\n");
   printf("\nList (Last to first): ");
   displayBackward();
   printf("\nList , after deleting first record: ");
   deleteFirst();
   displayForward();
   printf("\nList , after deleting last record: ");
   deleteLast();
   displayForward();
   printf("\nList , insert after key(4) : ");
   insertAfter(4,7, 13);
   displayForward();
   printf("\nList , after delete key(4) : ");
   del(4);
   displayForward();
}

출력

List (First to Last):
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
List (Last to first):
[ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56)
List , after deleting first record:
[ (5,40) (4,1) (3,30) (2,20) (1,10) ]
List , after deleting last record:
[ (5,40) (4,1) (3,30) (2,20) ]
List , insert after key(4) :
[ (5,40) (4,1) (7,13) (3,30) (2,20) ]
List , after delete key(4) :
[ (5,40) (7,13) (3,30) (2,20) ]