C language data structure leading two-way circular linked list

Directory

linked list

double linked list

head node

Diagram with headed doubly linked list

Code

tail insertion of doubly linked list

tail deletion of doubly linked list

header of doubly linked list

Delete the head of the doubly linked list

Doubly linked list lookup

The doubly linked list is inserted in front of the pos position

Doubly linked list deletes the node at position pos

Destruction of doubly linked list

About Interoperability of Linked Lists

full code

linked list

The linked list is a non-sequential and non-sequential storage structure in the physical storage structure, and the logical order of the data elements is realized through the link order of the pointers in the linked list.

In reality, the linked list is like a train, each car is connected, and each car carries passengers or goods.

The same is true for linked lists, nodes are like carriages, they are all linked together, and each node has data.

Double Linked List

Double linked list is that each node has two structure pointers that store addresses, one stores the address of the previous node

One saves the address of the next node, which is used to better find the node.

head node

The head node is generally called a sentinel position. We do not store any data in this sentinel position, but only store the addresses of two nodes.

Naming: head – phead previous node – prev next node – next data to be stored – x specified position – pos

Stored data – data

The above are some names of this linked list.

The graph with the head bidirectional circular linked list

After understanding these, let’s realize the addition, deletion, query and modification of this linked list

Code implementation

Use a structure to store three variables. Use typedef to take an alias: LTNode for use, and give a built-in type int an alias: LTDataType for easy modification.

typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;
struct ListNode* prev;
LTDataType data;
}LTNode;

Create the head node of the returned linked list

The initialization of the linked list needs to apply for space to store the sentinel bits. The sentinel bits only store addresses but not data. Because there are a lot of node spaces to apply for, write a separate function to use it.

The initialization here has a sentinel bit, so the return value is used to return.

header file declaration

//Apply for a new node
LTNode* BuyLTNode(LTDataType x);
//Create the head node of the returned linked list
LTNode* LTInit();

accomplish

//Apply for a new node
LTNode* BuyLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}

newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}

// Create the head node of the returned linked list
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);

phead->next = phead;
phead->prev = phead;

return phead;
}

Initialized state diagram

Tail insertion of doubly linked list

It is recommended to define a tail to store the next address of the head node, so that it can be connected casually when connecting.

tail is the tail node and newnode is the new node. If you do not define tail and rely on the next (phead->next) of the head node to link, it will be very troublesome when we link, we need to distinguish the order, otherwise the node will not be found.
After defining a tail, because we have the address of the next node, we can link at will without distinguishing the sequence.

After inserting, we can also print the result of inserting

statement

//The tail insertion of the linked list
void LTPushBack(LTNode* phead, LTDataType x);

accomplish

//Tail insertion of the doubly linked list
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);

LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);

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

use

void LTTest1()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
}

int main()
{
LTTest1();
return 0;
}

print result

Tail deletion of doubly linked list

The tail deletion of the linked list is very simple. Define a tail (tail) to delete, and then find the previous one, called tailprev. This records, two nodes. Then tail, free off. At this time, the tail is released, so the next of tailprev has no address, and the address of the head node phead needs to be saved. Save the address of tailprev in the prev of phead. All links are done.

But when the tail is deleted and the head node is deleted at the end, we will have problems when inserting. So we need to use assert to make an assertion, in case we delete it until there is a problem at the end.

The judgment of the assertion here is to write a function to return true or false. When LTEmpty judges that the next of phead is equal to phead, it returns true, and then we negate it again, so that the assert judgment can be false, and if it is false, it will trigger the assertion to end the program.

statement

//Tail deletion of double linked list
void LTPopBak(LTNode* phead);
//judgment empty
bool LTEmpty(LTNode* phead);

accomplish

//judgment empty
bool LTEmpty(LTNode* phead)
{
assert(phead);

return phead->next == phead;
}

// tail deletion of double linked list
void LTPopBak(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));

LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;

free(tail);

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

use

void LTTest1()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);

LTPopBak(plist);
LTPrint(plist);
LTPopBak(plist);
LTPrint(plist);
LTPopBak(plist);
LTPrint(plist);
LTPopBak(plist);
LTPrint(plist);
}

int main()
{
LTTest1();
return 0;
}

print result

Of course, after the deletion, the assertion will work. You can see that there is a problem in the function, and then you can follow the vine to find it.

head plug of doubly linked list

