catalogue
1, What is a two-way circular linked list
II Advantages and disadvantages of two-way cyclic linked list
III How to create a two-way circular linked list
1, What is a two-way circular linked list
Definition: lead two-way circular linked list: the most complex structure, which is generally used to store data separately. The linked list data structure used in practice is a two-way circular linked list. In addition, although the structure is complex, you will find that the structure will bring many advantages after code implementation, but the implementation is simple. We will know after code implementation. The specific implementation process is shown in the figure below.
II Advantages and disadvantages of two-way cyclic linked list
Bidirectional circular linked list
Advantages: the two-way leading circular linked list has the advantages of precursor and successor, that is, it can be found in both directions
Disadvantages: subscript random access is not supported
Advantages and disadvantages of sequence table
Advantages: relatively speaking, the space utilization rate is higher, no additional space is required, and the occupied space is small (the linked list needs to store pointers). Physical space is continuous. Support random access and subscript access (maximum advantage); Cache hit rate is high.
Disadvantages: inserting or deleting data in the head or middle requires moving one by one, with high time complexity but small space complexity
III How to create a two-way circular linked list
1. First create the structure, then create the head node (equivalent to the sentry position), and link the new node through the head node
typedef struct ListNode
{
struct ListNode*prev;
struct ListNode*next;
LTDataType data;
}ListNode;
2. Initialize the node (focus, the first node needs to be considered as the head node)
ListNode*ListInit()
{
ListNode*phead=BuyListNode(0);// At this time, phead is the sentinel position and serves as the head node
phead->next=phead;
phead->prev=phead;
return phead;
}
3. Create nodes
ListNode* BuyListNode(LTDataType x)
{
ListNode*node=(ListNode*)malloc(sizeof(ListNode));
node->next=NULL;
node->prev=NULL;
node->data=x;
return node;
}//Dynamic management space
4. Insert data (by inserting data, the head and tail insertion can also be realized, so the head and tail insertion can be realized by multiplexing)
void ListInsert(ListNode*pos,LTDataType x) / / insert data
{
assert(pos);
ListNode*newnode=BuyListNode(x);
ListNode*prev=pos->prev;
prev->next=newnode;
newnode->prev=prev;
newnode->next=pos;
pos->prev=newnode;
}
5. Delete the specified data (similarly, tail deletion and header deletion can also be realized by reuse)
void ListErase(ListNode*pos) / / delete the data at the specified location
{
assert(pos);
ListNode*prev=pos->prev;
ListNode*tail=pos->next;
prev->next=tail;
tail->prev=prev;
free(pos);
}
6. Destroy the linked list
void ListDestory(ListNode* phead)
{
ListNode*cur=phead->next;
while(cur!=phead) / / release the internal node first
{
ListNode*next=cur->next;
free(cur);
cur=next;
}
free(phead); // Release the header node again
}
IV Specific code
1. Header file
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<malloc.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode*prev;
struct ListNode*next;
LTDataType data;
}ListNode;
ListNode* BuyListNode(LTDataType x);
ListNode* ListInit();
void ListPushBack(ListNode* phead,LTDataType x);
void ListPusnFront(ListNode* phead,LTDataType x);
void ListPrint(ListNode*phead);
void ListpopBack(ListNode*phead);//Tail deletion
void ListPopFront(ListNode*phead);//Header deletion
void ListInsert(ListNode*pos,LTDataType x);//insert data
void ListErase(ListNode*pos);
void ListDestory(ListNode* phead);//Destroy
LTDataType ListEmpty(ListNode* phead);//Judge whether it is empty
LTDataType ListFind(ListNode* phead,LTDataType x);
2. Main function module
#include"ListNode.h"
void Test()
{
ListNode*plist=ListInit(0);
ListPushBack(plist,1);
ListPushBack(plist,2);
ListPushBack(plist,3);
ListPushBack(plist,4);
ListPushBack(plist,5);
ListPushBack(plist,6);
ListPusnFront(plist,88);
ListpopBack(plist);
ListPopFront(plist);
ListInsert(plist->next->next,55);
ListErase(plist->next->next);
ListPrint(plist);
LTDataType num=ListFind(plist,3);
if(num==1)
{
printf("eureka\n");
}
else
{
printf("No,\n") ;
}
LTDataType a=ListEmpty(plist);
if(a==0)
{
printf("empty\n");
}
else
{
printf("Non empty\n");
}
//int nums=ListEmpty(plist);
//printf("%d",nums);
}
int main()
{
Test();
return 0;
}
3. Function implementation module
#include"ListNode.h"
ListNode* BuyListNode(LTDataType x)
{
ListNode*node=(ListNode*)malloc(sizeof(ListNode));
node->next=NULL;
node->prev=NULL;
node->data=x;
return node;
}
ListNode*ListInit()
{
ListNode*phead=BuyListNode(0);//At this time, phead is the sentinel position and serves as the head node
phead->next=phead;
phead->prev=phead;
return phead;
}
void ListPushBack(ListNode*phead,LTDataType x)//Tail insertion
{
/*assert(phead);
ListNode*tail=phead->prev;
ListNode*newnode=BuyListNode(x);
tail->next=newnode;
newnode->prev=tail;
newnode->next=phead;
phead->prev=newnode;*/
ListInsert(phead,x);
}
void ListPusnFront(ListNode* phead,LTDataType x)//Head insert
{
/*assert(phead);
ListNode*first=phead->next;
ListNode*newnode=BuyListNode(x);
first->prev=newnode;
newnode->next=first;
phead->next=newnode;
newnode->prev=phead;*/
ListInsert(phead->next,x);
}
void ListPrint(ListNode*phead)
{
ListNode*cur=phead->next;
while(cur!=phead)
{
printf("%d ",cur->data);
cur=cur->next;
}
printf("\n");
}
void ListpopBack(ListNode*phead)//Tail deletion
{
assert(phead);
/*ListNode*tail=phead->prev;
ListNode*tailPrev=tail->prev;
free(tail);
tailPrev->next=phead;
phead->prev=tailPrev;*/
ListErase(phead->prev);
}
void ListPopFront(ListNode*phead)//Header deletion
{
assert(phead);
assert(phead->next!=phead);
/*ListNode*first=phead->next;
ListNode*firstnext=first->next;
free(first);
phead->next=firstnext;
firstnext->prev=phead;*/
ListErase(phead->next);
}
void ListInsert(ListNode*pos,LTDataType x)//insert data
{
assert(pos);
ListNode*newnode=BuyListNode(x);
ListNode*prev=pos->prev;
prev->next=newnode;
newnode->prev=prev;
newnode->next=pos;
pos->prev=newnode;
}
void ListErase(ListNode*pos)//Delete specified location data
{
assert(pos);
ListNode*prev=pos->prev;
ListNode*tail=pos->next;
prev->next=tail;
tail->prev=prev;
free(pos);
}
void ListDestory(ListNode* phead)
{
ListNode*cur=phead->next;
while(cur!=phead)
{
ListNode*next=cur->next;
free(cur);
cur=next;
}
free(phead);
}
LTDataType ListEmpty(ListNode* phead)//Determine whether the linked list is empty
{
if(phead->next==phead)
{
return 0;
}
else
{
return 1;
}
}
LTDataType ListFind(ListNode* phead,LTDataType x)
{
ListNode* cur=phead->next;
while(cur!=phead)
{
if(cur->data==x)
{
return 1;
}
cur=cur->next;
}
return 0;
}