Double linked list of linear list

Definition of double linked list

typedef struct DNode {
    
    int data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

Initialization of double linked list

bool InitDLinkList(DLinkList &L) {
    
    L = (DNode *) malloc(sizeof(DNode));
    if (L == NULL) return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}

Double linked list empty judgment operation

bool Empty(DLinkList L) {
    
    return L->next == NULL;
}

Establishment of double linked list

The first interpolation

DLinkList HeadInsert(DLinkList &L) {
    
    InitDLinkList(L);
    int x;
    scanf("%d", &x);
    while (x != 9999) {
    
        DNode *s = (DNode *) malloc(sizeof(DNode));
        s->data = x;
        if (L->next == NULL) {
    	// Determine whether there are other nodes 
            s->next = NULL;
            L->next = s;
            s->prior = L;
        } else {
    
            s->next = L->next;
            L->next->prior = s;

            L->next = s;
            s->prior = L;
        }
        scanf("%d", &x);
    }
    return L;
}

The tail interpolation

DLinkList TailInsert(DLinkList &L) {
    
    InitDLinkList(L);
    DNode *r = L;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
    
        DNode *s = (DNode *) malloc(sizeof(DNode));
        s->data = x;
        s->next = NULL;
        s->prior = r;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    return L;
}

Insertion of double linked list

The tail interpolation

// To insert by tail insertion 
void TailInsertList(DLinkList &L, int i, int e) {
    
    DNode *p = GetElem(L, i);
    //printf(" The first %d Value of bit order  = %d\n", i, p->data);
    DNode *s = (DNode *) malloc(sizeof(DNode));
    s->data = e;  // Assign to new s node 
    s->next = p->next;
    if (p->next != NULL)
        p->next->prior = s;

    p->next = s;
    s->prior = p;
}

Double linked list search

Search by bit

DNode *GetElem(DLinkList L, int i) {
    
    int j = 1;
    DNode *p = L->next;
    if (i == 0)return L;
    if (i < 1)return NULL;
    while (p && j < i) {
    
        p = p->next;
        j++;
    }
    return p;
}

According to the value lookup

DNode *LocateElem(DLinkList L, int x) {
    
    DNode *p = L->next;
    while (p && p->data != x) {
    
        p = p->next;
    }
    return p;
}

Deletion of double linked list

// Delete p The successor node of the node 
bool DeleteNextDNode(DLinkList &L, int i) {
    
    DNode *p = GetElem(L, i-1);
    DNode *q = p->next;
    printf("p=%d\n", q->data);
    if (q == NULL) return false;
    p->next = q->next;
    if (p->next != NULL)
        q->next->prior = p;
    free(q);
    return true;
}

Traversal of double linked list

void PrintList(DLinkList L) {
    
    DNode *p = L->next;
    while (p) {
    
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

Be careful

Among the values searched in bit order , i Is the order

Insert ( Tail insertion ) In operation , Insert bit order to i Behind , GetElem(L, i);

Delete ( Deletion at the end ) In operation , Delete the bit order as i Value , That is to find the bit order i-1 The node of ,GetElem(L, i-1);

Special attention should be paid to the critical value ! ! !

Complete code

/** * @Author JiaHaoHao * @Date 2022/07/01 17:18 * @ClassName: test12 * @Description:  Double linked list ( Leading node ) */
#include "stdio.h"
#include "stdlib.h"

typedef struct DNode {
    
    int data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

// initialization 
bool InitDLinkList(DLinkList &L) {
    
    L = (DNode *) malloc(sizeof(DNode));
    if (L == NULL) return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}

// Determine whether it is null 
bool Empty(DLinkList L) {
    
    return L->next == NULL;
}

// stay p Insert after the node s node 
bool InsertNextDNode(DNode *p) {
    
    DNode *s = (DNode *) malloc(sizeof(DNode));
    s->next = p->next;
    if (p->next != NULL)
        p->next->prior = s;

    s->prior = p;
    p->next = s;
}

// Head insertion method to establish double linked list 
DLinkList HeadInsert(DLinkList &L) {
    
    InitDLinkList(L);
    int x;
    scanf("%d", &x);
    while (x != 9999) {
    
        DNode *s = (DNode *) malloc(sizeof(DNode));
        s->data = x;
        if (L->next == NULL) {
      // Determine whether there are other nodes 
            s->next = NULL;
            L->next = s;
            s->prior = L;
        } else {
    
            s->next = L->next;
            L->next->prior = s;

            L->next = s;
            s->prior = L;
        }
        scanf("%d", &x);
    }
    return L;
}

// Tail insertion method to create double linked list 
DLinkList TailInsert(DLinkList &L) {
    
    InitDLinkList(L);
    DNode *r = L;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
    
        DNode *s = (DNode *) malloc(sizeof(DNode));
        s->data = x;
        s->next = NULL;
        s->prior = r;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    return L;
}

// Traversal operation 
void PrintList(DLinkList L) {
    
    DNode *p = L->next;
    while (p) {
    
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

// According to the value lookup 
DNode *LocateElem(DLinkList L, int x) {
    
    DNode *p = L->next;
    while (p && p->data != x) {
    
        p = p->next;
    }
    return p;
}

// Search by bit 
DNode *GetElem(DLinkList L, int i) {
    
    int j = 1;
    DNode *p = L->next;
    if (i == 0)return L;
    if (i < 1)return NULL;
    while (p && j < i) {
    
        p = p->next;
        j++;
    }
    return p;
}

// To insert by tail insertion 
void TailInsertList(DLinkList &L, int i, int e) {
    
    DNode *p = GetElem(L, i);
    printf(" The first %d Value of bit order  = %d\n", i, p->data);
    DNode *s = (DNode *) malloc(sizeof(DNode));
    s->data = e;  // Assign to new s node 
    s->next = p->next;
    if (p->next != NULL)
        p->next->prior = s;

    p->next = s;
    s->prior = p;
}

// Delete p The successor node of the node 
bool DeleteNextDNode(DLinkList &L, int i) {
    
    DNode *p = GetElem(L, i - 1);
    DNode *q = p->next;
    printf("p=%d\n", q->data);
    if (q == NULL) return false;
    p->next = q->next;
    if (p->next != NULL)
        q->next->prior = p;
    free(q);
    return true;
}

int main() {
    
    DLinkList L;

// HeadInsert(L); // Head insertion 
    TailInsert(L);  // Tail insertion 

    PrintList(L);

    //printf(" Bit order search : %d\n", GetElem(L, 1));
    //(" value finding : %d\n", LocateElem(L, 1));

    //DeleteNextDNode(L, 4); // Delete operation 

    TailInsertList(L, 3, 8);

    PrintList(L);

    return 0;
}