In # 03– Bidirectional lists, we designed bidirectional lists by adding head nodes. This article also designed bidirectional lists by adding head nodes.

First, the design of bidirectional circular linked list

The node design of a bidirectional circular list is the same as that of a bidirectional list:

Under the design of both head nodes, bidirectional cyclic lists and bidirectional linked listsThe differenceLies at the end of a bidirectional circular listnextPoint to theHead node, of the head nodepriorPoint to theEnd node:

Features of bidirectional cyclic lists:

  • 1. There areThe onlytheThe first oneNodes andThe last oneNode;
  • 2. Of the first nodepriorPoint to theEnd node, of the last nodenextPoint to theHead node;
  • 3. Prior refers to the prior, and next refers to the subsequent.

To prepare

Some data types have been redefined to make it easier for function calls to return some status values:

#define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define MAXSIZE 20 */ typedef int Status; / / typedef int ElemType; / / typedef int ElemType; /* ElemType specifies the value of the value. The value is assumed to be int */Copy the code

Define the node

Typedef struct Node{ElemType data; Struct Node *prior; Struct Node *next; // point to subsequent}Node; typedef struct Node * LinkList; // Redefine the type nameCopy the code

Second, create

Status creatLinkList(LinkList *L){// Create a header and add it to the list *L = (LinkList)malloc(sizeof(Node)); if (*L == NULL) { return ERROR; } // Next = (*L)->next = (*L); (*L)->prior = (*L); LinkList p = *L; for(int i=0; i < 10; LinkList temp = (LinkList)malloc(sizeof(Node)); temp->data = i; P ->next = temp; p->next = temp; // prior = p; *L temp->next = (*L); *L temp->next = (*L); / / p < = > \ < = > * L / / (4) precursor is the new temp * * L L - > the prior = temp; ⑤ p = p->next; } return OK; }Copy the code
  • Bidirectional circular linked list is created when addedThe first nodeAfter, in order to maintain the characteristics of the bidirectional cyclic linked list, the head nodenextandpriorShould be directedoneself;

  • useThe tail interpolationIn a bidirectional circular linked listfooterAfter inserting data, not only do you need toThe new nodeWith the originalEnd nodeEstablish connections,Prior of the headerAlso want to point toThe new node;
  • The key of the tail insertion method is to find the tail node, so using a variable to record the position of the tail node can effectively improve the efficiency of the next data insertion.

Three, insert,

Insert the next pointer to the header, prior to the previous pointer, and next to the tail does not point to NULL. Insert the next pointer to the header, prior to the previous pointer, and next to the tail does not point to NULL. Next on the tail of the bidirectional linked list points to NULL. If you use it to access next, crash will occur.

Status LinkListInsert(LinkList *L, int index, ElemType e){ //1. LinkList p = (*L); int i = 1; If (*L == NULL) return error; While (I < index && p->next! = *L) { p = p->next; i++; } //4. If (I >index) return error; LinkList temp = (LinkList)malloc(sizeof(Node)); If (temp == NULL) return error; E. Temp ->data = e; // set temp to p; temp->prior = p; //9. Temp's successor points to p->next; temp->next = p->next; //10.p is a new node temp; p->next = temp; Temp ->next->prior = temp; return OK; }Copy the code
  • First, determine whether the insertion position is legal;
  • Find the node p before the target position, and judge whether the effective node is found;
  • Create a new node temp, set the data;
  • Of the new node tempThe prior to p, tempNext points to NEXT of P;
  • Prior to the next node of p refers to the new node temp, so that temp is inserted after p.
  • becauseBidirectional circular linked listsOf each node ofNext, and the priorThey don’t point toNULL, soDon't have toLike the insertion of a bidirectional linked listEnd nodeDo extrajudge.

Fourth, traverse

Status Display(LinkList L){if (L == NULL) {printf(" Print bidirectional loop list is empty! \n\n"); return ERROR; } printf(" two-way circular list contents: "); LinkList p = L->next; while (p ! = L) { printf("%d ",p->data); p = p->next; } printf("\n\n"); return OK; }Copy the code

The key to traversal is knowing when to end the traversal, the two-way loop ends when next points to L.

Five, delete,

Status LinkListDelete(LinkList *L,int index,ElemType *e){ int i = 1; LinkList temp = (*L)->next; if (*L == NULL) { return ERROR; } if(temp->next == *L){return ERROR; While (I <= index && temp! = *L) {//temp ! Temp = temp->next; i++; If (temp == *L) reture ERROR; *e = temp->data; Next temp->prior->next = temp->next; = temp->next->prior = temp->prior; //5. Delete node temp free(temp); return OK; }Copy the code
  • Before deleting a node, check whether the linked listIs emptyOr have aeffectiveNode;
  • findDelete nodesTemp, and the tempCan'tforL, becauseL points to thetaThe first node, *L indicates that node deletion is invalid.
  • Before deleting node temp, change the value of tempPrecursors and subsequent connectionsRise up;
  • freeRelease the node.

Six, the general section

  • The lookup and modification of a bidirectional list is the same logic as the implementation of a bidirectional list,The differenceIs to traverse theThe end of theThe judgment of the end of the bidirectional list is:p->next == NULL; The end judgment of a bidirectional circular list is:p->next == L;
  • Bidirectional circular linked listsDon't have toAdditional insertion and deletion of endpointsjudgeBecause theEnd nodeThe next point toThe first node, the header can be accessedpriorWithout causing a crash.