Data structure: linear list – one-way linked list (headless)

Table of Contents

What is a one-way linked list

The difference and connection between sequence list and linked list

Sequence table:

Linked list:

Linked list representation (single item) and implementation

1.1 Concept and structure of linked list

1.2 Implementation of singly linked list (headless)

Files used

There will be the following features:

Linked list definition

Create new linked list element

tail plug

Head plug

tail delete

Header deletion

Find – given a pointer to a node

change

Insert before pos position

Delete the value of pos position

Finished product display

SList.h

SList.c

test.c

What is a one-way linked list

A one-way linked list is a common linear data structure that consists of a series of nodes. Each node contains two parts: data and a pointer to the next node. Each node can only access the nodes behind it, but not the previous nodes.

Characteristics of one-way linked list:

  • Each node contains data and a pointer to the next node.
  • The pointer of the last node points to a null value (NULL), indicating the end of the linked list.
  • Nodes can be added or removed dynamically, and the length of the linked list can be expanded or reduced as needed.
  • Nodes can be quickly inserted or deleted based on pointers without moving other nodes.

Singly linked lists have some advantages and disadvantages compared to arrays:

  • Advantages: The time complexity of inserting and deleting elements is O(1), and there is no need to move elements like an array; the length of the linked list can be dynamically adjusted, and there is no fixed size limit.
  • Disadvantages: To access the element at a specific position, you need to traverse it from the beginning, and the time complexity is O(n); compared with the array, using additional pointers to store the information of the next node will take up more memory space.

Due to the characteristics of a one-way linked list, it is often used in scenarios where elements need to be frequently inserted and deleted, or when the size and quantity of data cannot be determined in advance.

The difference and connection between sequence list and linked list

Sequence list:

advantage:
Spatially continuous and supports random access
shortcoming:

  1. The time complexity of insertion and deletion in the middle or front part is O(N)
  2. 2. The cost of capacity expansion is relatively high.

Linked list:

shortcoming:
Stored in units of nodes and does not support random access
advantage:

  1. The time complexity of inserting and deleting at any position is O(1)
  2. There is no capacity increase consumption. Node space is applied for on demand and released directly when no longer needed.

Linked list represents (single item) and realization

1.1 The concept and structure of linked lists

Concept: A linked list is a physical storage structure that is non-continuous and non-sequential. The logical sequence of data elements is through the linked list.
The pointer link order in

1.2 Single linked list (headless) implementation

  1. Headless one-way acyclic linked list: simple structure, generally not used to store data alone. In practice, it is more often used as other data structures.
    Structured substructures, such as hash buckets, graph adjacency lists, etc. In addition, this structure appears a lot in written interviews.
  2. 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
    It is a leading two-way circular linked list. In addition, although this structure is complex, after using the code to implement it, you will find that the structure will bring
    It has many advantages, and the implementation is simpler. We will know it later when we implement the code.

File used

Define three files:

  1. Header file SList.h
  2. Function implementation SList.c
  3. Code test test.c

Will have the following features:

//Print linked list
void SListPrint(SLTNode* phead);

//Create a new linked list element (dynamically apply for a node)
SLTNode* BuySListNode(SLTDataType x);

//Tail insertion
void SListPushBack(SLTNode** pphead, SLTDataType x);

//Head plug
void SListPushFront(SLTNode** pphead, SLTDataType x);

//Delete tail
void SListPopBack(SLTNode** pphead);

//Delete header
void SListPopFront(SLTNode** pphead);

//Search->SListAlter can be modified based on the search
SLTNode* SListFind(SLTNode* phead,SLTDataType x);

//change
void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);

//Insert before pos position
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//Delete the value of pos position
void SListErase(SLTNode** pphead, SLTNode* pos);

Linked list definition

Define the basic structure of a linked list

typedef struct SListNode
{
int data;
struct SListNode* next;
}SLTNode;

Create new linked list element

Create new elements for insertion into the original linked list

SLTNode* BuySListNode(SLTDataType x)
{
//Create space
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
assert(newnode);

newnode->data = x;
newnode->next = NULL;

return newnode;
}

Tail plug

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
//Create space
SLTNode* newnode = BuySListNode(x);

if (*pphead == NULL)
{
//Prevent the node from being empty at the beginning
*pphead = newnode;
}
else
{
//Find the tail node
SLTNode* tail = *pphead;//Find the first element of the linked list
while (tail->next != NULL)
{
//Retrieve unidentified nodes
tail = tail->next;
}
//Insert
tail->next = newnode;
}
}

