[C Language] Data Structure – Headless Single Linked List Example Study

Homepage
?Personal column – data structure learning?
Click to followLearn C language together

Directory

  • Introduction:
  • 1. Single linked list
    • 1.1 What is a singly linked list?
    • 1.2 Advantages and Disadvantages
  • 2. Realize the basic functions of singly linked list
    • 2.1 Define the structure
    • 2.2 Single linked list printing
    • 2.3 Destroy singly linked list
    • 2.4 Dynamically apply for a node
    • 2.5 Single linked list tail insertion
    • 2.6 Deleting the tail of singly linked list
    • 2.7 Single linked list header plug-in
    • 2.8 Deletion of single linked list header
    • 2.9 Single linked list search
    • 2.10 Arbitrary insertion into singly linked list
    • 2.11 Arbitrary deletion of singly linked lists
  • 3. Code organization
    • 3.1 SList.h declares functions
    • 3.2 SList.c defines functions
    • 3.3 study.c call
  • 4. The blogger has something to say

Introduction:

We have already studied the sequence list before. Today we will study the singly linked list of the linked list, which is also a headless singly linked list. This requires a full understanding of the first-level pointers and the second-level pointers.

1. Single linked list

1.1 What is a singly linked list

A singly linked list is a common data structure formed by a series of nodes connected in sequence.
Each node contains two pieces of information: data information and pointer to the next node.
The first node of a singly linked list is called the head node, and the last node has no next node and its pointer points to null.
Similar to a train, the locomotive connects to the next carriage, and the subsequent carriages are connected in turn.

Figure 1.1

1.2 Advantages and Disadvantages

Advantages of singly linked list:

  1. Dynamic: The length of a singly linked list can grow dynamically, and there is no need to specify the length in advance;
  2. High memory utilization: each node in the linked list only needs to store the address of the next node, and does not need to store a fixed-size location like an array, so memory can be used more flexibly;
  3. Convenient insertion and deletion operations: Since only the pointers in the linked list nodes need to be changed, nodes can be easily inserted and deleted in the linked list.

Disadvantages of singly linked list:

  1. Difficulty in random access: Since the entire linked list must be traversed from the head node to access a node at any position, random access is inefficient;
  2. Waste of storage space: Since the pointer to the next node needs to be stored in the linked list node, additional storage space is required;
  3. Reverse traversal is not supported: Since the linked list nodes only store pointers to the next node, the linked list cannot be traversed in reverse.

2. Implement basic functions of singly linked list

We need to create two C files: study.c and SList.c, and a header file: SList.h.
A header file to declare the function, a C file to define the function, and another C file to use the main function main() for testing.

2.1 Define structure

typedef means type definition. typedef struct is for the convenience of using this structure.

If struct SeqList {} defines the structure like this. When applying for SeqList variables, you need to write like this, struct SList n;
If you use typedef, you can write it like this, typedef struct SList{}SL;. When applying for variables, you can write like this, SL n;
The difference lies in whether the struct keyword can be omitted when using it.

SList.h declares functions

//Give the int type an alias - SLNDataType
typedef int SLNDataType;
typedef struct SListNode
{<!-- -->
SLNDataType val;
struct SListNode* next;
}SLNode;

2.2 Single linked list printing

SeqList.h declares functions

//Singly linked list printing
void SLTPrint(SLNode*phead);

SList.c defines functions

//Print structure
void SLTPrint(SLNode*phead)
{<!-- -->
SLNode* cur = phead;//points to the head node
while (cur != NULL)
{<!-- -->
printf("%d-> ", cur->val);
cur = cur->next;
}
printf("NULL\
");
}

2.3 Destroy singly linked list

The dynamically allocated space needs to be released after it is used up to prevent problems later.
SList.h declares functions

//Singly linked list destruction
void SLTDestroy(SLNode** pphead);

SList.c defines functions

//Singly linked list destruction
void SLTDestroy(SLNode** pphead)
{<!-- -->
assert(pphead);
SLNode* cur = *pphead;
SLNode* prev = NULL;
while (cur != NULL)
{<!-- -->
prev = cur->next;
free(cur);
cur = prev;
}
*pphead = NULL;
}

2.4 Dynamically apply for a node

