# 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 ðŸ™ŒðŸ™ŒðŸ™ŒðŸ™Œ