# Day2: basic operation of single linked list

cataloguecatalogue

# preface

• In the previous section, we implemented the basic operations of the sequence table. In this section, we will learn about the single linked list (not the leading node), and realize some basic operations and precautions of the single linked list.

# 1. Definition of single linked list

1. Single linked list is the simplest linked list representation in the linked list, also known as linear linked list. The linked list is discontinuous. The relationship between nodes is represented by pointers. A node contains two fields:

Data field: generally represented by data, which stores a data element
Pointer field: store a pointer to the starting storage address of the next node, which plays the role of linking two nodes

2. Structure of single linked list

datan: tail node, no successor, and next points to NULL

Relationship between each node:
The first and second nodes: A2 = A1 - > next;
...
The last node: a (n) = a (n-1) - > next, a (n) - > next = null

# 2. Characteristics of single linked list

1. The length is easy to expand
2. The logical order may not be consistent with the physical order
3. Data can be stored continuously or discontinuously
4. Each node has a pointer field, which consumes a lot of storage space

# 3. Basic operation of single linked list

```#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool. h> / / bool header file
typedef int SLTDataType;//Rename to facilitate changing the data type
typedef struct SListNode
{
SLTDataType data; //Data domain
struct SListNode* next; //Pointer field
}SLTNode;
```

## 2. Initialization

1. Initialization, open up space for the header pointer, and set it to null after successful development.
```void SListInit(SLTNode** phead)
{
{
perror("SListInit");
return;
}
}
```

## 3. Print

1. Traverse according to the structure of the single linked list. Remember not to traverse with the head pointer. Rename the head pointer to p for traversal, which is highly readable
```//ergodic
{
while (p)
{
printf("%d->", p->data);//print data
p = p->next;//Point to the next node and know that the node is NULL
}
printf("NULL\n");
}
```

## 4. Create a new node

1. malloc opens up memory to node. If the development fails, exit. If the development succeeds, set node - > data to x and node - > next to null
```//Create node
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
exit(-1);
}
node->data = x;
node->next = NULL;
return node;
}
```

## 5. Tail insertion

1. When it is an empty table, it is equivalent to inserting a node at the head of the linked list. The pointer needs to be modified: newnode - > next = * pphead* pphead = newnode;
2. In case of non empty table, insert a new node newnode after the next node of current, and the pointer needs to be modified:
newnode->next = tail->next; tail->next = newnode;
3. Here, the BuySListNode function is used to create a new node, so only write current - > next = newnode; Readers can change according to their own implementation methods

```void SListPushBack(SLTNode** pphead, SLTDataType x)
{
{
SLTNode* newnode = BuySListNode(x);//Create a new node
}
else
{
//When a node exists
while (tail->next)//Here, you can judge whether the next node is empty. You cannot judge whether the node is empty. Otherwise, you will directly find the end. If the end is NULL, the insertion will fail
{
tail = tail->next;
}
SLTNode* newnode = BuySListNode(x);//Call the function to create a new node
tail->next = newnode;
}
}
```

## 6. Tail deletion

1. When there is only one node, save the initial node with tail, and modify the pointer: tail = *pphead; free(tail); tail=NULL;
2. When there are multiple nodes, save the precursor node with prev, and tail is the successor node. Traverse the linked list, find the tail node, and modify the pointer: prev = tail; tail = tail->next; free(tail); prev->next = NULL;

```void SListPopBack(SLTNode** pphead)
{
//Violent way
//Gentle way
{
return;
}*/
SLTNode* prev = NULL;
if (tail->next == NULL)
{
free(tail);
tail = NULL;
}
else
{
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
```

1. As the name suggests, the header is inserted before the first node to become the first node. Modify the pointer: newnode - > next = head; head = newnode;

```void SListPushFront(SLTNode** pphead, SLTDataType x)
{
newnode->next = *pphead;//Point to the first node
}
```

1. Header deletion: delete the first node, make the header pointer point to the second node, and modify the pointer: next = head - > next; head = next;

```void SListPopFront(SLTNode** pphead)
{
}
```

## 9. Insert

1. A single linked list is usually inserted into a node after the pos position
3. It is neither the first node nor the last node. Modify the direction: newnode - > next = current - > next; current->next = newnode;
4. The last node is modified to point to: newnode - > next = current - > next; current->next = newnode;

```//Insert after pos position
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
newnode->next = pos->next;
pos->next = newnode;
}
```

## 10. Delete

2. Delete in the middle or tail, and modify to: del = current - > next; current->next = del->next;
```void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* nextnode = pos->next;
pos->next = pos->next->next;
free(nextnode);
nextnode = NULL;
}
```

## 11. Search

1. Find a node with a value equal to x one by one, find and return the node, otherwise return NULL, and modify the pointer: cur = cur - > next;
```SLTNode* SListFind(SLTNode** pphead, SLTDataType x)
{
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
```

## 12. Destroy

1. Release one node by one and modify the pointer: next = cur - > next; free(cur); cur = next;
```void SListDestory(SLTNode** pphead)
{
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
}
```

## 13. Get the number of linked list nodes

1. There is a node, size+1, modify pointer: cur = cur - > next;
```size_t SListSize(SLTNode* phead)
{
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
```

# 4. Precautions for single linked list

matters needing attention:

1. Try not to operate with the head pointer. You can use type renaming to prevent the head pointer from being found and the linked list from being lost. It is very troublesome to not find the head pointer. Each operation involves the head node, such as head plug deletion, traversal, reversing the linked list, etc. the head pointer is required. The purpose of this is to enhance readability
2. When traversing the linked list, check whether the tail of the linked list is empty
3. When inserting and deleting a node, you need to find the node before the insertion point or deletion point
4. When inserting nodes, you need to pay attention to malloc
5. To delete a node, you need to use free to release the opened memory to prevent memory leakage (often forgotten)