There is not much difference between the head insertion and tail insertion of the linked list. Use newnode to store the new node, and then next to store the next address of the head node for easy search.

The following is the same link as the tail plug. Because the address behind the head node is stored, it can be linked at will.

statement

//The header of the linked list
void LTPushFront(LTNode* phead, LTDataType x);

accomplish

//The header of the linked list
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);

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

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

use

void LTTest2()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);

LTPrint(plist);
}

int main()
{
LTTest2();
return 0;
}

print result

Delete the head of the doubly linked list

The head deletion and tail deletion of the linked list are similar, first stores the address of phead’s next, and second stores the address of first’s next.

Because the first is to be deleted, the address of second is stored in next of phead, and the address of prev is stored in second.

statement

//Delete the head of the linked list
void LTPopFront(LTNode* phead);

accomplish

//Delete the head of the linked list
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));

LTNode* first = phead->next;
LTNode* second = first->next;

phead->next = second;
second->prev = phead;

free(first);
}

use

Here is one more deletion, so it will be asserted and reported as an error

void LTTest2()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);

LTPrint(plist);

LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPrint(plist);
}

int main()
{
LTTest2();
return 0;
}

result print

Search for doubly linked list

The search of this linked list needs to be coordinated, and the insertion of the pos position is used. This is to run the linked list to find the value, and return the address of the node if it is found.

statement

// Doubly linked list lookup
LTNode* LTFind(LTNode* phead, LTDataType x);

accomplish

// Doubly linked list lookup
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}

cur = cur->next;
}
return NULL;
}

The doubly linked list is inserted before the pos position

There is no difference between the front insertion at the pos position, the head insertion, and the rear insertion.

Use pos here to save the address returned by LTFind, and then judge whether pos is empty, and insert it if it is not empty.

statement

// The doubly linked list is inserted in front of pos
void LTInsert(LTNode* pos, LTDataType x);

accomplish

// The doubly linked list is inserted in front of pos
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyLTNode(x);
LTNode* posPrev = pos->prev;

newnode->next = pos;
newnode->prev = posPrev;
posPrev->next = newnode;
pos->prev = newnode;
}

use

void LTTest3()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);

LTNode* pos = LTFind(plist, 2);
if (pos)
{
LTInsert(pos, 20);
}
LTPrint(plist);

}

int main()
{
LTTest3();
return 0;
}

Doubly linked list deletes node at position pos

There is no difference between deleting the pos position and deleting the tail and deleting the head.

statement

// Doubly linked list deletes the node at position pos
void LTErase(LTNode* pos);

accomplish

// Doubly linked list deletes the node at position pos
void LTErase(LTNode* pos)
{
assert(pos);
assert(!LTEmpty(pos));

LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;

posPrev->next = posNext;
posNext->prev = posPrev;

free(pos);
}

use

void LTTest3()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);

LTNode* pos = LTFind(plist, 2);
if (pos)
{
LTInsert(pos, 20);
}
LTPrint(plist);

LTErase(pos);
LTPrint(plist);
}

int main()
{
LTTest3();
return 0;
}

Destruction of doubly linked list

Destruction is to delete all nodes in the linked list free. Use a loop to delete nodes, and after deletion, just delete the sentinel position (head node). After use, empty the plist by the way.

statement

// Doubly linked list destruction
void LTDDestroy(LTNode* phead);

accomplish

// Doubly linked list destruction
void LTDDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}

use

void LTTest3()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);

LTNode* pos = LTFind(plist, 2);
if (pos)
{
LTInsert(pos, 20);
}
LTPrint(plist);

LTErase(pos);
LTPrint(plist);

LTDDestroy(plist);
plist = NULL;
}

int main()
{
LTTest3();
return 0;
}

About the interoperability of linked lists

On the top, you can see the pos position of inserting and deleting before pos. There is not much difference between head-to-tail insertion and head-to-tail deletion.

In this way, it seems that we can directly use the function inserted before pos to realize head insertion and tail insertion. Delete the pos position to realize the deletion of the head and the tail.

All the things that should be implemented above have been realized, and the code for the realization is directly given below.

Interoperability of tail plugs

The node to be deleted is at the prev position of phead. Just insert before pos and give the phead position. function will find itself

//Tail insertion of the doubly linked list
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);

LTInsert(phead, x);
}

interoperability

The position of the tail deletion is the previous one of phead

//Tail deletion of double linked list
void LTPopBak(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));

