C++ realized bidirectional circular linked list

This article example Shared C++ realization bidirectional circular linked list specific code for your reference, the specific content is as follows

1. The concept

1. Each node in the double-linked list should have two link Pointers:

lLink - > Pointer to a precursor node (precursor pointer or left chain pointer)

rLink- > A pointer to a successor node (backdrive or right chain pointer)

2. Double-linked list usually adopts the circular linked list method with additional head node:

first: A header pointer that does not hold data, or data that is specifically requested. Its lLink points to the last node of the double-linked list,

Its rLink points to the first node of the double-linked list (the first valid node). The left pointer to the first node of a linked list, lLink, and the right pointer to the last node

rLink points to additional headers.

2. Implementation procedures

1.DblList.h

#ifndef DblList_h
#define DblList_h
#include <iostream>
using namespace std;
 
template <class T>
struct DblNode { //  Linked list node definition 
 T data;
 DblNode<T> *lLink, *rLink; //  List precursor (left chain) and successor (right chain) Pointers 
 DblNode(DblNode<T> *left = NULL, DblNode<T> *right = NULL):lLink(left), rLink(right){} //  The constructor 
 DblNode(T value, DblNode<T> *left = NULL, DblNode<T> *right = NULL):data(value), lLink(left), rLink(right){} //  The constructor 
};
 
template <class T>
class DblList { //  Double linked list (bidirectional circular list) 
public:
 DblList(); //  Constructor: Creates additional headers 
 ~DblList(); //  Destructor: Frees all storage 
 void createDblList(); //  Create a bidirectional linked list 
 int Length()const; //  Calculate the length of the double linked list 
 bool isEmpty(); //  Null double linked list 
 DblNode<T> *getHead()const; //  Take the additional head 
 void setHead(DblNode<T> *ptr); //  Sets the address of the additional head node 
 DblNode<T> *Search(const T x); //  In the linked list, look for values equal to the given value in the following direction x The node 
 DblNode<T> *Locate(int i, int d); //  Locate the control in the linked list i A node, d=0 Press forerunner direction, otherwise press successor direction 
 bool Insert(int i, const T x, int d); //  In the first i I'm going to insert the node x . d=0 Press forerunner direction, otherwise press successor direction 
 bool Remove(int i, T &x, int d); //  Delete the first i A node, x Back to delete its value, d=0 Press forerunner direction, otherwise press successor direction 
 void Output(); //  Outputs data from a double-linked list 
private:
 DblNode<T> *first; //  Additional head 
};
 
template <class T>
DblList<T>::DblList() {
 //  Constructor: Creates additional headers 
 first = new DblNode<T>();
 if(NULL == first) {
  cerr << " Dynamic allocation of memory space failed! " << endl;
  exit(1);
 }
 first->rLink = first->lLink = first; //  Point to their own 
}
 
template <class T>
DblList<T>::~DblList() { //  Destructor: Frees all storage 
 DblNode<T> *current = first->rLink;
 while(current != first) {
  current->rLink->lLink = current->lLink; //  from lLink In the chain off 
  current->lLink->rLink = current->rLink; //  from rLink In the chain off 
  delete current; //  Release the space 
  current = first->rLink;
 }
 delete first;
 first = NULL;
}
 
template <class T>
void DblList<T>::createDblList() {
 //  Create a bidirectional linked list 
 int n, val;
 DblNode<T> *current = first;
 cout << " Please enter the number you want to enter n:";
 cin >> n;
 cout << " Please enter the number you want to enter: " << endl;
 for(int i = 0; i < n; i++) {
  cin >> val;
  DblNode<T> *newNode = new DblNode<T>(val);
  if(NULL == newNode) {
   cerr << " Dynamic allocation of memory space failed! " << endl;
   exit(1);
  }
  //  The tail insertion 
  while(current->rLink != first)
   current = current->rLink; //  We're going to move in the direction 
  newNode->rLink = current->rLink;
  current->rLink = newNode;
  newNode->rLink->lLink = newNode;
  newNode->lLink = current;
  current = current->rLink; // current Move back 
 }
}
 
template <class T>
int DblList<T>::Length()const {
 //  Calculate the length of the double linked list 
 DblNode<T> *current = first->rLink;
 int count = 0;
 
 while(current != first) {
  current = current->rLink;
  count++;
 }
 return count;
}
 
template <class T>
bool DblList<T>::isEmpty() {
 //  Null double linked list 
 return first->rLink == first;
}
 
template <class T>
DblNode<T> *DblList<T>::getHead()const {
 //  Take the additional head 
 return first;
}
 
template <class T>
void DblList<T>::setHead(DblNode<T> *ptr) {
 //  Sets the address of the additional head node 
 first = ptr;
}
 
template <class T>
DblNode<T> *DblList<T>::Search(const T x) {
 //  In the linked list, look for values equal to the given value in the following direction x The node 
 DblNode<T> *current = first->rLink;
 while(current != first && current->data != x)
  current = current->rLink;
 if(current != first)
  return current; //  Search success 
 else //  Search failure 
  return NULL;
}
 
