[Data structure] Simple implementation of singly linked list

Tip: After the article is written, the table of contents can be automatically generated. For how to generate it, please refer to the help document on the right.

Article directory

• Preface
• 1. Definition of singly linked list
• 2. The composition of data elements in the linked list
• 3. Basic operations of linked lists
• 4. Functional realization of singly linked list
• • 4.1 Print singly linked list
  • 4.2. Destroy the linked list
  • 4.3. Create new nodes
  • 4.4. Single linked list tail insertion
  • 4.5. Single linked list header plug-in
  • 4.6. Deleting the tail of singly linked list
  • 4.7. Deleting the head of a singly linked list
  • 4.8. Single linked list data search
  • 4.9. Insert in front of pos
  • 4.10. Delete the pos position of the linked list
  • 4.11. Insert after pos in the linked list
  • 4.12. Delete after pos in the linked list
• Summarize

Foreword

1. Definition of singly linked list

A singly linked list is a chained access data structure that uses a set of storage units with arbitrary addresses to store data elements in a linear list. The data in the linked list is represented by nodes. Each node is composed of: element (image of data element) + pointer (indicating the storage location of subsequent elements). The element is the storage unit that stores the data, and the pointer is to connect each The address data of the node.

2. The composition of data elements in the linked list

Each element itself consists of two parts:
1. The information itself is called “Data field“
2. The pointer pointing to the immediate successor is called “Pointer field“

3. Basic operations of linked lists

The SeqList.h header file code is as follows

typedef int SLDatetype;
typedef struct SListNode
{<!-- -->
    SLDatetype val;//data field
    struct SListNode* next; //Pointer field
}SListNode;

//print linked list
void SLTPrint(SListNode*phead);
//Destroy the linked list
void SLTDestroy(SLNode** pphead);
//Tail insertion
void SLTPushBack(SListNode** pphead,SLDatetype x);

//Head plug
void SLTPushFront(SListNode** pphead,SLDatetype x);

//Delete tail
void SLTPopBack(SListNode** pphead);

//Delete header
void SLTPopFront(SListNode** pphead);

//Find
SListNode*SLTFind(SListNode* plist,SLDatetype x);

//Insert in front of pos
void SLTInsert(SListNode** pphead, SListNode* pos, SLDatetype x);
//Delete in front of pos
void SLTErase(SListNode** pphead,SListNode* pos);

//Insert after pos
void* SLTInsertAfter(SListNode* pos,SLDatetype x);
//Delete after pos
void* SLTEraseAfter(,SListNode* pos)

4. Functional implementation of singly linked list

4.1 Print singly linked list

There is no need for assertions when printing linked lists. Linked lists are different from sequential lists. When there are no elements in the linked list, the linked list is an empty linked list, and the head pointer points to NULL, so there will be problems with assertions.

void SLTPrint(SListNode*phead)
{<!-- -->
SListNode* tail=phead;
//Traverse the linked list
while(tail->next!=NULL)
{<!-- -->
printf("%d->",tail->val);
//Update tail at the same time
tail=tail->next;
}
printf("NULL");
}

4.2. Destroy linked list

Note: The destruction operation does not allow direct free (phead), because the linked list is not stored continuously in the physical structure, and it must be released one node at a time.

void SLTDestroy(SLNode** pphead)
{<!-- -->
//Assert to prevent passing null pointer
assert(pphead);
SLNode* cur = *pphead;
//Empty linked list does not enter the loop
while (cur)
{<!-- -->
SLNode* next = cur->next;
//Release each node
free(cur);
cur = next;
}
//Remember to leave it blank at the end
*pphead = NULL;
}

4.3. Create new nodes

Because we need to create nodes later in the insertion part, we specially designed a function to create nodes, which is convenient and reduces repeated code.