Regardless of inserting a node at the head, tail or any position of the linked list, a node needs to be opened. The function of opening a node must be written in each insertion function, which will be repeated. For convenience, we define a separate function to open a new node. Just call it once.
SList.c defines functions

SLNode* CreateNode(SLNDataType x)
{<!-- -->
//Let the pointer newnode point to the new space opened by malloc
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)//If the development fails, an error message will be returned
{<!-- -->
perror("malloc fail");
exit(-1);
}
//Dereference the structure members and change their values
newnode->val = x;
//Let next point to empty
newnode->next = NULL;
return newnode;
}

2.5 Single linked list tail insertion

Idea:
Create a new node and let the next node of the last node in the linked list point to the new node.

SList.h declares functions

//Single linked list tail insertion
void SLTPushBack(SLNode** pphead, SLNDataType x);

SList.c defines functions
If there are no nodes in this linked list, just let the head pointer plist point directly to newnode.
One thing to note is that plist is a first-level pointer. If we want to change plist, we must use a second-level pointer to receive the address of plist, so that we can change the point of plist.

//Single linked list tail insertion
void SLTPushBack(SLNode** pphead, SLNDataType x)
{<!-- -->
assert(pphead);

SLNode* newnode = CreateNode(x);
//If the beginning is empty, point directly to the space opened by the CreateNode() function to complete the tail insertion
if (*pphead == NULL)
{<!-- -->
*pphead = newnode;
//To change the external structure pointer Node*, use Node**
}
else
{<!-- -->
//Find the tail
SLNode* tail = *pphead;
//If the structure member next points to a non-null pointer
while (tail->next != NULL)
{<!-- -->
//Let tail point to the next node
tail = tail->next;
}
//Let the next of the tail node point to the newly opened space to complete the tail insertion
tail->next = newnode;
}
}

study.c calls

//Test tail insertion and tail deletion
void TestSLT1()
{<!-- -->
SLNode* plist = NULL;
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);

SLTPrint(plist);
SLTDestroy( & amp;plist);
}

int main()
{<!-- -->
TestSLT1();
return 0;
}

2.6 Deleting the tail of a singly linked list

Find the penultimate node, let its next point to NULL, and use free() to release the last node.
If there is only one node, just release the head node directly.

SList.h declares functions

//Delete the end of a singly linked list
void SLTPopBack(SLNode** pphead);

SList.c defines functions

//Delete the end of a singly linked list
void SLTPopBack(SLNode** pphead)
{<!-- -->
assert(pphead);
assert(*pphead);
//When there is only one node
if ((*pphead)->next == NULL)
{<!-- -->
//Release directly
free(*pphead);
*pphead = NULL;
}
//Multiple nodes
else
{<!-- -->
//tail points to the beginning
SLNode* tail = *pphead;
//define another null pointer
SLNode* prev = NULL;
//The next node pointed to by the next member is not empty
while (tail->next != NULL)
{<!-- -->
//Let prev point to the space pointed by tail
prev = tail;
//tail points to the next node
tail = tail->next;
}
//The loop ends, the point pointed by tail is empty, and the space is released
free(tail);
//Let the next member in the structure pointed to by prev point to NULL to complete the tail deletion
prev->next = NULL;
}
}

study.c calls

//Test tail insertion and tail deletion
void TestSLT1()
{<!-- -->
SLNode* plist = NULL;
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPrint(plist);

SLTPopBack( & amp;plist);
SLTPrint(plist);
SLTDestroy( & amp;plist);
SLTPrint(plist);
}
int main()
{<!-- -->
TestSLT1();
return 0;
}

2.7 Single linked list header insertion

Let the head node plist point to the newly opened node, and then let the next of the newly opened node point to the previous first node.

SList.h declares functions

//Single linked list header plug-in
void SLTPushFront(SLNode** pphead, SLNDataType x);

SList.c defines functions

//Single linked list header plug-in
void SLTPushFront(SLNode** pphead, SLNDataType x)
{<!-- -->
assert(pphead);
//Let *newnode point to the new space opened by the CreateNode() function
SLNode* newnode = CreateNode(x);
//Let the next member in the newly opened node point to the node at the beginning of the linked list
newnode->next = *pphead;
//Re-point the previous head node to the newly opened node to complete the head insertion
*pphead = newnode;
}

study.c calls