template <class T>
DblNode<T> *DblList<T>::Locate(int i, int d) {
 //  positioning 
 if((first->rLink == first) || (i = 0))
  return first;
 DblNode<T> *current;
 if(d == 0)
  current = first->lLink; //  Search the front direction 
 else
  current = first->rLink;
 for(int j = 1; j < i; j++)
 {
  if(current == first)
   break;
  else if(d == 0)
   current = current->lLink;
  else
   current = current->rLink;
 }
 if(current != first) //  Positioning success 
  return current;
 else
  return NULL;
}
 
template <class T>
bool DblList<T>::Insert(int i, const T x, int d) {
 //  insert 
 DblNode<T> *current = Locate(i, d); //  Find the first i A node 
 if(current == NULL) // i Unreasonable. Insert failed 
  return false;
 DblNode<T> *newNode = new DblNode<T>(x);
 if(newNode == NULL) {
  cerr << " Memory space allocation failed! " << endl;
  exit(1);
 }
 if(d == 0) { //  Insert in the front direction 
  newNode->lLink = current->lLink;
  current->lLink = newNode;
  newNode->lLink->rLink = newNode;
  newNode->rLink = current;
 }
 else { //  Subsequent direction insertion 
  newNode->rLink = current->rLink;
  current->rLink = newNode;
  newNode->rLink->lLink = newNode;
  newNode->lLink = current;
 }
 return true;
}
 
template <class T>
bool DblList<T>::Remove(int i, T &x, int d) {
 //  delete 
 DblNode<T> *current = Locate(i, d); //  Find the first i A node 
 if(current == NULL) // i Unreasonable. Insert failed 
  return false;
 current->rLink->lLink = current->lLink; //  from lLink In the chain off 
 current->lLink->rLink = current->rLink; //  from rLink In the chain off 
 x = current->data;
 delete current; //  Release the space 
 current = NULL; //  Point to the empty 
 return true; //  Delete the success 
}
 
template <class T>
void DblList<T>::Output() {
 //  Outputs data from a double-linked list 
 DblNode<T> *current = first->rLink;
 while(current != first) {
  cout << current->data << " ";
  current = current->rLink;
 }
 cout << endl;
}
 
#endif /* DblList_h */

2.main.cpp

#include "DblList.h"
using namespace std;
 
int main(int argc, const char * argv[]) {
 int finished = 0, choice, i, x, d, len; // i Stored in the first i A, d: Storage direction  - " 0 Represents the direction of the precursor, or the direction of the successor 
 DblList<int> L;
 DblNode<int> *head = NULL, *current;
 
 while(!finished) {
  cout << "\n********* The menu *********\n";
  cout << "1: Create a double linked list \n";
  cout << "2: The length of a double linked list \n";
  cout << "3: Is the double linked list empty? \n";
  cout << "4: Take the additional head \n";
  cout << "5: Sets the address of the additional head node \n";
  cout << "6: In the linked list, look for values equal to the given value in the following direction x The node \n";
  cout << "7: Locate the control in the linked list i A node, d=0 Press forerunner direction, otherwise press successor direction \n";
  cout << "8: In the first i I'm going to insert the node x . d=0 Press forerunner direction, otherwise press successor direction \n";
  cout << "9: Delete the first i A node, x Back to delete its value, d=0 Press forerunner direction, otherwise press successor direction \n";
  cout << "10: Outputs data from a double-linked list :\n";
  cout << "11: exit \n";
  cout << " Please enter options [1-11] : \n";
  cin >> choice;
  switch(choice) {
   case 1:
    L.createDblList(); //  Create a double linked list 
    break;
   case 2:
    len = L.Length(); //  The length of a double linked list 
    cout << " The length of the double-linked list is: " << len << endl;
    break;
   case 3:
    if(L.isEmpty()) //  Whether the double linked list is empty 
     cout << " The double linked list is empty " << endl;
    else
     cout << " The double linked list is not empty " << endl;
    break;
   case 4:
    head = L.getHead();
    break;
   case 5:
    L.setHead(head); //  Sets the address of the additional head node 
    break;
   case 6:
    cout << " Enter the value you are looking for x:";
    cin >> x;
    if(L.Search(x) != NULL)
     cout << " Search successful! " << endl;
    else
     cout << " Search failed! " << endl;
    break;
   case 7:
    cout << " Please enter the to position number i A node i And the direction d(d=0 Press forerunner direction, otherwise press successor direction ):";
    cin >> i >> d;
    current = L.Locate(i, d);
    if(current == NULL)
     cout << " To locate failure !" << endl;
    else
     cout << " Successful positioning! " << endl;
    break;
   case 8:
    cout << " In the first i I'm going to insert the node x . d=0 Press forerunner direction, otherwise press successor direction. Please enter the i, x and d:";
    cin >> i >> x >> d;
    if(L.Insert(i, x, d))
     cout << " Insert the success !" << endl;
    else
     cout << " Insert failed! " << endl;
    break;
   case 9:
    cout << " Delete the first i A node, x Back to delete its value, d=0 Press forerunner direction, otherwise press successor direction. Please enter the i and d:";
    cin >> i >> d;
    if(L.Remove(i, x, d))
     cout << " The deletion succeeded, and the deleted value was: " << x << endl;
    else
     cout << " Delete failed! " << endl;
    break;
   case 10:
    cout << " The data in the double-linked list is: " << endl;
    L.Output();
    break;
   case 11:
    finished = 1;
    break;
   default:
    cout << " Input error ,  Please re-enter! " << endl;
  } // switch
 } // while
 return 0;
}