Unidirectional lists have been introduced in # 01- unidirectional lists and # 02- unidirectional cyclic lists. This article will introduce bidirectional lists.

First, the design of bidirectional linked list

In a unidirectional list, a next pointer points to the next node. In a bidirectional list, a prior pointer points to the previous node, so that the current node can be obtained from next, and prior can obtain the precursor. The node design is as follows:

Through such node design, the chain structure of the bidirectional linked list can be obtained as follows:

Two design ideas of bidirectional linked list:

  • 1. The first is the design of bidirectional linked list with head node;
  • 2. The second is the design of bidirectional linked list without head node.

Bidirectional linked list features:

  • 1. Have a unique first node and a unique last node;
  • 2. Prior on the first node is NULL, and next on the last node is NULL.
  • 3. Prior refers to the prior, and next refers to the subsequent.

The advantages of a head node are already known in # 01 and # 02, so we also design a head node when designing a bidirectional list.

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 createLinkList(LinkList *L){// Create a head Node and point *L to the head Node *L = (LinkList)malloc(sizeof(Node)); if (*L == NULL) return ERROR; // Next and prior = NULL (*L)->prior = NULL; (*L)->next = NULL; (*L)->data = -1; LinkList p = *L; For (int I =0; i < 10; LinkList temp = (LinkList)malloc(sizeof(Node)); temp->prior = NULL; temp->next = NULL; temp->data = i; P ->next = temp; Temp ->prior = p; P = p->next; } return OK; }Copy the code
  • To create a bidirectional linked list, you need to create oneHead node, according to the nature of the bidirectional linked list, at this time the head nodeThe prior and nextShould be directedNULL;
  • useThe tail interpolationWhen inserting data into the list, the newly created node is placed at the end of the list, the previous last node’s next points to the new node, and the new node’s prior points to the previous last node.
  • recordThe tail of the nodelocationFacilitate the next insertion of data.

Third, traverse

void display(LinkList L){ LinkList temp = L->next; If (temp == NULL){printf(" Print bidirectional linked list is empty! \n"); return; } while (temp) { printf("%d ",temp->data); temp = temp->next; } printf("\n"); }Copy the code

The key to traversal is knowing where to end, which, by the nature of bidirectional lists, ends when next points to NULL.

Four, insert,

Status ListInsert(LinkList *L, int i, ElemType data){ //1. If (I < 1) return ERROR; LinkList temp = (LinkList)malloc(sizeof(Node)); temp->data = data; temp->prior = NULL; temp->next = NULL; //3. Point p to the header! LinkList p = *L; For (int j = 1; j < i && p; j++) { p = p->next; } //5. If (p == NULL){return ERROR; } //6. Check whether the insertion position is the end of the list; if (p->next == NULL) { p->next = temp; temp->prior = p; }else {//1️ prior = temp p->next->prior = temp; //2️ one ->next points to original p->next temp->next = p->next; //3️ one ->next p->next = temp; //4️ new temp precursor = p temp->prior = p; } return OK; }Copy the code
  • When inserting data, you first need to determine the inserted datalocationWhether or notlegal;
  • To find the target locationBefore aNode to judge whether the effective insertion position is finally found;
  • Create a new node, following the characteristics of the bidirectional linked list: first the target locationNext of the previous nodePoint to theThe new node; Secondly, there are two situations as follows:
  • 1. If the insertion position isEnd nodeThe location of the,Next for the new nodePoint to theNext of the previous node(now pointing to NULL),Prior of the new nodePoint to theFront node;
  • 2. If the insertion positionnotEnd node,Next for the new nodePoint to theNodes in the back.priorPoint to theFront node;Next of the previous nodePoint to theThe new node.Prior of the following nodePoint to the new node.

As shown in the figure above, when p is inserted into the list, it may be inserted at the position of the first element node, at the position of the last node, or at some other position. Because of the existence of the head node, we know that next and prior are not NULL on any node except the tail node, so we need to do special processing for the tail node.

5. Delete the specified location

Status ListDelete(LinkList *L, int i, ElemType *e){ int k = 1; LinkList p = (*L); //1. Check whether the bidirectional list is empty, if so, return ERROR; if (*L == NULL) { return ERROR; } //2. Find the previous node of the destination while (k < I && p! = NULL) { p = p->next; k++; } / / 3. If k > I or p = = NULL is returned ERROR if (k > I | | p = = NULL) {return ERROR; } // create a temporary pointer to the node to be deleted, and assign the data of the node to *e back to LinkList delTemp = p->next; *e = delTemp->data; P ->next = delTemp->next; //6. If the next node to be deleted is not null, then the precursor pointer to the next node to be deleted is assigned p; if (delTemp->next ! = NULL) { delTemp->next->prior = p; } //7. Delete delTemp node free(delTemp); return OK; }Copy the code
  • Delete again to determine the current deletelocationWhether it is legal;
  • findRemove nodesAnd delete the nodeprecursor;
  • precursorNext points to the nodedeleteNext of the node;
  • andinsertAgain, needjudgeDelete a node. Yes NoEnd node;
  • 1. If you delete the end node, do nothing (next points to NULL on the precursor node). ;
  • 2. If it is deletednotThe end node that needs to be removed from the nodepriorOf the node to be deletedprecursor.

Delete the specified element

Status LinkListDeletVAL(LinkList *L, int data){ LinkList p = *L; If (p->data == data) {// Next = p->prior->next = p-> next = p->prior->next = p->next; // If (p->next! = NULL){ p->next->prior = p->prior; } // delete node p free(p); // Exit loop break; } p p = p->next; } return OK; }Copy the code

There may be data in the linked list with the same data in each data domain, so it is necessary to traverse the whole linked list to find all the data that meet the criteria for deletion.

Seven, query

int selectElem(LinkList L,ElemType elem){

    LinkList p = L->next;
    int i = 1;
    
    while (p) {
        if (p->data == elem) {
           return i;
        }
        i++;
        p = p->next;
    }

    return  -1;
}
Copy the code

The query is divided into the query of the specified location of the element and the query of the location of the specified element, the former result is unique, the latter result may be multiple, the above method is to query the location of the specified element, in the query of the first condition of the location will be returned.

Eight, modify,

Status replaceLinkList(LinkList *L,int index,ElemType newElem){
    if (index < 1) return ERROR;
    
    LinkList p = (*L)->next;

    for (int i = 1; i < index; i++) {
        p = p->next;
    }

    p->data = newElem;
    return OK;
}
Copy the code

Instead of managing whether to modify, query, delete, or insert, the first thing you should determine is whether the location of the operation is legal. The handling of abnormal cases is the key to ensure the stability and robustness of an algorithm.

Nine,

The importance of the head node is also clearly reflected in the bidirectional linked list. The tail node should be treated specially in the deletion and insertion of the bidirectional linked list containing the head node.