//Test header insertion and removal
void TestSLT2()
{<!-- -->
SLNode* plist = NULL;
SLTPushFront( & amp;plist, 10);
SLTPushFront( & amp;plist, 20);
SLTPushFront( & amp;plist, 30);
SLTPushFront( & amp;plist, 40);
SLTPrint(plist);

SLTDestroy( & amp;plist);
}
int main()
{<!-- -->
TestSLT2();
return 0;
}

2.8 Single linked list header deletion

Let plist point to the second node and release the first node.

SList.h declares functions

//Delete single linked list header
void SListPopFront(SLNode** pphead);

SList.c defines functions

//Delete single linked list header
void SListPopFront(SLNode** pphead)
{<!-- -->
assert(*pphead);
//tail points to the beginning
SLNode* tail = *pphead;
//Let the head node pointer point to the next node
*pphead = (*pphead)->next;
//Release the space of the first node and complete the header deletion
free(tail);
tail = NULL;
}

study.c calls

//Test header insertion and removal
void TestSLT2()
{<!-- -->
SLNode* plist = NULL;
SLTPushFront( & amp;plist, 10);
SLTPushFront( & amp;plist, 20);
SLTPushFront( & amp;plist, 30);
SLTPushFront( & amp;plist, 40);
SLTPrint(plist);

SLTPopFront( & amp;plist);
SLTPrint(plist);
SLTPopFront( & amp;plist);
SLTPrint(plist);

SLTDestroy( & amp;plist);
}
int main()
{<!-- -->
TestSLT2();
return 0;
}

2.9 Single linked list search

If you want to find out whether there is a value stored in val in the linked list, traverse the linked list and check the val value of each node. If found, the address of the node will be returned. If not found, -1 will be returned. We will apply the specific function later.

SList.h declares functions

//Singly linked list search
SLNode* SListFind(SLNode* pphead, SLNDataType x);

SList.c defines functions

SLNode* SListFind(SLNode* phead, SLNDataType x)
{<!-- -->
SLNode* cur = phead;
while (cur)
{<!-- -->
if (cur->val == x)
{<!-- -->
return cur;
}
else
{<!-- -->
cur = cur->next;
}
}
return NULL;
}

2.10 Arbitrary insertion into singly linked list

Insertion into a singly linked list is not limited to head insertion and tail insertion, but can be done at any position.
For example, if we insert a node before a value in the linked list, we can use singly linked list search to find the number, return the position of its node, and then insert the node at that position.

If the pos position happens to be at the first node, it is the head plug, and you can directly call the previous head plug function.

SList.h declares functions

void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);

SList.c defines functions

void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{<!-- -->
assert(pphead);
assert(pos);
assert(*pphead);
\t
//Single node
if (*pphead == pos)
{<!-- -->
SLTPushFront(pphead, x);
}
//Multiple nodes
else
{<!-- -->
SLNode* tail = *pphead;
while (tail->next != pos)
{<!-- -->
tail = tail->next;
}
SLNode* newnode = CreateNode(x);
tail->next = newnode;
newnode->next = pos;
}
}

study.c calls

void TestSLT3()
{<!-- -->
SLNode* plist = NULL;
SLTPushBack( & amp;plist, 10);
SLTPushBack( & amp;plist, 20);
SLTPushBack( & amp;plist, 30);
SLTPushBack( & amp;plist, 40);
SLTPrint(plist);

SLNode* pos = SListFind(plist, 30);

if (pos != NULL)
{<!-- -->
SLTInsert( & amp;plist, pos, 3);
SLTPrint(plist);
}
SLTDestroy( & amp;plist);
}
int main()
{<!-- -->
TestSLT3();
return 0;
}

2.11 Arbitrary deletion of singly linked lists

It is similar to any insertion. If the pos position is at the head, it means head deletion. Just call it directly.
SList.h declares functions

//Delete anywhere in singly linked list
void SLTErase(SLNode** pphead, SLNode* pos);

SList.c defines functions

//Delete anywhere in singly linked list
void SLTErase(SLNode** pphead, SLNode* pos)
{<!-- -->
assert(pphead);
assert(pos);
assert(*pphead);

SLNode* tail = *pphead;
if (*pphead == pos)
{<!-- -->
SLTPopFront(pphead);
}
else
{<!-- -->
while (tail->next != pos)
{<!-- -->
tail = tail->next;
}
tail->next = pos->next;
free(pos);
pos = NULL;
}
}