SListNode* CreaetNode(SLDatetype x)
{<!-- -->
SListNode* newnode=(SListNode*)malloc(sizeof(SListNode));
//Determine whether malloc successfully opened the node
if(newnode==NULL)
{<!-- -->
//Exit the program directly if development fails
printf("malloc fail");
exit(-1);
}
newnode->val=x;
newnode->next=NULL;
return newnode;
}

4.4, Single linked list tail insertion

Ideas

void SLTPushBack(SListNode**pphead,SLDatetype x)
{<!-- -->
//Assert to prevent passing null pointer
assert(pphead);
//Create node
SListNode*newnode=CreatNode(x);
if(*pphead==NULL)
{<!-- -->
*pphead=newnode;
}
else
{<!-- -->
SListNode*tail=*pphead;
//Find the tail, if the pointer is empty, do not enter the loop
while(tail->next!=NULL)
{<!-- -->
//update tail
tail=tail->next;
}
//Point to new node
tail->next=newnode;
}
}

Tests and test results
Tail plug

void Test1()
{<!-- -->
SListNode*plist=NULL;
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPrint(plist);
}

4.5, Single-linked table header insertion

Ideas

void SLTPushFront(SListNode** pphead, SLDatetype x)
{<!-- -->
//Assert to prevent a null pointer from being passed in
assert(pphead);
SListNode*newnode=CreatNode(x);
newnode->next=*pphead;
*pphead=newnode;
}

Tests and test results
Head plug

void Test2()
{<!-- -->
SListNode* plist = NULL;
SLTPushFront( & amp;plist, 1);
SLTPushFront( & amp;plist, 2);
SLTPushFront( & amp;plist, 3);
SLTPushFront( & amp;plist, 4);
SLTPrint(plist);
}

4.6. Deleting the tail of a singly linked list

Ideas

void SLTPopBack(SListNode** pphead)
{<!-- -->
//Assert to prevent null pointer from being passed in
assert(pphead);
//Violent inspection method
assert(*pphead);
//a node
if((*pphead)->==NULL)
{<!-- -->
free(*pphead);
*pphead=NULL;
}
//Multiple nodes
else
{<!-- -->
//Double pointer, find tail
SListNode*prve=NULL;
SListNode*tail=*pphead;
while(tail->next==NULL)
{<!-- -->
//tail is always in front of prev
prev=tail;
//update tail
tail=tail->next;
}
//Release space
free(tail);
\t\t//Blanking
prve->next=NULL;
}
}

Tests and test results
We directly test tail deletion based on Test1

void Test1()
{<!-- -->
SListNode* plist = NULL;
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPrint(plist);//Print 1, 2, 3, 4
\t
SLTPopBack( & amp;plist);//Delete one at the end
SLTPrint(plist);//Print 1, 2, 3

SLTPopBack( & amp;plist);//Delete one at the end
SLTPrint(plist);//1, 2

SLTPopBack( & amp;plist);//Delete the next one
SLTPrint(plist);//1

SLTPopBack( & amp;plist);//Deleted
SLTPrint(plist);//Print NULL
}

4.7, Head deletion of singly linked list

Ideas

void SLTPopFront(SListNode** pphead)
{<!-- -->
assert(pphead);
//Multiple nodes
SListNode*tmp=*pphead;
*pphead=(*pphead)->next;
//Release the space pointed to
free(tmp);
}

test

void TestSLT2()
{<!-- -->
SListNode* plist = NULL;
SLTPushFront( & amp;plist, 1);
SLTPushFront( & amp;plist, 2);
SLTPushFront( & amp;plist, 3);
SLTPushFront( & amp;plist, 4);
SLTPrint(plist);//The header prints 4->3->2->1->NULL

SLTPopFront( & amp;plist);//Delete one header
SLTPrint(plist);//3->2->1->NULL
}

4.8, Single linked list data search

Start traversing from the head node of the linked list, and compare the value of the data field in the linked list in turn to see if it is equal to x, which is equivalent to returning the node pointer. If it cannot be found or does not exist in the linked list, it will return empty and exit the program.