LTErase(phead->prev);
}

plug interoperability

The position of the head plug is the next position of the phead, just pass the value to it

//The header of the linked list
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);

LTInsert(phead->next, x);
}

header interoperability

The position of head deletion is the next one of phead

//Delete the head of the linked list
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));

LTErase(phead->next);
}

full code

The files I use have 3 header files, function implementation files, and main function files.

Header file List.h

#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>

typedef int LTDataType;

typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
LTDataType data;
}LTNode;

//Apply for a new node
LTNode* BuyLTNode(LTDataType x);
//Linked list initialization
LTNode* LTInit();
//End of linked list
void LTPushBack(LTNode* phead, LTDataType x);
// tail deletion of double linked list
void LTPopBak(LTNode* phead);
//judgment empty
bool LTEmpty(LTNode* phead);
//The header of the linked list
void LTPushFront(LTNode* phead, LTDataType x);
// Delete the head of the linked list
void LTPopFront(LTNode* phead);
// doubly linked list lookup
LTNode* LTFind(LTNode* phead, LTDataType x);
// The doubly linked list is inserted in front of pos
void LTInsert(LTNode* pos, LTDataType x);
// The doubly linked list deletes the node at position pos
void LTErase(LTNode* pos);
// doubly linked list destruction
void LTDDestroy(LTNode* phead);

Function implementation file List.c

#include "List.h"

//Apply for a new node
LTNode* BuyLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}

newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}

//Print
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\
");
}

//Doubly linked list initialization
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);

phead->next = phead;
phead->prev = phead;

return phead;
}

//Tail insertion of doubly linked list
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);

LTInsert(phead, x);
//LTNode* tail = phead->prev;
//LTNode* newnode = BuyLTNode(x);

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

// tail deletion of double linked list
void LTPopBak(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));

LTErase(phead->prev);
//LTNode* tail = phead->prev;
//LTNode* tailPrev = tail->prev;

//free(tail);

//tailPrev->next = phead;
//phead->prev = tailPrev;
}

//The header of the linked list
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);

LTInsert(phead->next, x);
//LTNode* newnode = BuyLTNode(x);
//LTNode* next = phead->next;

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

// Delete the head of the linked list
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));

LTErase(phead->next);
//LTNode* first = phead->next;
//LTNode* second = first->next;

//phead->next = second;
//second->prev = phead;

//free(first);
}

// Doubly linked list lookup
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}

cur = cur->next;
}
return NULL;
}

// The doubly linked list is inserted in front of pos
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyLTNode(x);
LTNode* posPrev = pos->prev;

newnode->next = pos;
newnode->prev = posPrev;
posPrev->next = newnode;
pos->prev = newnode;
}

// The doubly linked list deletes the node at position pos
void LTErase(LTNode* pos)
{
assert(pos);
assert(!LTEmpty(pos));

LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;

posPrev->next = posNext;
posNext->prev = posPrev;

free(pos);
}

//judgment empty
bool LTEmpty(LTNode* phead)
{
assert(phead);

return phead->next == phead;
}

// Doubly linked list destruction
void LTDDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}

Main function file Test.c

Here are my usage tests for all functions.

#include "List.h"

void LTTest1()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);

LTPopBak(plist);
LTPrint(plist);
LTPopBak(plist);
LTPrint(plist);
LTPopBak(plist);
LTPrint(plist);
LTPopBak(plist);
LTPrint(plist);
//LTPopBak(plist);
//LTPrint(plist);
}

void LTTest2()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);

LTPrint(plist);

LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
//LTPopFront(plist);
//LTPrint(plist);
}

void LTTest3()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);

LTNode* pos = LTFind(plist, 2);
if (pos)
{
LTInsert(pos, 20);
}
LTPrint(plist);

LTErase(pos);
LTPrint(plist);

LTDDestroy(plist);
plist = NULL;
}

int main()
{
LTTest3();
return 0;
}

Finally, thank you for watching. If there is something wrong there, please suggest it and discuss it. in vain

linked list

Double Linked List

head node

Code implementation

Tail insertion of doubly linked list

Tail deletion of doubly linked list

head plug of doubly linked list

Delete the head of the doubly linked list

Search for doubly linked list

The doubly linked list is inserted before the pos position

Doubly linked list deletes node at position pos

Destruction of doubly linked list

About the interoperability of linked lists

full code