Several insertion, deletion and specified location output of bidirectional linked list

Appearance of two-way linked list

A two-way linked list is composed of a precursor pointer, a descendant pointer and a data field. The front and back pointers between nodes are connected to form a linked list

Encapsulation of bidirectional linked list nodes

Compared with a single linked list, a two-way linked list has only one more precursor pointer

typedef struct Node {
    int data;//content
    struct Node* frontNode;//Precursor pointer
    struct Node* nextNode;//Subsequent pointer
}*LPNODE;

The characteristic of bidirectional linked list is that it can output the linked list from left to right or from right to left. Therefore, a head node and tail node need to point to the head and tail of the linked list respectively to realize the sequential or reverse printing of the linked list

Encapsulated linked list

typedef struct List {
    struct Node* HeadNode;//Head node
    struct Node* TailNode;//Tail node
    int curSize;//Wanjinyou parameters
}*LPLIST;

Wanjinyou parameter is responsible for recording the number of nodes to facilitate subsequent condition judgment

Create head and tail nodes

Here, it mainly plays the role of encapsulating the head node and tail node. The function initializes the node and returns the corresponding node

LPNODE CreateHeadNode() {
    LPNODE headNode = (LPNODE)malloc(sizeof(Node));//Dynamically request memory of a node size
    assert(headNode);//Air judgment
    headNode->frontNode = NULL;
    headNode->nextNode = NULL;
    return headNode;
}
LPNODE CreateTailNode() {
    LPNODE tailNode = (LPNODE)malloc(sizeof(Node));
    assert(tailNode);
    tailNode->frontNode = NULL;
    tailNode->nextNode = NULL;
    return tailNode;
}

NULL is determined because the memory application may fail and return NULL. This function is to avoid affecting the operation of subsequent pointers due to assignment to NULL pointers.

Create a new node

LPNODE CreateNode(int data) {
    LPNODE newNode = (LPNODE)malloc(sizeof(Node));
    assert(newNode);
    newNode->data = data;//Unlike the head node and tail node, the node to be inserted is to initialize data
    newNode->frontNode = NULL;
    newNode->nextNode = NULL;
    return newNode;
}

The purpose of creating a new node is to facilitate the creation of subsequent new nodes

Create linked list and initialize data

LPLIST CreateList() {
    LPLIST list = (LPLIST)malloc(sizeof(List));//Request a List size memory
    assert(list);//Air judgment
    list->curSize = 0;//The current node is 0
    list->HeadNode = CreateHeadNode();//Initialize header node
    list->TailNode =CreateTailNode();//Initialize tail node
    return list;
}

Head insertion

The key point here is that when the node is 0, the next node of the head node is NULL. If you want to insert again, you must require the precursor pointer of the next node of the head node to point to the new node. Here, because the node is NULL, you can't manually operate the NULL pointer to cause an interrupt

The tail node points to the last node, because the head interpolation is always inserted in the middle, and the position of the tail node at the end has not changed

The code is as follows:

void insertByHead(LPLIST list, int data) {
    LPNODE newNode = CreateNode(data);
    if(list->curSize==0)//When there are no nodes
        list->TailNode = newNode;//Point to a new node for the node
    else {
        newNode->nextNode = list->HeadNode->nextNode;//The trailing pointer of the new node points to the next of the header node
        list->HeadNode->nextNode->frontNode = newNode;//The precursor pointer of the new node points to the new node
    }
    list->HeadNode->nextNode = newNode;//The trailing pointer of the header node points to the new node
    newNode->frontNode = list->HeadNode;//The precursor pointer of the new node points to the head node
    list->curSize++;//Each time one is inserted, the number of nodes is increased by one
}

Tail interpolation

The key point of tail interpolation is similar to that of head interpolation, because when the node is 0, the subsequent pointer will be null

In addition, every new node inserted is the tail node, and the direction of the tail node should be changed

The code is as follows:

void insertByTail(LPLIST list, int data) {
    LPNODE newNode = CreateNode(data);
    if (list->curSize == 0)//When node is empty
        list->HeadNode =newNode;
    else {
        list->TailNode->nextNode = newNode;//Straight in the back
        newNode->frontNode = list->TailNode;
    }
    list->TailNode = newNode;//Change tail node
    list->curSize++;
}

Insert at specified location

Idea: prepare a pointer in the front and a pointer in the back. The two pointers go hand in hand. When the later pointer points to the specified position, insert the data between the two pointers

The point here is that if the specified data is not found, the data should be inserted behind the linked list, and the tail node changes at the same time

The code is as follows:

void insertByAppoint(LPLIST list, int data, int posData) {
    LPNODE LeftNode = list->HeadNode->nextNode;//Left pointer
    LPNODE curNode = list->HeadNode->nextNode;//Current pointer
    while (curNode != NULL && curNode->data != posData) {//Keep looking if you don't find it. The CurNode found is empty
        LeftNode = curNode;//Move left pointer
        curNode = curNode->nextNode;//Move current pointer
    }
    LPNODE newNode = CreateNode(data);//Create a new node
    //After that, insert the middle operation
    LeftNode->nextNode = newNode;
    newNode->frontNode = LeftNode;
    if (curNode == NULL)//Tail node change
        list->TailNode = newNode;
    if (curNode != NULL) {
        newNode->nextNode = curNode;
        curNode->frontNode = newNode;
    }
    list->curSize++;//Increase in the number of nodes
}

Node deletion

The idea here is similar to the above. Prepare two pointers, one in the front and one in the back, going hand in hand. When the position of the node to be deleted is found, stop moving, connect the next node of the rear pointer with the node pointed to by the front pointer, and finally release the memory of the node pointed to by the rear pointer

The code is as follows:

void DeleteByAppoint(LPLIST list, int posData) {
    LPNODE frontNode = list->HeadNode;//Front pointer
    LPNODE curNode = list->HeadNode;//Current pointer
    while (curNode != NULL && curNode->data != posData) {
        frontNode = curNode;
        curNode = curNode->nextNode;
    }
    if (curNode == NULL)//Return if not found
        return;
    //Connect nodes in front of and behind curNode
    frontNode->nextNode = curNode->nextNode;
    curNode->nextNode->frontNode = frontNode;
    free(curNode);//Free memory
    curNode = NULL;
    list->curSize--;//Delete one node and one node less
}

Orderly insertion of linked list

Prepare a pile of disorderly data and return the ordered linked list through orderly insertion

Idea: insert one by one in order. When the value of the next node is larger or smaller than the value in the node to be inserted, insert it in front of the node to form a sort from small to large or from large to small. If it is not found, insert it in the back

main points:

1. If you want to insert to the back, you don't need to point the predecessor pointer of the subsequent pointer to the front node, because misoperation of the null pointer will cause program interruption

2. When a new node is inserted into the last position, the tail node will change

The code is as follows:

void insertBySqList(LPLIST list, int Mydata) {
    LPNODE frontNode = list->HeadNode;//Front pointer
    LPNODE PosNode = list->HeadNode->nextNode;//Specify position pointer
    while (PosNode != NULL && PosNode->data < Mydata) {
        frontNode = PosNode;//move
        PosNode = PosNode->nextNode;//move
    }
    LPNODE newNode = CreateNode(Mydata);//New node creation
    frontNode->nextNode = newNode;
    newNode->frontNode = frontNode;
    if (PosNode == NULL)//Change tail node
        list->TailNode = newNode;
    if (PosNode != NULL) {
        PosNode->frontNode = newNode;
        newNode->nextNode = PosNode;
    }
    list->curSize++;
}

Print linked list

You can print from beginning to end or from end to end

1. From beginning to end

void printListByHead(LPLIST list) {
    printf("Head output:\t");
    LPNODE pMove = list->HeadNode->nextNode;
    while (pMove) {
        printf("%d\t", pMove->data);
        pMove = pMove->nextNode;
    }
    printf("\n");
}

2. From end to end

void printListByTail(LPLIST list) {
    printf("Tail output:\t");
    LPNODE pMove = list->TailNode;
    while (pMove!=list->HeadNode) {
        printf("%d\t", pMove->data);
        pMove = pMove->frontNode;
    }
    printf("\n");
}

Test code:

For the beauty of the console output data, I added some line breaks and text modifiers

The code is as follows:

int main() {
    LPLIST list = CreateList();
    printf("\n Tail interpolation\n");
    for (int i = 0; i < 5; i++)
        insertByTail(list, i);
    printListByHead(list);
    printListByTail(list);
    printf("Delete specified data");
    DeleteByAppoint(list, 3);
    printListByHead(list);
    LPLIST list2 = CreateList();
    printf("\n Head insertion\n");
    for (int i = 0; i < 5; i++)
        insertByHead(list2, i);
    printListByHead(list2);
    printListByTail(list2);
    printf("Delete specified data");
    DeleteByAppoint(list2, 2);
    printListByTail(list2);
    printf("Inserts the of the specified data");
    insertByAppoint(list2, 100, 2);
    printListByTail(list2);
    printf("Inserts the of the specified data");
    printListByHead(list2);
    LPLIST list3 = CreateList();
    int array[] = { 3,5,9,7,2,6 };
    printf("Construction of ordered linked list");
    for(int i=0;i<6;i++)
    insertBySqList(list3, array[i]);
    printListByTail(list3);
    printf("Construction of ordered linked list");
    printListByHead(list3);
    return 0;
}

The operation effect is as follows: