Implementation of bidirectional linked list (c language data structure)

catalogue

Functions to be realized

Realization of specific functions

1. Create a new node

2. Initialization of bidirectional linked list

3. Tail insertion of two-way linked list

4. Printing of bidirectional linked list

5. Header deletion of two-way linked list

6. Destruction of two-way linked list

7. Node search of bidirectional linked list

8. The two-way linked list is inserted before the pos position

9. Delete the node at the target location

10. Header deletion

11. Deletion

Summary

The following are the test documents

Functions to be realized

The following is defined in our list H file to declare the functions that we need to implement in the two-way linked list.

The two-way linked list carries the pre node and post node of the node, which can access the pre elements of the node more conveniently than the single linked list.

At the same time, we use a two-way linked list with sentinel positions. The next pointer of our tail node points to our sentinel position, and the front node of our sentinel position points to our tail node.

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
    struct ListNode*next;
    struct ListNode*prev;
    LTDataType data;
}LTNode;
LTNode* BuyListNode(LTDataType x);


// Create the head node of the return linked list
LTNode *ListInit();
// Bidirectional linked list destruction
void ListDestory(LTNode* pHead);
// Bidirectional linked list printing
void ListPrint(LTNode*phead);
// Bidirectional linked list tail insertion
void ListPushBack(LTNode*phead,LTDataType x);
// Bidirectional linked list tail deletion
void ListPopBack(LTNode* pHead);
// Bidirectional chain header insertion
void ListPushFront(LTNode*phead,LTDataType x);
// Bidirectional linked list header deletion
void ListPopFront(LTNode* pHead);
// Bidirectional linked list lookup
LTNode * ListFind(LTNode* pHead, LTDataType x);
// The two-way linked list is inserted in the front pos
void ListInsert(LTNode* pos, LTDataType x);
// Two way linked list deletes the node at pos
void ListErase(LTNode* pos);

Realization of specific functions

1. Create a new node

We open up a new element, modify the data in the node to our incoming data, and empty our pre node and post node.

LTNode* BuyListNode(LTDataType x)
{
    LTNode *node=(LTNode*)malloc(sizeof(LTNode));
    if(node==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    node->data=x;
    node->next=NULL;
    node->prev=NULL;
    return node;
}

2. Initialization of bidirectional linked list

LTNode *ListInit()
{
    LTNode *phead= BuyListNode(-1);
    phead->next=phead;
    phead->prev=phead;
    return phead;
}

3. Tail insertion of two-way linked list

void ListPushBack(LTNode*phead,LTDataType x)
{
    assert(phead);
    LTNode* newnode= BuyListNode(x);
    LTNode*tail=phead->prev;
    tail->next=newnode;
    newnode->prev=tail;
    newnode->next=phead;
    phead->prev=newnode;
}

4. Printing of bidirectional linked list

void ListPrint(LTNode*phead)
{
    assert(phead);
    LTNode *temp=phead->next;
    while(temp!=phead)
    {
        printf("%d->",temp->data);
        temp=temp->next;
    }
    printf("\n");
    printf("All contents in the linked list have been printed successfully\n");
}

5. Header deletion of two-way linked list

void ListPushFront(LTNode*phead,LTDataType x)
{
    assert(phead);

    LTNode*newnode= BuyListNode(x);
    LTNode *next=phead->next;

    phead->next=newnode;
    newnode->prev=phead;
    newnode->next=next;
    next->prev=newnode;
}

6. Destruction of two-way linked list

void ListDestory(LTNode* pHead)
{
    LTNode *p=pHead->next;
    while(p!=pHead)
    {
        LTNode *pp=p;
        p=p->next;
        free(pp);
    }
    pHead->next=pHead;
    pHead->prev=pHead;
    printf("The entire linked list has been successfully destroyed\n");
}

7. Node search of bidirectional linked list

LTNode * ListFind(LTNode* pHead, LTDataType x)
{
    assert(pHead);
    LTNode *p=pHead->next;
    while(p!=pHead&&p->data!=x)
    {
        p=p->next;
    }
    if(p->data==x)
    {
        return p;
    }
    else
    {
        printf("Not found\n");
        return NULL;
    }
}

8. The two-way linked list is inserted before the pos position

void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode *p=pos->prev;
    LTNode *newnode= BuyListNode(x);
    newnode->next=pos;
    pos->prev=newnode;
    p->next=newnode;
    newnode->prev=p;
    printf("Insert successfully implemented%d\n",x);
}

9. Delete the node at the target location

void ListErase(LTNode* pos)
{
    assert(pos);
    LTNode *p=pos->prev;
    p->next=pos->next;
    pos->prev=p;
    printf("Successfully deleted%d\n",pos->data);
    free(pos);
}

10. Header deletion

We only need to call our previous delete function to delete the first node of our linked list, that is, the next node of our sentinel node

void ListPopFront(LTNode* pHead)
{
    ListErase(pHead->next);
}

11. Deletion

Since the leading pointer of the sentinel position of our two-way linked list points to the tail node of our two-way linked list, we can find our tail node only through the leading node of the sentinel position node of our two-way linked list, and then call our function to delete the specified position to delete our tail node.

void ListPopFront(LTNode* pHead)
{
    ListErase(pHead->next);
}

Summary

The following code is written in the list C in the document

#include "List.h"
LTNode* BuyListNode(LTDataType x)
{
    LTNode *node=(LTNode*)malloc(sizeof(LTNode));
    if(node==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    node->data=x;
    node->next=NULL;
    node->prev=NULL;
    return node;
}
LTNode *ListInit()
{
    LTNode *phead= BuyListNode(-1);
    phead->next=phead;
    phead->prev=phead;
    return phead;
}
void ListPushBack(LTNode*phead,LTDataType x)
{
    assert(phead);
    LTNode* newnode= BuyListNode(x);
    LTNode*tail=phead->prev;
    tail->next=newnode;
    newnode->prev=tail;
    newnode->next=phead;
    phead->prev=newnode;
}
void ListPrint(LTNode*phead)
{
    assert(phead);
    LTNode *temp=phead->next;
    while(temp!=phead)
    {
        printf("%d->",temp->data);
        temp=temp->next;
    }
    printf("\n");
    printf("All contents in the linked list have been printed successfully\n");
}

void ListPushFront(LTNode*phead,LTDataType x)
{
    assert(phead);

    LTNode*newnode= BuyListNode(x);
    LTNode *next=phead->next;

    phead->next=newnode;
    newnode->prev=phead;
    newnode->next=next;
    next->prev=newnode;
}
void ListDestory(LTNode* pHead)
{
    LTNode *p=pHead->next;
    while(p!=pHead)
    {
        LTNode *pp=p;
        p=p->next;
        free(pp);
    }
    pHead->next=pHead;
    pHead->prev=pHead;
    printf("The entire linked list has been successfully destroyed\n");
}
LTNode * ListFind(LTNode* pHead, LTDataType x)
{
    assert(pHead);
    LTNode *p=pHead->next;
    while(p!=pHead&&p->data!=x)
    {
        p=p->next;
    }
    if(p->data==x)
    {
        return p;
    }
    else
    {
        printf("Not found\n");
        return NULL;
    }
}
void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode *p=pos->prev;
    LTNode *newnode= BuyListNode(x);
    newnode->next=pos;
    pos->prev=newnode;
    p->next=newnode;
    newnode->prev=p;
    printf("Insert successfully implemented%d\n",x);
}
void ListErase(LTNode* pos)
{
    assert(pos);
    LTNode *p=pos->prev;
    p->next=pos->next;
    pos->prev=p;
    printf("Successfully deleted%d\n",pos->data);
    free(pos);
}
void ListPopFront(LTNode* pHead)
{
    ListErase(pHead->next);
}
void ListPopBack(LTNode* pHead)
{
    ListErase(pHead->prev);
}

The following are the test documents

#include"List.h"
int main() {
    LTNode* plist=ListInit();
    ListPushBack(plist,5);
    ListPushBack(plist,10);
    ListPushBack(plist,53);
    ListPushBack(plist,9);
    ListPushBack(plist,3);
    ListPushBack(plist,34);
    ListPushBack(plist,5);
    ListPushFront(plist,9);
    ListPrint(plist);
    ListInsert(ListFind(plist,9),8);
    ListPrint(plist);

//    ListErase(ListFind(plist,53));
    ListPopFront(plist);
    ListPrint(plist);
    ListPopBack(plist);
    ListPrint(plist);
    ListDestory(plist);
    return 0;
}

 

Tags: C data structure linked list

Posted by wolfcry044 on Fri, 13 May 2022 02:09:49 +0300