Data structure is to define a certain structure, such as array structure, linked list structure, tree structure, etc. the implementation of data structure is the implementation function that we actively manage additions, deletions, checks and changes

Concept understanding of linked list

Concept: a linked list is a node by node. You can apply for memory on the heap as needed. You need to apply for one by one. It will be easy to understand the "headless one-way acyclic linked list" first, and then understand other linked list structures. The value of a single linked list is also convenient for us to learn hash buckets

Before programming, we need to know the real stored procedure of the linked list in memory. In essence, it can point to the next node because the previous one has the next address

Next, we still program and implement the dynamic sequence table in the vs environment. Here we write it in files, in the header file slist H, in slist C for specific function definitions, in test C to do specific test implementation

First, let's take a look at the header file seqlist H middle interface

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//Typedef when using typedef to change the type, you can change int to double, char, etc
typedef int SLTDateType;

typedef struct SListNode
{
  SLTDateType data;//Define date to save data
  //One pointer in each data points to the next, otherwise it cannot be found
  struct SListNode* next;
} SListNode;

//The linked list has a pointer to the first node, and the first one is saved until the last pointer points to null 

SListNode* BuyListNode(SListNode* phead);//Add new node function

void SListPrint(SListNode* phead);//Print function, first pass a pointer to the first

void SListPushBack(SListNode** pphead,SLTDateType x);//Tail insertion

void SListPopBack(SListNode** pphead);//Tail deletion

void SListPushFront(SListNode** pphead, SLTDateType x);//Head insertion

void SListPopFront(SListNode** pphead);//Header deletion

void SListDestroy(SListNode** pphead);//Empty function to free up space

SListNode* SListFind(SListNode* phead, SLTDateType x);//Find a node location

void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
//Insert before specifying location

void SListInsertAfter(SListNode* pos, SLTDateType x);//Insert after specifying location

void SListErase(SListNode** pphead, SListNode* pos);//Delete specified location

void SListEraseAfter(SListNode* pos);//Delete the data behind the specified location

We know that the definition method of function is very important and we need to understand it in depth. Let's study it in slist The specific function implementation in C

Add new node function definition

SListNode* BuyListNode(SLTDateType x)//Add new node function
{
  //Consider that when the linked list is empty, so open a new node first
  SListNode* newnode = 
   (SListNode*)malloc(sizeof(SListNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;

  return newnode;//Return to new node
}

Print function definition

Each node will have a next to store the address of the next node

void SListPrint(SListNode* phead)//Print linked list function
{
  SListNode* cur = phead;
   //At this time, cur is equal to the pointer passed to the header node
   //There is a data stored in the address of the first node
  while (cur != NULL)
  {
   printf("%d->", cur->data);//Get header node data using pointer
   cur = cur->next;
  //Each node will have a next to store the address of the next node
  //The next node can be found through the address
  }
  printf("NULL\n");
}

Tail insert function definition

The tail node flag next points to null

void SListPushBack(SListNode** pphead, SLTDateType x)//Tail insert node
{
  assert(pphead);
  //Consider that when the linked list is empty, so open a new node first
  SListNode* newnode = BuyListNode(x);
  //Call the above function to open a new node
  if (*pphead == NULL)//If it is empty, it will not find the tail
  {
    //Let the first pointer point to the new node and save the address of the new node
    *pphead = newnode;
  }
  else// //Not empty go down
  {
    SListNode* tail = *pphead;//Define the tail pointer, point to the head first, and look back from the beginning
    while (tail->next != NULL)//Not empty keep looking
    {
      tail = tail->next;
    }
    //Find the tail here. Next, give the address of the new node to the tail node just now
    tail->next = newnode;//As long as the next of the tail node points to the new node
  }
}

Tail delete function definition

//The tail deletion also needs to pass the secondary pointer, and finally the header pointer needs to be modified
void SListPopBack(SListNode** pphead)//Tail deletion
{
 assert(*pphead != NULL);//Judgment is not empty

 if ((*pphead)->next == NULL)
 {
	free(*pphead);
	*pphead = NULL;
 }
 else
 {
  SListNode* prev = NULL;//Save the tail pointer by defining more than one pointer
  //At this time * pphead first pointer address
  SListNode* tail = *pphead;
  while (tail->next != NULL)//Let's find the tail
  {
 	prev = tail;//Give me a prev before you leave
 	tail = tail->next;
  }

  //Find the tail here
  // Note that before deleting, we need to point the previous one of the tail to null, otherwise it will become a wild pointer
  free(tail);
  tail = NULL;
  prev->next = NULL;
  }
}

Header insert function definition

First define a new node and give the address of the first node to the new node

void SListPushFront(SListNode** pphead, SLTDateType x)
{
 assert(pphead);
 SListNode* newnode = BuyListNode(x);//Call the above function to open a new node
 newnode->next = *pphead;//Give the address of the first node to the new node
 *pphead = newnode;//And then become the new head
}

Header delete function definition

void SListPopFront(SListNode** pphead)//Header deletion
{
 assert(*pphead != NULL);
 SListNode* next = (*pphead)->next;//Take the next one of phead first
 free(*pphead);
 *pphead = next;
}

Null function definition

Empty functions are generally placed at the end of the functions we insert or delete, freeing up the space we apply for on the heap and returning it to the operating system. In addition, they will also check for cross-border problems accordingly

void SListDestroy(SListNode** pphead)//Empty function to free up space
{
  assert(pphead);
  //If the space is discontinuous, it should be released, otherwise the memory leaks
  SListNode* cur = *pphead;//Empty from the beginning
  while (cur)//It's not empty. Keep going
  {
   //First find the next node location and delete it
   SListNode* next = cur->next;
   free(cur);
   cur = next;
  }
  *pphead = NULL;
}

We first use the above interface to implement a test The first test case in C TestSList 1

void TestSList1()
{
//Empty the start list
SListNode* plist = NULL;
SListPushBack(&plist, 1);//Tail insertion 123456
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);
SListPushBack(&plist, 5);
SListPushBack(&plist, 6);
SListPrint(plist);//Print 1->2->3->4->5->6->null
	
SListPopBack(&plist);//Tail deletion twice
SListPopBack(&plist);

SListPrint(plist);//Print 1->2->3->4->null

SListPushFront(&plist, 1);//Head insert data 1234
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPrint(plist);//Print 4->3->2->1->1->2->3->4->null

SListPopFront(&plist);//Delete the header twice
SListPopFront(&plist);

SListPrint(plist);//Print 2->1->1->2->3->4->null

SListDestroy(&plist);//Empty the function and put it at the end to free up space
}
int main()
{
TestSList1();
return 0;
}

Note: here plist (argument) and phead (formal parameter) both point to the address of the first node

Next, we will learn the remaining function interfaces in slist The specific function implementation in C

Find a node location

SListNode* SListFind(SListNode* pphead, SLTDateType x)//Find a node
{
//Traverse the linked list, and find the value of x node
SListNode* cur = pphead;
while (cur)
{
 if (cur->data == x)
 {
 return cur;//Return when you find it
 }
 else 
 {
 cur = cur->next;//I haven't found it. Keep looking
 }
}
 return NULL;//Last not found, return null
}

Here we use find using the pointer of the return node (SListNode* pphead). First, use the above search interface to implement a search in test The second test case in C TestSList 2

void TestSList2()
{
//Empty the start list
SListNode* plist = NULL;
SListPushFront(&plist, 1);//Head insert data 12342
SListPushFront(&plist, 2);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPushFront(&plist, 2);
SListPrint(plist);//Print 2->4->3->2->1->null
	
//When finding multiple data
SListNode* pos = SListFind(plist, 2);
int i = 1;
while (pos)
{
printf("Section%d individual pos node:%p->%d\n",i++,pos,pos->data);
//Print the first pos node: 0000020c088ef120->2
//Print the second pos node: 0000020c088ef580->2
pos = SListFind(pos->next, 2);
//Here, continue to look behind the first 2
}
	 
//be careful:
//Using find that returns the pointer of the node, in addition to finding, you can also modify the pos position data
pos = SListFind(plist, 3);//Revision 3 - >30
if (pos)
{
 pos->data = 30;
}
SListPrint(plist);//Print 2->4->30->2->1->null

SListDestroy(&plist);//Empty the function and put it at the end to free up space
}
int main()
{
 TestSList2();
 return 0;
}

Insert before specifying location

//Insert before specifying location
void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
 assert(pphead);
 assert(pos);
 //pos position alone is not enough
 //We also need to have a previous location of pos, so that the previous location points to the new data node, and the new node location points to pos
  
 //The first step is to prepare a new node
 SListNode* newnode = BuyListNode(x);//Call the above function to open a new node
 if (*pphead == pos)//Judge the condition of head insertion
 {
  newnode->next = *pphead;
  *pphead = newnode;
 }
 else
 {
  //Find the previous position of pos
  SListNode* posprev = *pphead;//Define posorev find from scratch
  while (posprev->next != pos)
  {
  posprev = posprev->next;
  }
  posprev->next = newnode;//Let the previous location point to the new data node
  newnode->next = pos;//The new node location is pointing to pos
 }

}