Head plug

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);

newnode->next = *pphead;
*pphead = newnode;//The address is passed to pphead
//*pphead= & amp;plist
\t
/*
There is no need to check whether the header plug is empty
*/
}

Tail Delete

void SListPopBack(SLTNode** pphead)
{
assert(*pphead);
if ((*pphead)->next==NULL)
{
//1, only one node

free(*pphead);
*pphead = NULL;
}
else
{
//2, there are multiple nodes
\t\t
//Replace the address stored in the previous chain element with NULL to prevent wild pointers
/* Writing method 1 */
SLTNode* tailPrev = NULL;
SLTNode* tail = *pphead;
while (tail->next!=NULL)
{
tailPrev = tail;//tail’s address
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;

/* //Writing method two
* //tail is looking for the penultimate element
while (tail->next->next!=NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
*/
}
}

head delete

void SListPopFront(SLTNode** pphead)
{
//prevent being deleted
assert(*pphead);
\t
//Find the first linked list element
SLTNode* next = (*pphead)->next;//Storage the first element to store the address of the next element
free(*pphead);//Release the first element
*pphead = next;//Change the second element to the first element
}

Find-a pointer to a node

//No need to change the element, so pass the first-level pointer
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data==x)
return cur;
cur = cur->next;
}
//The specified element is not found, returns NULL
return NULL;
}
Change

Modifying elements is based on creation and search.

void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{
printf("Modification successful:\
");
//Find the corresponding element first, then make changes
SLTNode* ret = SListFind(phead, y);
ret->data = x;
}

Insert before pos position

Insert before any position

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);

//Head plug
if (pos == *pphead)
SListPushFront(pphead, x);
else
{
//Insert before any position
SLTNode* prev = *pphead;
while (prev->next!=pos)//Find the position of pos
{
prev = prev->next;//prev stores the address of pos
}
//find location
SLTNode* newnode = BuySListNode(x);//Create a new linked list element and assign a value
prev->next = newnode;//Assign the address of the next element to the previous element
newnode->next = pos;//Storage the address of the next element for the inserted element
}
}

Delete the value of pos position

void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);

if (*pphead == pos)
SListPopFront(pphead);//Delete the header
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)//Find the position of pos
{
prev = prev->next;//prev stores the address of pos
//Move to the previous position of pos, next stores the address of pos
}
//Change the address stored in prev to the address of the element after pos
prev->next = pos->next;
//Release pos
free(pos);
pos = NULL;
}
}

Finished product display

SList.h

#pragma once

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

typedef int SLTDataType;

typedef struct SListNode
{
int data;
struct SListNode* next;
}SLTNode;

//print linked list
void SListPrint(SLTNode*phead);

//Create a new linked list element (dynamically apply for a node)
SLTNode* BuySListNode(SLTDataType x);

//Tail insertion
void SListPushBack(SLTNode** pphead, SLTDataType x);

//Head plug
void SListPushFront(SLTNode** pphead, SLTDataType x);

//Delete tail
void SListPopBack(SLTNode** pphead);

//Delete header
void SListPopFront(SLTNode** pphead);

//Search->SListAlter can be modified based on the search
SLTNode* SListFind(SLTNode* phead,SLTDataType x);

void SListAlter(SLTNode* phead, SLTDataType x,SLTDataType y);

//Insert before pos position
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//Delete the value of pos position
void SListErase(SLTNode** pphead, SLTNode* pos);

SList.c

#include "SList.h"
 
//Print
void SListPrint(SLTNode*phead)
{
SLTNode* cur = phead;
while (cur!=NULL)
{
printf("%d->", cur->data);
cur = cur->next;//Storage the address of the next element
}
printf("NULL\
");
}

//Create new linked list element
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
assert(newnode);

newnode->data = x;
newnode->next = NULL;

return newnode;
}

//Tail insertion
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);

SLTNode* newnode = BuySListNode(x);//data

if (*pphead == NULL)
{
//Prevent the node from being empty at the beginning
*pphead = newnode;
}
else
{
//Find the tail node
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
//Storage new node address
tail = tail->next;
}
tail->next = newnode;
}
}

//Head plug
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);

SLTNode* newnode = BuySListNode(x);

newnode->next = *pphead;
*pphead = newnode;//The address is passed to pphead
//*pphead= & amp;plist
\t
/*
There is no need to check whether the header plug is empty
*/
}

