Concept of linked list
Linked list is a non continuous and non sequential storage structure in physical storage structure. The logical order of data elements is realized through the pointer link order in the linked list.
Compared with the sequential list, the linked list lacks the concept of capacity. It needs to open up space to store data in the sequential list, which will lead to a waste of space.
The linked list only needs to open up new nodes when it needs to store new data.
Structure of linked list
- The linked list structure is logically continuous, but it is not necessarily continuous in physical structure.
- The linked list is divided into one-way or two-way linked list, leading or not leading linked list, circular or non circular linked list. There are two common linked lists: headless one-way acyclic linked list and leading two-way acyclic linked list
- Each node has a variable to store the address of the next node, so that the next node can be found through the node
Headless one-way acyclic linked list
structure
For example, in the above figure, each node has two members, one for storing data and the other for storing the address of the next node. The next node can be found through the address.
In reality, nodes are generally applied for on the heap, and the space for multiple applications may or may not be continuous
Implementation of linked list
Define linked list structure
typedef int SLTDataType;//Rename the data type to facilitate subsequent operations that need to change the type
typedef struct SListNode
{
SLTDataType data;//data
struct SListNode* next;//Pointer to the next structure
}SLTNode;//Rename the structure for easy writing
Linked list printing
// Single linked list printing
void SListPrint(SLTNode* phead)
{
//No assertion required
SLTNode* cur = phead;//Create a new pointer operation
while (cur != NULL)
{
//When the next node pointed to by the node is not empty, print the node data
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
Dynamically apply for a new node
// Dynamically apply for a node
SLTNode* BuySLTNode(SLTDataType x)
{
//Use the dynamic memory function malloc to open up a new node space, and pay attention to the consistency of types
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//Judge whether the development is successful
if (newnode == NULL)
{
perror("malloc fail");
return;
}
//Assign data to this node
newnode->data = x;
newnode->next = NULL;
return newnode;
}
Insert data into the chain header
// Header insertion of single linked list
void SListPushFront(SLTNode** phead,SLTDataType x)//The function can change the original address of the node only after the address of the node is passed in
{
//Create a new node to point to the address of the original head node
SLTNode* newnode = BuySLTNode(x);
newnode->next = *phead;
*phead = newnode;
}
Debug the function in the main function to see whether it is successful
SLTNode* Plist = NULL; SListPushFront(&Plist, 1); SListPushFront(&Plist, 2); SListPushFront(&Plist, 3); SListPushFront(&Plist, 4); SListPrint(Plist);
You can see that the program successfully inserted data.
Tail insertion of linked list
There may be two cases of tail insertion. The first case is: when the linked list is an empty linked list, the new node we create can be inserted directly; The second case: it is not an empty linked list. According to the idea, you should first find the end node of the linked list, and then point to the address of the newly created node.
// Single chain tail insertion
void SListPushBack(SLTNode** phead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
//The linked list is empty
if (*phead == NULL)
*phead = newnode;
//Linked list is not empty
else
{
//Tail finding
SLTNode* tail = *phead;
while (tail->next != NULL)
tail = tail->next;
//The end of the original list points to the newly created node
tail->next = newnode;
}
}
Main function test
SListPushBack(&Plist, 5); SListPushBack(&Plist, 6); SListPushBack(&Plist, 7); SListPrint(Plist);
Header deletion of linked list
First, you need to judge whether the linked list is empty. If it is empty, there is no data to delete. Note that the deleted node space needs to be released
Deletion idea: directly change the address of the original head node to the address of the original second node
// Single chain header deletion
void SListPopFront(SLTNode** phead)
{
assert(phead);
//Judge whether *phead is empty
assert(*phead != NULL);
SLTNode* del = *phead;
*phead = (*phead)->next;
//Free up deleted space
free(del);
del = NULL;
}
Main function test
SLTNode* Plist = NULL; SListPushFront(&Plist, 1); SListPushFront(&Plist, 2); SListPushFront(&Plist, 3); SListPushFront(&Plist, 4); SListPrint(Plist); SListPopFront(&Plist); SListPrint(Plist);
Tail deletion of linked list
When the linked list has only one node, you can release the node directly. When the linked list has multiple nodes, we need to find the end of the node. Note that we only need to release the node pointed to by the penultimate node
// Tail deletion of single linked list
void SListPopBack(SLTNode** phead)
{
assert(phead);
//Judge whether it is empty
assert(*phead != NULL);
//If there is only one node
if ((*phead)->next == NULL)
{
free(*phead);
*phead = NULL;
}
//If there are multiple nodes
else
{
//Tail finding
SLTNode* tail = *phead;
while (tail->next->next != NULL)//Judge whether the next node of the node is empty
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
Main function test
SLTNode* Plist = NULL; SListPushFront(&Plist, 1); SListPushFront(&Plist, 2); SListPushFront(&Plist, 3); SListPushFront(&Plist, 4); SListPrint(Plist); SListPopBack(&Plist); SListPrint(Plist);
Search of linked list
There are also two cases for the node of the linked list. The first case is that when the linked list is empty or the target data cannot be found, NULL can be returned; The second case: when the data is found, the address of the node where the data is located is returned
// Single linked list lookup
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
return cur;
//If this node data is not, then find the next node
cur = cur->next;
}
//If it cannot be found or the linked list is empty
return NULL;
}
Main function test
SLTNode* Plist = NULL;
SListPushFront(&Plist, 1);
SListPushFront(&Plist, 2);
SListPushFront(&Plist, 3);
SListPushFront(&Plist, 4);
SListPrint(Plist);
SLTNode* pos = SListFind(Plist, 3);
if (pos)
printf("eureka\n");
Insert data before and after pos position respectively
before
First, be sure to check whether the linked list is empty. If it is empty, you cannot insert it. When the linked list has only one node, it becomes the header insertion written above
//Insert x before pos position
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
assert(phead);
assert(pos);
if (*phead == pos)
//If the linked list has only one node, it is header insertion
SListPushFront(phead,x);
else
{
SLTNode* newnode = BuySLTNode(x);
SLTNode* prev = *phead;
//You need to traverse the linked list to find the previous node of pos
while (prev->next != pos)
{
prev = prev->next;
//If pos is not in the linked list, check whether prev is empty
assert(prev);
}
//The node before the original pos points to the new node
prev->next = newnode;
//The new node points to pos
newnode->next = pos;
}
}
// Single linked list inserts x after pos position
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
//The new node points to the node that pos originally pointed to
newnode->next = pos->next;
//The node pointed to by pos becomes a new node
pos->next = newnode;
}
Main function test
SLTNode* Plist = NULL;
SListPushFront(&Plist, 1);
SListPushFront(&Plist, 2);
SListPushFront(&Plist, 3);
SListPushFront(&Plist, 4);
SListPrint(Plist);
SLTNode* pos = SListFind(Plist, 3);
if (pos != NULL)
{
SListInsert(&Plist, pos, 20);
}
SListPrint(Plist);
You can see that a new data 20 is inserted before the data 3
after
Inserting after pos is very simple. After creating a new node, point to the address that pos originally points to, and point to the address of the new node.
Therefore, it is more recommended to use the insertion method after pos
//Single linked list inserts x after pos position
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
//The new node points to the node that pos originally pointed to
newnode->next = pos->next;
//The node pointed to by pos becomes a new node
pos->next = newnode;
}
Main function test
SLTNode* Plist = NULL;
SListPushFront(&Plist, 1);
SListPushFront(&Plist, 2);
SListPushFront(&Plist, 3);
SListPushFront(&Plist, 4);
SListPrint(Plist);
SLTNode* pos = SListFind(Plist, 3);
if (pos != NULL)
{
SListInsertAfter(pos, 30);
}
You can see that data 30 is inserted after data 3
Value after pos position is deleted in single linked list
The deleted value points directly to the next node of pos, and the original next node of pos can be released
// Value after pos position is deleted in single linked list
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
SLTNode* cur = pos->next->next;
free(pos->next);
pos->next = NULL;
pos->next = cur;
}
Destruction of linked list
Release each node
// Destruction of single linked list
void SListDestory(SLTNode** phead)
{
assert(phead);
SLTNode* cur = *phead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*phead = NULL;
}
summary
The structure of single linked list is not very complex, but there are many details that need to be paid attention to in code implementation. Pay attention to the parameters of the function. If the address of the node is not changed, the function of adding and deleting cannot be realized. Also try to avoid memory leaks and wild pointers.
The above is my personal understanding of the single linked list. If there is any incorrect, please point out 🙌🙌🙌🙌
