The concept and structure of linked lists
A linked list is a non-continuous and non-sequential storage structure in terms of physical storage structure. The logical order of data elements is realized through the pointer link order in the linked list
The sequence table we learned in the previous article is stored continuously
For example:
The sequence list is like a row of seats on a train, it is continuous
The linked list is like the carriages of a train, with something in the middle connecting them to each other.
The basic structure diagram of a linked list is as follows:
There is a pointer pointing to the next node
The concept and structure of linked lists
In practice, the structures of linked lists are very diverse. There are 8 types of linked list structures when combined with the following situations:
Linked lists can be one-way or two-way, cyclic or non-cyclic, leading or not leading. With such a combination, eight types of lists will appear.
The one-way list is as follows:
Two-way list:
Compared with one-way, it is easier to add, delete, check and modify in two-way. It will have a prev node, which can mark the previous node of the current node.
Circular list:
In fact, the circular list means that the last node points to the beginning node.
Taking the lead and not taking the lead:
We can call the head node the sentinel bit, which will not store valid data in the linked list.
In fact, there are only two of the eight types of linked lists that we most commonly use:
Headless one-way acyclic linked list:
Headed two-way loop list:
- Headless one-way acyclic linked list: simple structure, generally not used to store data alone. In practice, it is more of a substructure of other data structures.
- Headed two-way circular linked list: the most complex structure, generally used to store data separately. The linked list data structures used in practice are all headed bidirectional circular linked lists. In addition, although this structure is complex, you will find that it is actually relatively simple in subsequent studies.
Implementation of linked list
The first thing we need to understand is the implementation of a singly linked list:
The header file is as follows:
#include<stdio.h>
#include<assert.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// Dynamically apply for a node
SListNode* BuySListNode(SLTDateType x);
//Singly linked list printing
void SListPrint(SListNode* plist);
//Insert at the end of single linked list
void SListPushBack(SListNode** pplist, SLTDateType x);
// Header of singly linked list
void SListPushFront(SListNode** pplist, SLTDateType x);
//Tail deletion of singly linked list
void SListPopBack(SListNode** pplist);
//Delete single linked list header
void SListPopFront(SListNode** pplist);
//Singly linked list search
SListNode* SListFind(SListNode* plist, SLTDateType x);
//Insert x after pos position in singly linked list
void SListInsertAfter(SListNode* pos, SLTDateType x);
//Singly linked list deletes the value after pos position
void SListEraseAfter(SListNode* pos);
//Destruction of singly linked list
void SListDestroy(SListNode** plist);
Creation of new nodes:
If we want to create a node, the first step is to dynamically open up a space for it.
Then assign the value of this new node newnode to x, and set its next to empty, and then the function returns this node
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
Print of linked list:
When printing a linked list, we can use a symbol -> to replace the space, but the linked list actually does not have this symbol.
We can first define cur and start traversing from the first node of the linked list. When cur is empty, we will not print it, and print the data of cur once. Cur must be equal to the next of cue.
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\
");
}
Tail insertion in singly linked list:
What we need to pay attention to here is to remember to use the secondary pointer, because when the linked list is empty, what we want to change is the address of the node, and if we want to change the address, we must use the address of the address, which is the secondary pointer.
First, we need to insert a node. All we have to do is create a new node, and use a function we defined before directly.
Then we create a tail pointer and let it traverse from the first position of the linked list to the last node. At this time, let the next of tail equal newnode.
void SListPushBack(SListNode** pplist, SLTDateType x)
{
assert(pplist);
/*assert(*pplist);*///You can insert tail when the linked list is empty
SListNode* newnode = BuySListNode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
SListNode* tail = *pplist;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
Head plug of singly linked list:
Header insertion is relatively simple. We directly set the next node of the new node equal to the first node of the linked list, which is *pplist. What we pass in is **pplist, which is the address of the node address, so we need to dereference it once to Address to next of newnode
void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
Tail deletion of singly linked list:
We can divide the cases of tail deletion into two types:
1. When there is only one node:
When there is only one node, we directly free the node. Secondly, in order to prevent wild pointers, we need to make it empty.
2. When there are multiple nodes:
We create a tail and prev, and then use a loop to traverse tail to the last node. When the loop’s termination condition is tail->next is empty, when the condition is met, tail is assigned to prev. When the loop is jumped out, prev is before the last node. For a node, we directly free the tail and leave it empty, so that the tail node is deleted.
void SListPopBack(SListNode** pplist)
{
assert(*pplist);//Cannot delete the linked list when it is empty, violent check
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* prev = NULL;
SListNode* tail = *pplist;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
Delete the head of a singly linked list:
Head deletion is very simple. First define a tail to store the position of the first node, and then move the position of the first node to its next. Remember to free the pointer that temporarily stores the position of the first node. Avoid wild pointer problems
void SListPopFront(SListNode** pplist)
{
assert(*pplist);//Cannot delete the linked list when it is empty, violent check
SListNode* tail = *pplist;
*pplist = (tail)->next;
free(tail);
}
Node search:
It is also easier to find nodes. You can traverse directly with a while loop. If the data of cur is equal to x, cur will be returned. Otherwise, there is no such node and null will be returned.
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
SListNode* cur = plist;
while (cur->next)
{
if (cur->data == x)
{
return cur;
//break;
}
cur = cur->next;
}
return NULL;
}
Insert node after a node:
The first thing you need to do when inserting a node is to create a new node
Then the first thing to do is to connect the next of newnode to the next of the position pos to be inserted.
Then set next of pos to newnode
Note here that the position cannot be reversed, otherwise the next of newnode will not be found.
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
Delete the node after a node:
To delete a node after the node, first there must be a node after this node, so pos->next must be asserted
We store pos->next in next, and then point pos->next directly to next->next, that is, put pos->next=pos->next->next
void SListEraseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
//pos->next = pos->next->next;
SListNode* next = pos->next;
pos->next = next->next;
free(next);
}
Destruction of singly linked list:
Just leave pplist blank.
void SListDestroy(SListNode** pplist)
{
SListNode* node = *pplist;
node = NULL;
free(node);
}
Okay, today’s sharing ends here, thank you all for your support!
The complete code is as follows:
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\
");
}
void SListPushBack(SListNode** pplist, SLTDateType x)
{
assert(pplist);
/*assert(*pplist);*///You can insert tail when the linked list is empty
SListNode* newnode = BuySListNode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
SListNode* tail = *pplist;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
void SListPopBack(SListNode** pplist)
{
assert(*pplist);//Cannot delete the linked list when it is empty, violent check
//SListNode* tail = pplist;
//while (tail->next->next)
//{
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* prev = NULL;
SListNode* tail = *pplist;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
void SListPopFront(SListNode** pplist)
{
assert(*pplist);//Cannot delete the linked list when it is empty, violent check
SListNode* tail = *pplist;
*pplist = (tail)->next;
free(tail);
}
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
SListNode* cur = plist;
while (cur->next)
{
if (cur->data == x)
{
return cur;
//break;
}
cur = cur->next;
}
return NULL;
}
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListEraseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
//pos->next = pos->next->next;
SListNode* next = pos->next;
pos->next = next->next;
free(next);
}
void SListDestroy(SListNode** pplist)
{
SListNode* node = *pplist;
node = NULL;
free(node);
}