//Delete tail
void SListPopBack(SLTNode** pphead)
{
assert(*pphead);
\t
if ((*pphead)->next==NULL)
{
//1, only one node

free(*pphead);
*pphead = NULL;
}
else
{
//2, there are multiple nodes

//Replace the address stored in the previous chain element with NULL to prevent wild pointers
/* Writing method 1 */
SLTNode* tailPrev = NULL;
SLTNode* tail = *pphead;
while (tail->next!=NULL)
{
tailPrev = tail;//tail’s address
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;

/* //Writing method two
* //tail is looking for the penultimate element
while (tail->next->next!=NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
*/
}
}

//Delete header
void SListPopFront(SLTNode** pphead)
{
//prevent being deleted
assert(*pphead);

SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}

//Find-give a pointer to a node
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data==x)
return cur;
cur = cur->next;
}
return NULL;
}

//change
void SListAlter(SLTNode* phead, SLTDataType x, SLTDataType y)
{
assert(phead);
printf("Modification successful:\
");
SLTNode* ret = SListFind(phead, y);
ret->data = x;
}
//Insert before pos position
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);

//Head plug
if (pos == *pphead)
SListPushFront(pphead, x);
else
{
SLTNode* prev = *pphead;
while (prev->next!=pos)//Find the position of pos
{
prev = prev->next;//prev stores the address of pos
}
//find location
SLTNode* newnode = BuySListNode(x);//Create a new linked list element and assign a value
prev->next = newnode;//Assign the address of the next element to the previous element
newnode->next = pos;//Storage the address of the next element for the inserted element
}
}

//Delete the value of pos position
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);

if (*pphead == pos)
SListPopFront(pphead);//Delete the header
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)//Find the position of pos
{
prev = prev->next;//prev stores the address of pos
//Move to the previous position of pos, next stores the address of pos
}
//Change the address stored in prev to the address of the element after pos
prev->next = pos->next;
//Release pos
free(pos);
pos = NULL;
}
}

test.c

test.c is only used for testing code. This article focuses on understanding one-way linked lists, so menu creation is not performed.
However, the modified test also includes an explanation of some linked list structures and principles. Please read it patiently.

#include "SList.h"
void TestSList1()
{
SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
assert(n1);

SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
assert(n2);

SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
assert(n3);

SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
assert(n4);
\t
n1->data=1;
n2->data=2;
n3->data=3;
n4->data=4;

n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
\t
SListPrint(n1);
}

void TestSList2()
{
SLTNode* plist = NULL;
//The address of the plist pointer is passed
\t
//If plist is passed directly, it will result in SLTNode* phead.
//phead is a temporary copy and does not affect the actual parameters.
SListPushBack( & amp;plist, 1);
SListPushBack( & amp;plist, 2);
SListPushBack( & amp;plist, 3);
SListPushBack( & amp;plist, 4);
\t
SListPrint(plist);//No need to pass a secondary pointer if it does not change

SListPushFront( & amp;plist,0);
SListPrint(plist);

SListPopFront( & amp;plist);
SListPrint(plist);
\t
SListPopBack( & amp;plist);
/*SListPrint(plist);
SListPopBack( & amp;plist);
SListPrint(plist);
SListPopBack( & amp;plist);
SListPrint(plist);
SListPopBack( & amp;plist);
SListPrint(plist);*/
/*SListPopBack( & amp;plist);
SListPrint(plist);*/
}
\t
void TestSList3()
{
SLTNode* plist = NULL;
//The address of the plist pointer is passed

//If plist is passed directly, it will result in SLTNode* phead.
//phead is a temporary copy and does not affect the actual parameters.
SListPushBack( & amp;plist, 1);
SListPushBack( & amp;plist, 2);
SListPushBack( & amp;plist, 3);
SListPushBack( & amp;plist, 4);

SListPrint(plist);//No need to pass a secondary pointer if it does not change


//Find
SLTNode* ret = SListFind(plist, 3);
if (ret)
{
//If the return value is not empty, it is found
printf("Found\
");
}
SListPrint(plist);
\tRevise
//SListAlter(plist, 20, 2);
//SListPrint(plist);

//Insert
SLTNode* pos = SListFind(plist, 3); //Find first and then make changes
if(pos)
{
SListInsert( & amp;plist, pos, 40);
}
SListPrint(plist);

\t//delete
pos = SListFind(plist, 2);//Find first and then delete
if(pos)
{
SListErase( & amp;plist, pos);
}
SListPrint(plist);
}

int main()
{
TestSList3();
\t 
return 0;
}

The explanation of one-way linked list is finished! Creation is not easy, if you like it please leave a like, thank you very much

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 52,105 people are learning the system