study.c calls

//Insert and delete anywhere in a singly linked list
void TestSLT3()
{<!-- -->
SLNode* plist = NULL;
SLTPushBack( & amp;plist, 10);
SLTPushBack( & amp;plist, 20);
SLTPushBack( & amp;plist, 30);
SLTPushBack( & amp;plist, 40);
SLTPrint(plist);

SLNode* pos = SListFind(plist, 30);
if (pos != NULL)
{<!-- -->
SLTErase( & amp;plist, pos);
}
SLTPrint(plist);
SLTDestroy( & amp;plist);
}

int main()
{<!-- -->
TestSLT3();
return 0;
}

3. Code organization

3.1 SList.h declaration function

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

// Dynamically apply for a node
typedef int SLNDataType;
typedef struct SListNode
{<!-- -->
SLNDataType val;
struct SListNode* next;
}SLNode;

//Singly linked list printing
void SLTPrint(SLNode* phead);
//Destroy single linked list
void SLTDestroy(SLNode** pphead);
//Insert at the end of single linked list
void SLTPushBack(SLNode** pphead, SLNDataType x);
//Single linked list header insertion
void SLTPushFront(SLNode** pphead, SLNDataType x);
//Delete the end of the singly linked list
void SLTPopBack(SLNode** pphead);
//Delete single linked list header
void SLTPopFront(SLNode** pphead);
//Singly linked list search
SLNode* SListFind(SLNode* pphead, SLNDataType x);

//Insert anywhere in singly linked list
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
//Delete anywhere in singly linked list
void SLTErase(SLNode** pphead, SLNode* pos);


void SLTInsertAfter(SLNode* pos, SLNDataType x);
void SLTEraseAfter(SLNode* pos);

3.2 SList.c defines functions

#include "SList.h"

//Print structure
void SLTPrint(SLNode*phead)
{<!-- -->
SLNode* cur = phead;//points to the head node
while (cur != NULL)
{<!-- -->
printf("%d-> ", cur->val);
cur = cur->next;
}
printf("NULL\
");
}

//Destroy single linked list
void SLTDestroy(SLNode** pphead)
{
assert(pphead);
SLNode* cur = *pphead;
SLNode* prev = NULL;
while (cur != NULL)
{
prev = cur->next;
free(cur);
cur = prev;
}
*pphead = NULL;
}

SLNode* CreateNode(SLNDataType x)
{<!-- -->
//Let the pointer newnode point to the new space opened by malloc
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)//If the development fails, an error message will be returned
{<!-- -->
perror("malloc fail");
exit(-1);
}
//Dereference the structure members and change their values
newnode->val = x;
//Let next point to empty
newnode->next = NULL;
return newnode;
}
//Insert at the end of single linked list
void SLTPushBack(SLNode** pphead, SLNDataType x)
{
assert(pphead);

SLNode* newnode = CreateNode(x);
//If the beginning is empty, point directly to the space opened by the CreateNode() function to complete the tail insertion
if (*pphead == NULL)
{
*pphead = newnode;
//To change the external structure pointer Node*, use Node**
}
else
{
//Find the tail
SLNode* tail = *pphead;
//If the structure member next points to a non-null pointer
while (tail->next != NULL)
{
//Let tail point to the next node
tail = tail->next;
}
//Let the next of the tail node point to the newly opened space to complete the tail insertion
tail->next = newnode;
}
}

//Delete the end of the singly linked list
void SLTPopBack(SLNode** pphead)
{
assert(pphead);
assert(*pphead);
//When there is only one node
if ((*pphead)->next == NULL)
{
//Release directly
free(*pphead);
*pphead = NULL;
}
//Multiple nodes
else
{
//tail points to the beginning
SLNode* tail = *pphead;
//define another null pointer
SLNode* prev = NULL;
//The next node pointed to by the next member is not empty
while (tail->next != NULL)
{
//Let prev point to the space pointed by tail
prev = tail;
//tail points to the next node
tail = tail->next;
}
//The loop ends, the point pointed by tail is empty, and the space is released
free(tail);
//Let the next member of the structure pointed to by prev point to NULL to complete the tail deletion.
prev->next = NULL;
}

}

//Single linked list header insertion
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
assert(pphead);