SListNode* SLTFind(SListNode* phead, SLDateType x)
{<!-- -->
//Assert to prevent passing null pointer
assert(phead);
SListNode* cur=phead;
//Traverse
while (cur)
{<!-- -->
if (cur->val == x)
{<!-- -->
return cur;
}
else
{<!-- -->
cur=cur->next;
}
}
return NULL;
}

4.9. Insert before pos

Ideas

void SLTInsert(SListNode**pphead,SListNode*pos,SLDatetype x)
{<!-- -->
assert(pphead);
assert(*pphead);
assert(pos);
if(*pphead==pos)
{<!-- -->
//Head plug
SLTPushFront(pphead,x);
}
else
{<!-- -->
SListNode*prev=*pphead;
while(prev->next!=pos)
{<!-- -->
prev=prev->next;
}
SListNode*newnode=CreatNode(x);
prve->next=newnode;
newnode->next=pos;
}
}

Tests and test results

void TestSLT3()
{<!-- -->
SListNode* plist = NULL;
SLTPushFront( & amp;plist, 1);
SLTPushFront( & amp;plist, 2);
SLTPushFront( & amp;plist, 3);
SLTPushFront( & amp;plist, 4);
SLTPrint(plist);

SListNode* pos = SLTFind(plist, 4);
SLTInsert( & amp;plist, pos, 40);
SLTPrint(plist);
\t
pos = SLTFind(plist, 2);
SLTInsert( & amp;plist, pos, 20);
}

4.10. Delete the pos position of the linked list

Ideas

void SLTErase(SListNode** pphead, SListNode* pos)
{<!-- -->
assert(pphead);
assert(*pphead);
assert(pos);
if(*pphead==pos)
{<!-- -->
//Delete header
SLTPopFront(pphead);
}
else
{<!-- -->
SListNode*prve=*pphead;
while(prev->next=pos)
{<!-- -->
prev=prev->next;
}
prev->next=pos->next;
free(pos);
pos=NULL;
}
}

Tests and test results

void TestSLT4()
{<!-- -->
SLNode* plist = NULL;
//Insert data
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPrint(plist);

SLNode* pos = SLTFind(plist, 1);
SLTErase( & amp;plist, pos);
SLTPrint(plist);
\t
pos = SLTFind(plist, 3);
SLTErase( & amp;plist, pos);
SLTPrint(plist);
}

4.11. Insert after pos in the linked list

void SLTInsertAfter(SListNode* pos, SLDateytype x)
{<!-- -->
//Assert that the null pointer NULL cannot point to the next node
assert(pos);
SListNode* newnode = CreatNode(x);
newnode->next = pos->next;
pos->next = newnode;
}

4.12. Delete after pos in the linked list

void SLTEraseAfter(SListNode* pos)
{<!-- -->
assert(pos);
//Assert, if pos is the last node, there is no need to delete it.
assert(pos->next);

SListNode* tmp = pos->next;
pos->next = pos->next->next;

free(tmp);
tmp = NULL;
}

Summary

