1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
|
[\<- 05/01](05-01.md)
---
## Link the Node to the List
- Assume we have already created a linked list and allocated memory for the new node
- In order to insert a node, what do you need to know?
- Different Situations:
- Insert in Middle
- know Predecessor
- know Successor
- Insert at End
- know Predecessor
- don't know Successor (NULL)
- Insert into Empty List
- don't know Predecessor (nothing before this)
- don't know Successor
- Insert at Beginning
- don't know Predecessor (nothing before this)
- know Successor
- Be careful about **pointer manipulations**!
## Insert in Middle
- Now we have a list with several nodes, and we want to add a new node in the middle of the list
- Manipulate two pointers:
- `pNew->next` & `pPre->next`
- **Order Matters!**: need to handle `pNew->next` first
```
pNew->next = pPre->next;
pPre->next = pNew;
pList->count++;
```
- Big-O Runtime: O(1)
## Insert at End
- Now we have a list with several nodes, and we want to add a new node at the end of the list
- Manipulate two pointers:
- `pNew->next` & `pPre->next`
```
pNew->next = NULL;
pPre->new = pNew;
pList->count++;
```
## Insert at Beginning
- Now we have a list with one/several node(s), and we want to add a new node at the beginning of the list
- Manipulate two pointers:
- `pNew->next` & `pList->head`
```
pNew->next = pList->head;
pList->head = pNew;
pList->count++;
```
## Insert into Empty List
- An empty list has the list structure only
- Manipulate two pointers:
- `pNew->next` & `pList->head`
```
pNew->next = NULL;
pList->head = pNew;
pList->count++;
```
- Note that the code can in theory be written exactly the same as for the previous case (inserting at beginning)
- Simultaneously, the first two cases can also be combined (inserting in the middle, inserting at the end)
## Insert Items in Linked List
```
void insert(struct list *plist, struct node *pPrev, struct node *pNew){
//pPrev = NULL if inserting as first node
if(pPrev == NULL){ //inserting in beginning
pNew->next = pList->head;
pList->head = pNew;
}
else{ //inserting in middle/end
pNew->next = pPrev->next;
pPrev->next = pNew;
}
pList->count++;
}
```
- What is the big O? O(1) **Only when `pPrev` is given**
- What is missing?
- Possible segmentation fault if `pNew` is NULL -> **missing assertions**
```
void insert(struct list *plist, struct node *pPrev, struct node *pNew){
assert(plist != NULL && pNew != NULL);
//pPrev = NULL if inserting as first node
if(pPrev == NULL){ //inserting in beginning
pNew->next = plist->head;
plist->head = pNew;
}
else{ //inserting in middle/end
pNew->next = pPrev->next;
pPrev->next = pNew;
}
plist->count++;
}
```
## A New Question
- Can we do something even better?
- Yes!
## Dummy Node
- Let's introduce a dummy node at the start of the list. The dummy node (or **sentinet**) does not contain valid data nor count as a node in the list
- We now have predecessors for all insertions!
```
void insert(struct list *plist, struct node *pPrev, struct node *pNew){
assert(plist != NULL && pPrev != NULL && pNew != NULL);
pNew->next = pPrev->next;
pPrev->next = pNew;
pList->count++;
}
```
- Inserting as the first node in the lsit means inserting **after** the dummy node. Also, the list is never truly empty
- So two of our 4 cases don't exist any more
- Results: Less special cases to handle and less core dumps!
## A Linked List without NULL Pointer
- The advantage of a dummy node is that the head pointer is never NULL
- An advantage of a circular list is that no pointer in the nodes are ever NULL
- Combining the two would give you a data structure with no NULL pointers
---
- For example, what does an empty circular doubly-linked list with a dummy node look like?
- Count = 0
- There will be a dummy node with garbage data
- It will have two pointers (next and prev) that both point to itself
---
# Deleting Items
- How many cases for deletion?
- 3 Cases for Deletion
1. delete the **first node**
2. delete the **last node**
3. delete the node **after a given node**
## Deleting the First Node
- What changes?
- `pList->count`
- `head pList->head`
- node to delete is gone (memory needs to be freed)
```
pDel = pList->head;
pList->head = pDel->next;
free(pDel);
pList->count--;
```
## Deleting the Last Node
- What changes?
- `pList->count`
- previous node's next pointer
- node to delete is gone (memory needs to be freed)
```
pDel = pPre->next;
pPre->next = NULL;
free(pDel);
pList->count--;
```
## Deleting a Node after a Given Node
- What changes?
- `pList->count`
- node before node to delete's next pointer
- node to delete is gone (memory needs to be freed)
```
pDel = pPre->next;
pPre->next = pDel->next;
free(pDel);
pList->count--;
```
---
```
void delete(struct node *pList, struct node *pPrev){
//pPrev == NULL if we want to delete the first node
assert(pList != NULL)
struct node *pDel;
if(pPrev == NULL){ //case 1
pDel = pList->head;
pList->head = pDel->next;
}
else{ //case 2 or 3
pDel = pPrev->next;
pPrev->next = pDel->next;
}
pList->count--;
free(pDel);
}
```
- Recall how we combine case 1 & 2 for inserting items
- We can do the same thing here!
- Cases 2 & 3 look similar. They become identical if we replace the NULL in case 2 with `pDel->next`
- We can improve things by including a dummy node (like when inserting)
```
void delete(struct list *pList, struct node *pPrev){
assert(pList != NULL && pPrev != NULL);
pDel = pPrev->next;
pPrev->next = pDel->next;
pList->count--;
free(pDel);
}
```
---
[05/06 ->](05-06.md)
|
