# 1, Basic cognition

## What is a cycle

The last node of the linked list points to the head node, forming a ring. Therefore, any other node can be found from any node in the circular linked list.

## What is a double linked list

Two pointers are stored in the structure of the linked list, one pointing to the predecessor node and the other pointing to the successor node.

## Basic structure

As shown in the figure, data is the stored number, prev and next point to the predecessor node and the successor node respectively.

## 1. Initialization

Initialization is to create a head node and return the head node.
Since it is a double linked list, initialization is to create this head node. Even if there is only one head node, it must abide by the rules and point to itself. Here I spent a picture to make it easy for everyone to understand.

Only one head node
The following is the code directly!

```LTNode* SLTInit()
6	{
7		LTNode* phead= (LTNode*)malloc(sizeof(LTNode));
11	}
12
```

## 2. Head insertion method

First, create a new node to store data. Here, call the "create node" function. I put the "create node" function on the last side. Students who don't know it will go on to look.

Here, insert one end to the front of the list.

```void LTPushFront(LTNode* phead, LTDataType x)
51	{
52		assert(phead != NULL);
53		LTNode* newnode = BuyLTNode(x);
54		LTNode* next = phead->next;
55
56
57
58		phead->next = newnode;
59		newnode->next = next;
60		newnode->prev = phead;
61		next->prev = newnode;
62
63	}
64
```

## 3. Tail insertion method

```void LTPhshBack(LTNode* phead, LTDataType x)
21	{
22		assert(phead != NULL);
24		LTNode* tail = phead->prev;
25
26
27		tail->next = newnode;
28		newnode->prev = tail;
29
30		newnode->next = phead;
31		phead->prev = newnode;
32
33	}
34

```

## 4. Head deletion method

```void LTPopFront(LTNode* phead)
81	{
82		assert(phead != NULL);
83		assert(phead->next != NULL);
84
85		LTNode* next = phead->next;
86		LTNode* nextNext= next->next;
87		phead->next = nextNext;
88		nextNext->prev = phead;
89		free(next);
90		next = NULL;
91
92	}
93
```

## 4. Tail deletion method

```void LTPopBack(LTNode* phead)
66	{
67		assert(phead != NULL);
68		//Cannot delete sentinel position
70		LTNode* tail = phead->prev;
71		LTNode* cur = tail->prev;
72		cur->next = phead;
73		phead->prev = cur;
74
75		tail = NULL;
76		free(tail);
77	}
78
```

## 5. Search function

```LTNode* LTFind(LTNode* phead, LTDataType x)
96	{
97		assert(phead != NULL);
98		LTNode* cur = phead->next;
100		{
101			if (cur->data == x)
102			{
103				return cur;
104			}
105			cur = cur->next;
106		}
107		return NULL;
108	}
109
110
```

## 6. Insert a number in a certain position

This function can be reused for head interpolation and tail interpolation.

```void LTInsert(LTNode* pos, LTDataType x)
113	{
114		assert(pos != NULL);
115		LTNode* newnode = BuyLTNode(x);
116		LTNode* posPrev = pos->prev;
117
118		posPrev->next = newnode;
119		newnode->prev = posPrev;
120
121		newnode->next = pos;
122		pos->prev = newnode;
123
124	}
125
```

## 7. Delete the number in a certain position

This function can be reused to the head deletion method and the tail deletion method.

```void LTErease(LTNode* pos)
127	{
128		assert(pos != NULL);
129		LTNode* posPrev = pos->prev;
130		LTNode* posNext = pos->next;
131
132		posPrev->next = posNext;
133		posNext->prev = posPrev;
134		free(pos);
135		pos = NULL;
136
137
```

## 8. Create node

```LTNode* BuyLTNode(LTDataType x)
13	{
14		LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
15		newnode->data = x;
16	}
17

```

# summary

When inserting or deleting, you must remember to assert, otherwise there may be errors, but you can't find the error.
Double linked list is a storage structure that is updated on the basis of sequential list. Its advantages are that it is efficient to insert at any position, and it can apply for space on demand, without causing space waste.

Posted by kidestranged on Wed, 07 Sep 2022 21:55:27 +0300