//Let *newnode point to the new space opened by the CreateNode() function
SLNode* newnode = CreateNode(x);
//Let the next member in the newly opened node point to the node at the beginning of the linked list
newnode->next = *pphead;
//Re-point the previous head node to the newly opened node to complete the head insertion
*pphead = newnode;
}


//Delete single linked list header
void SLTPopFront(SLNode** pphead)
{
assert(pphead);
assert(*pphead);
//tail points to the beginning
SLNode* tail = *pphead;
//Let the head node pointer point to the next node
*pphead = (*pphead)->next;
//Release the space of the first node and complete the header deletion
free(tail);
tail = NULL;
}

//Singly linked list search
SLNode* SListFind(SLNode* phead, SLNDataType x)
{<!-- -->
SLNode* cur = phead;
while (cur)
{<!-- -->
if (cur->val == x)
{<!-- -->
return cur;
}
else
{<!-- -->
cur = cur->next;
}
}
return NULL;
}

//Insert anywhere in singly linked list
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
assert(pphead);
assert(pos);
assert(*pphead);
//Single node
if (*pphead == pos)
{
SLTPushFront(pphead, x);
}
//Multiple nodes
else
{
SLNode* tail = *pphead;
while (tail->next != pos)
{
tail = tail->next;
}
SLNode* newnode = CreateNode(x);
tail->next = newnode;
newnode->next = pos;
}
}

//Delete anywhere in singly linked list
void SLTErase(SLNode** pphead, SLNode* pos)
{<!-- -->
assert(pphead);
assert(pos);
assert(*pphead);

SLNode* tail = *pphead;
if (*pphead == pos)
{<!-- -->
SLTPopFront(pphead);
}
else
{<!-- -->
while (tail->next != pos)
{<!-- -->
tail = tail->next;
}
tail->next = pos->next;
free(pos);
pos = NULL;
}
}


void SLTInsertAfter(SLNode* pos, SLNDataType x)
{
assert(pos);
SLNode* newnode = CreateNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SLTEraseAfter(SLNode* pos)
{
assert(pos);
assert(pos->next);

SLNode* tmp = pos->next;
pos->next = pos->next->next;
free(tmp);
tmp = NULL;
}

3.3 study.c call

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
//The address of each node is not related and is random, one in the east and one in the west

//If you want to change int*, you must pass int**

//Test tail insertion and tail deletion
void TestSLT1()
{<!-- -->
SLNode* plist = NULL;
SLTPushBack( & amp;plist, 1);
SLTPushBack( & amp;plist, 2);
SLTPushBack( & amp;plist, 3);
SLTPushBack( & amp;plist, 4);
SLTPrint(plist);

SLTPopBack( & amp;plist);
SLTPrint(plist);
SLTDestroy( & amp;plist);
SLTPrint(plist);

}
//Test header insertion and deletion
void TestSLT2()
{<!-- -->
SLNode* plist = NULL;
SLTPushFront( & amp;plist, 10);
SLTPushFront( & amp;plist, 20);
SLTPushFront( & amp;plist, 30);
SLTPushFront( & amp;plist, 40);
SLTPrint(plist);

SLTPopFront( & amp;plist);
SLTPrint(plist);
SLTPopFront( & amp;plist);
SLTPrint(plist);

SLTDestroy( & amp;plist);
\t
}

//Insert and delete anywhere in the singly linked list
void TestSLT3()
{<!-- -->
SLNode* plist = NULL;
SLTPushBack( & amp;plist, 10);
SLTPushBack( & amp;plist, 20);
SLTPushBack( & amp;plist, 30);
SLTPushBack( & amp;plist, 40);
SLTPrint(plist);

SLNode* pos = SListFind(plist, 30);

/*if (pos != NULL)
{
SLTInsert( & amp;plist, pos, 3);
SLTPrint(plist);
}
SLTDestroy( & amp;plist);*/


if (pos != NULL)
{<!-- -->
SLTErase( & amp;plist, pos);
}
SLTPrint(plist);
SLTDestroy( & amp;plist);
}
int main()
{<!-- -->
//TestSLT1();
//TestSLT2();
TestSLT3();
return 0;
}

4. The blogger has something to say

The content about headless singly linked lists is shared here. For more relevant content, follow the blogger. If you have any questions, you can leave a message and discuss with the blogger.