Data structure linear list – headed two-way circular linked list

Preface: It’s been a long time, friends. In the last article, we studied the singly linked list, one of the data structures, linear tables, and learned many benefits of the singly linked list. However, it is impossible to have a perfect data structure, even if it is a singly linked list. There will be many disadvantages.

So in today’s article, we will learn the promax version of singly linked list – Leading two-way circular linked list.

1. What is a leading two-way circular linked list

Regarding the leading two-way circular linked list, we split it into four parts: leading, two-way, circular, and linked list. Among them, we already know what is going on with the linked list, so let’s analyze it together with the following figure. The first three concepts.

1. Take the lead

The so-called leader means that at the beginning of the linked list, there is a head node that does not store any data. We usually call it the “sentinel bit”.

So what is the significance of the existence of the sentinel bit? ? ?

It canhelp us perform various operations on linked lists more conveniently. What are the specific advantages? We will demonstrate it by combining the various operations of implementing linked lists later.

2. Two-way

The singly linked list we studied earlier has only one chain between each node, and the next node can only be found from the previous node.

As for a doubly linked list, that is, there are two chains connected between the two nodes. Not only can you find the next one from the previous one, but you can also find the previous one from the latter one.

3. Loop

Loop, as the name suggests, is to connect the head and tail of the linked list to form a circular linked list in a logical sense.

So after understanding the meaning of the leading two-way circular linked list, let’s take a look at how to implement it.

We have since simplified the name of the linked list to double linked list.

2. Implementation of double linked list

1. Definition of double linked list

typedef int DLLDataType;
//define double linked list
typedef struct DLinkList
{
DLLDataType data;
struct DLinkList* prev;//points to the previous node
struct DLinkList* next;//points to the next node
}DLLNode;

The double linked list is based on the single linked list. It has one more prev pointer to point to the previous node, which is easier to understand.

2. Initialization of double linked list

//Initialize double linked list
DLLNode* DLinkListInit()
{
DLLNode* phead = (DLLNode*)malloc(sizeof(DLLNode));
if (phead == NULL)
{
perror("DLinkListInit->malloc");
}
phead->next = phead;
phead->prev = phead;
return phead;
}

The initialization of the double linked list requires creating the sentinel bit first. Considering that the linked list is empty and the linked list still needs to cycle, we set both the prev and next of the sentinel bit. Point to yourself.

DLLNode* dll = DLinkListInit();

To create a double linked list, we are accustomed to using the above method.

Because if we use the singly linked list initialization method, we need to use secondary pointers, but our subsequent operations of various functions of double linked lists have nothing to do with secondary pointers.

So in order to make our double-linked list all completed by first-level pointers, choose to create a double-linked list by receiving function return values.

3. Creation of double linked list nodes