//Print
void SLTPrint(SListNode*phead)
{<!-- -->
SListNode* tail=phead;
//Traverse the linked list
while(tail->next!=NULL)
{<!-- -->
printf("%d->",tail->val);
//Update tail at the same time
tail=tail->next;
}
printf("NULL");
}
//destroy
void SLTDestroy(SLNode** pphead)
{<!-- -->
//Assert to prevent passing null pointer
assert(pphead);
SLNode* cur = *pphead;
//Empty linked list does not enter the loop
while (cur)
{<!-- -->
SLNode* next = cur->next;
//Release each node
free(cur);
cur = next;
}
//Remember to leave it blank at the end
*pphead = NULL;
}
//Create node
SListNode* CreaetNode(SLDatetype x)
{<!-- -->
SListNode* newnode=(SListNode*)malloc(sizeof(SListNode));
//Determine whether malloc successfully opened the node
if(newnode==NULL)
{<!-- -->
//Exit the program directly if development fails
printf("malloc fail");
exit(-1);
}
newnode->val=x;
newnode->next=NULL;
return newnode;
}
//Tail insertion
void SLTPushBack(SListNode**pphead,SLDatetype x)
{<!-- -->
//Assert to prevent passing null pointer
assert(pphead);
//Create node
SListNode*newnode=CreatNode(x);
if(*pphead==NULL)
{<!-- -->
*pphead=newnode;
}
else
{<!-- -->
SListNode*tail=*pphead;
//Find the tail, if the pointer is empty, do not enter the loop
while(tail->next!=NULL)
{<!-- -->
//update tail
tail=tail->next;
}
//Point to new node
tail->next=newnode;
}
}
//Head plug
void SLTPushFront(SListNode** pphead, SLDatetype x)
{<!-- -->
//Assert to prevent a null pointer from being passed in
assert(pphead);
SListNode*newnode=CreatNode(x);
newnode->next=*pphead;
*pphead=newnode;
}
//Delete tail
void SLTPopBack(SListNode** pphead)
{<!-- -->
//Assert to prevent null pointer from being passed in
assert(pphead);
//Violent inspection method
assert(*pphead);
//a node
if((*pphead)->==NULL)
{<!-- -->
free(*pphead);
*pphead=NULL;
}
//Multiple nodes
else
{<!-- -->
//Double pointer, find tail
SListNode*prve=NULL;
SListNode*tail=*pphead;
while(tail->next==NULL)
{<!-- -->
//tail is always in front of prev
prev=tail;
//update tail
tail=tail->next;
}
//Release space
free(tail);
\t\t//Blanking
prve->next=NULL;
}
}
//Delete header
void SLTPopFront(SListNode** pphead)
{<!-- -->
assert(pphead);
//Multiple nodes
SListNode*tmp=*pphead;
*pphead=(*pphead)->next;
//Release the space pointed to
free(tmp);
}
//Find
SListNode* SLTFind(SListNode* phead, SLDateType x)
{<!-- -->
//Assert to prevent passing null pointer
assert(phead);
SListNode* cur=phead;
//Traverse
while (cur)
{<!-- -->
if (cur->val == x)
{<!-- -->
return cur;
}
else
{<!-- -->
cur=cur->next;
}
}
return NULL;
}
//Insert in front of pos
void SLTInsert(SListNode**pphead,SListNode*pos,SLDatetype x)
{<!-- -->
assert(pphead);
assert(*pphead);
assert(pos);
if(*pphead==pos)
{<!-- -->
//Head plug
SLTPushFront(pphead,x);
}
else
{<!-- -->
SListNode*prev=*pphead;
while(prev->next!=pos)
{<!-- -->
prev=prev->next;
}
SListNode*newnode=CreatNode(x);
prve->next=newnode;
newnode->next=pos;
}
}
//Delete pos position
void SLTErase(SListNode** pphead, SListNode* pos)
{<!-- -->
assert(pphead);
assert(*pphead);
assert(pos);
if(*pphead==pos)
{<!-- -->
//Delete header
SLTPopFront(pphead);
}
else
{<!-- -->
SListNode*prve=*pphead;
while(prev->next=pos)
{<!-- -->
prev=prev->next;
}
prev->next=pos->next;
free(pos);
pos=NULL;
}
}
//Insert after pos in the linked list
void SLTInsertAfter(SListNode* pos, SLDateytype x)
{<!-- -->
//Assert that the null pointer NULL cannot point to the next node
assert(pos);
SListNode* newnode = CreatNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//Delete after pos in the linked list
void SLTEraseAfter(SListNode* pos)
{<!-- -->
assert(pos);
//Assert, if pos is the last node, there is no need to delete it.
assert(pos->next);

SListNode* tmp = pos->next;
pos->next = pos->next->next;

free(tmp);
tmp = NULL;
}