Insert after specifying location

void SListInsertAfter(SListNode* pos, SLTDateType x)//Insert after specifying location
{
 assert(pos);
 //At this time, note that the newnode must first point to the next pos 
 //Step 1 / / prepare a new node first
 SListNode* newnode = BuyListNode(x);//Call the above function to open a new node
 newnode->next = pos->next;
 pos->next = newnode;
}

Delete specified location

void SListErase(SListNode** pphead, SListNode* pos)//Delete specified location
{
 assert(pphead);
 assert(pos);
 //pos is anywhere
 //Before deleting, let the previous point to the next pos position
 if (pos == *pphead)//Consider deleting headers first
 {
  SListPopFront(pphead);//Call the top header deletion function
 }
 else
 {
  //Find the previous position of pos
  SListNode* posprev = *pphead;//Define posorev find from scratch
  while (posprev->next != pos)
  {
   posprev = posprev->next;
  }
  //
  posprev->next = pos->next;//Let the previous position point to the next position of pos first
  free(pos);//Then delete pos
 }
}

Delete the data behind the specified location

void SListEraseAfter(SListNode* pos)//Delete the data behind the pos at the specified location
{
 //Let pos point to the next position of pos first
 assert(pos->next);
 SListNode* next = pos->next;//Define next as the data to be deleted
 pos->next = next->next;
 //Let the next position of pos point to the next position of data to be deleted (next)
 free(next);//Then delete next
}

At this time, we use the above interface to implement a test The third test case in C TestSList 3

void TestSList3()
{
//Start to empty the linked list
SListNode* plist = NULL;
SListPushBack(&plist, 1);//Tail insertion 1234 
SListPushBack(&plist, 2);
SListPushBack(&plist, 3);
SListPushBack(&plist, 4);

SListNode* pos = SListFind(plist, 4);//Insert before specifying digit 4 position
if (pos)
{
 SListInsert(&plist, pos, 60);//Insert 60 in front of position 4
}
SListPrint(plist);//Print 1->2->3->60->4->null

pos = SListFind(plist, 4);//Insert after specifying the position of number 4
if (pos)
{
 SListInsertAfter(pos, 5);//Insert 5 after position 4
}
SListPrint(plist);//Print 1->2->3->60->4->5->null

pos = SListFind(plist, 4);//Find 4
if (pos)
{
 SListErase(&plist, pos);//Delete current position 4
}
	
SListPrint(plist);//Print 1->2->3->60->5->null

pos = SListFind(plist, 60);//Find 60
if (pos)
{
 SListEraseAfter(pos);//Delete the last one of 60
}
SListPrint(plist);//Print 1->2->3->60->null
	
SListDestroy(&plist);//Empty the function and put it at the end to free up space
}
int main()
{
 TestSList3();
 return 0;
}

In the learning of Java and C++, the sequence table, linked list and binary tree in the early learning data structure are convenient for us to learn better later. We will continue to share the implementation of binary tree and algorithm later

I hope you can gain something from this article. See you next