DLLNode* CreateNewNode(DLLDataType x)
{
DLLNode* newnode = (DLLNode*)malloc(sizeof(DLLNode));
if (newnode == NULL)
{
perror("CreateNewNode->malloc");
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}

Creating a new node in a doubly linked list is almost the same as in a singly linked list. One thing to note is Don’t forget to leave the two pointers blank to prevent wild pointers from appearing.

In this way, we have implemented a basic doubly linked list framework. Next, we will implement various basic operations of doubly linked lists.

3. Operation of double linked list

1. Printing of double linked list

So in order to facilitate the testing of other functions, we will first implement the printing function of the double linked list:

void DLinkListPrint(DLLNode* phead)
{
assert(phead);
DLLNode* cur = phead->next;
printf("phead<=>");
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("phead\
");
}

Let’s strictly carry out the assert. If phead is empty, it means that the double-linked list does not exist.

Two points should be noted here:

1. Why is phead->next? ? ?

It is not difficult to understand that when we initialize the double linked list, the return value given to dll is the sentinel bit, but the sentinel bit does not store data, so we have to start from the next node of the sentinel bit.

2. Judgment conditions of while loop

Because we are a loopable linked list, there is no case where cur is empty, but cur will eventually point to the sentinel again. bit, so when cur == phead, it means that we have traversed the double linked list once.

As for the content of the printf function, just for fun, haha, let me show it:

This will allow everyone to understand the double linked list more vividly.

2. Tail insertion of double linked list

What are the advantages of tail insertion in doubly linked lists compared to singly linked lists? ? ?

If you want to insert the end of a singly linked list, you must first perform a loop to find the end. The time complexity is high, but a doubly linked list is easier to do because the one before the sentinel bit The node is the tail, which is phead->prev. Once the tail is found, it will be easy to handle:

//Tail insert
void DLinkListPushBack(DLLNode* phead, DLLDataType x)
{
assert(phead);
DLLNode* newnode = CreateNewNode(x);
DLLNode* tail = phead->prev;
tail->next = newnode;
newnode->next = phead;
newnode->prev = tail;
phead->prev = newnode;
}

Replace tail with tail, the next operation is:

The next of the old tail points to the new tail

The next of the new tail points to the sentinel position

The prev of the new tail points to the old tail

The prev of the sentinel bit points to the new tail

It seems simple, but we know that Singly linked lists must consider the special case of whether the linked list is empty, but Double linked lists do not need to.

Because if the double-linked list is empty, there will only be sentinel bits, and the sentinel bits are connected head to tail. After entering the above code operation, there will be no errors.

3. Tail deletion of double linked list

Tail deletion is even simpler. You only need to find the tail, then find the node before the tail through the tail, then connect this node to the sentinel bit, and then Just set the tail free:

//Delete tail
void DLinkListPopBack(DLLNode*phead)
{
assert(phead);
assert(phead->next != phead);
DLLNode* tail = phead->prev;
DLLNode* tailprev = tail->prev;
phead->prev = tailprev;
tailprev->next = phead;
free(tail);
tail = NULL;
}

Should tail deletion consider the special case of only one node? It still does not need to be done because after an operation, the sentinel bits are still connected end to end.

But tail deletion must consider the situation of empty linked list, because if the linked list is empty, the sentinel bit is free. Once the sentinel bit no longer exists, we will not be able to perform subsequent operations strong>. Therefore, one more assert assertion is required.

At this point, friends, have you already felt the strength of the sentinel position and the doubly linked list.

4. Header insertion of doubly linked list

The head plug is almost the same as the tail plug. I will give the code directly here. I hope my friends can understand and master it by themselves.

//Head plug
void DLinkListPushFront(DLLNode* phead, DLLDataType x)
{
assert(phead);
DLLNode* head = phead->next;
DLLNode* newnode = CreateNewNode(x);
phead->next = newnode;
newnode->next = head;
head->prev = newnode;
newnode->prev = phead;
}

5. Deleting the head of a doubly linked list

Head deletion is similar to tail deletion, and the situation of empty linked list should be considered:

//Delete header
void DLinkListPopFront(DLLNode*phead)
{
assert(phead);
assert(phead->next != phead);
DLLNode* head = phead->next;
DLLNode* headnext = head->next;
phead->next = headnext;
headnext->prev = phead;
free(head);
head = NULL;
}

6. Search in double linked list

If it is a search, then we have to traverse it from the beginning:

//Search
DLLNode* DLinkListFind(DLLNode* phead,DLLDataType x)
{
assert(phead);
DLLNode* cur = phead->next;
while(cur)
{
if (cur->data == x)
return cur;
else
cur = cur->next;
}
return NULL;
}

Still have to pay attention to the conditions of the while loop here, which are the same as the printing of double linked lists.

7. Arbitrary insertion into a doubly linked list

Insertion at any position in a doubly linked list still needs to be combined with a search, because only a search can get the address of the pos position.

But let’s stipulate here that arbitrary insertion means inserting in front of the pos position.

For exampleI want to insert new data in the fourth position of the table, then I have to vacate the fourth position, so that the original fourth position and the ones behind it will move backwards .

In this way, we need to find the previous node of the pos node, which will facilitate our operation:

//pos position insert
void DLinkListInsert(DLLNode* pos, DLLDataType x)
{
assert(pos);
DLLNode* newnode = CreateNewNode(x);
DLLNode* posprev = pos->prev;
posprev->next = newnode;
newnode->prev = posprev;
pos->prev = newnode;
newnode->next = pos;
}

8. Arbitrary deletion of double linked lists

The form of arbitrary deletion is similar to that of arbitrary insertion, except that it is also necessary to record the next node of pos:

//pos position delete
void DLinkListEease(DLLNode* pos)
{
assert(pos);
DLLNode* posprev = pos->prev;
DLLNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
free(pos);
    pos = NULL;
}

9. Modification of double linked list

If you want to modify the data, you still have to use a search operation to find the address where you want to modify the pos position, and then it’s simple:

//pos position change
void DLinkListAmend(DLLNode* pos, DLLDataType x)
{
assert(pos);
pos->data = x;
}

Just modify data directly.

10. Destruction of double linked list

To destroy a double linked list, you also need to traverse and free each space. It is worth noting that the sentinel bits also need to be destroyed:

//Destroy
void DLinkListDestroy(DLLNode*phead)
{
assert(phead);
DLLNode* cur = phead->next;
while (cur != phead)
{
DLLNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}

4. Complete code display

1.DLinkList.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int DLLDataType;
//define double linked list
typedef struct DLinkList
{
DLLDataType data;
struct DLinkList* prev;
struct DLinkList* next;
}DLLNode;

//Initialize double linked list
DLLNode* DLinkListInit();
//Print double linked list
void DLinkListPrint(DLLNode* phead);
//Create new node
DLLNode* CreateNewNode(DLLDataType x);
//Tail insert
void DLinkListPushBack(DLLNode* phead, DLLDataType x);
//Delete tail
void DLinkListPopBack(DLLNode* phead);
//Head plug
void DLinkListPushFront(DLLNode* phead, DLLDataType x);
//Delete header
void DLinkListPopFront(DLLNode* phead);
//Find
DLLNode* DLinkListFind(DLLNode* phead,DLLDataType x);
//pos position insert
void DLinkListInsert(DLLNode* pos, DLLDataType x);
//pos position delete
void DLinkListEease(DLLNode* pos);
//pos position change
void DLinkListAmend(DLLNode* pos,DLLDataType x);
//destroy
void DLinkListDestroy(DLLNode* phead);

2.DLinkList.c

#include "DLinkList.h"
//Initialize double linked list
DLLNode* DLinkListInit()
{
DLLNode* phead = (DLLNode*)malloc(sizeof(DLLNode));
if (phead == NULL)
{
perror("DLinkListInit->malloc");
}
phead->next = phead;
phead->prev = phead;
return phead;
}
//Print double linked list
void DLinkListPrint(DLLNode*phead)
{
assert(phead);
DLLNode* cur = phead->next;
printf("phead<=>");
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("phead\
");
}
//Create new node
DLLNode* CreateNewNode(DLLDataType x)
{
DLLNode* newnode = (DLLNode*)malloc(sizeof(DLLNode));
if (newnode == NULL)
{
perror("CreateNewNode->malloc");
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
//Tail insertion
void DLinkListPushBack(DLLNode* phead, DLLDataType x)
{
assert(phead);
DLLNode* newnode = CreateNewNode(x);
DLLNode* tail = phead->prev;
tail->next = newnode;
newnode->next = phead;
newnode->prev = tail;
phead->prev = newnode;
}
//Delete tail
void DLinkListPopBack(DLLNode* phead)
{
assert(phead);
DLLNode* tail = phead->prev;
DLLNode* tailprev = tail->prev;
phead->prev = tailprev;
tailprev->next = phead;
free(tail);
tail = NULL;
}
//Head plug
void DLinkListPushFront(DLLNode* phead, DLLDataType x)
{
assert(phead);
DLLNode* head = phead->next;
DLLNode* newnode = CreateNewNode(x);
phead->next = newnode;
newnode->next = head;
head->prev = newnode;
newnode->prev = phead;
}
//Delete header
void DLinkListPopFront(DLLNode* phead)
{
assert(phead);
DLLNode* head = phead->next;
DLLNode* headnext = head->next;
phead->next = headnext;
headnext->prev = phead;
free(head);
head = NULL;
}
//Find
DLLNode* DLinkListFind(DLLNode* phead,DLLDataType x)
{
assert(phead);
DLLNode* cur = phead->next;
while(cur)
{
if (cur->data == x)
return cur;
else
cur = cur->next;
}
return NULL;
}
//pos position insert
void DLinkListInsert(DLLNode* pos, DLLDataType x)
{
assert(pos);
DLLNode* newnode = CreateNewNode(x);
DLLNode* posprev = pos->prev;
posprev->next = newnode;
newnode->prev = posprev;
pos->prev = newnode;
newnode->next = pos;
}
//pos position delete
void DLinkListEease(DLLNode* pos)
{
assert(pos);
DLLNode* posprev = pos->prev;
DLLNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
free(pos);
pos = NULL;
}
//pos position change
void DLinkListAmend(DLLNode* pos, DLLDataType x)
{
assert(pos);
pos->data = x;
}
//Destroy
void DLinkListDestroy(DLLNode*phead)
{
assert(phead);
DLLNode* cur = phead->next;
while (cur != phead)
{
DLLNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}

You can test the test code yourself and will not show it here.

5. Summary

Double-linked lists still have great advantages over single-linked lists. It is recommended that you write a double-linked list entirely on your own after learning single-linked lists. This will give you a better understanding of linked lists. Take mastery to the next level!

Finally, I would like to remind everyone not to forget One-click triple connection! ! !

See you next time!

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57517 people are learning the system