Data Structures
List Remove
Removing a linked node changes the previous node to skip over it.
previous pointer
The previous node is needed so its link can bypass the removed node.
removed flag
A flag records whether the target value was found.
List Remove
list_remove.c
Replay: real traced execution (multi-file project)
#include <stdio.h>
struct Node {
int value;
struct Node *next;
};
int main(void) {
int removeValue = 20;
struct Node third = {30, 0};
struct Node second = {20, &third};
struct Node first = {10, &second};
struct Node *head = &first;
struct Node *previous = 0;
struct Node *current = head;
int removed = 0;
while (current != 0 && removed == 0) {
if (current->value == removeValue) {
if (previous == 0) {
head = current->next;
} else {
previous->next = current->next;
}
removed = 1;
} else {
previous = current;
current = current->next;
}
}
printf("removed=%d head=%d\n", removed, head->value);
return 0;
}
#include <stdio.h>
struct Node {
int value;
struct Node *next;
};
int main(void) {
int removeValue = 10;
struct Node third = {30, 0};
struct Node second = {20, &third};
struct Node first = {10, &second};
struct Node *head = &first;
struct Node *previous = 0;
struct Node *current = head;
int removed = 0;
while (current != 0 && removed == 0) {
if (current->value == removeValue) {
if (previous == 0) {
head = current->next;
} else {
previous->next = current->next;
}
removed = 1;
} else {
previous = current;
current = current->next;
}
}
printf("removed=%d head=%d\n", removed, head->value);
return 0;
}
#include <stdio.h>
struct Node {
int value;
struct Node *next;
};
int main(void) {
int removeValue = 30;
struct Node third = {30, 0};
struct Node second = {20, &third};
struct Node first = {10, &second};
struct Node *head = &first;
struct Node *previous = 0;
struct Node *current = head;
int removed = 0;
while (current != 0 && removed == 0) {
if (current->value == removeValue) {
if (previous == 0) {
head = current->next;
} else {
previous->next = current->next;
}
removed = 1;
} else {
previous = current;
current = current->next;
}
}
printf("removed=%d head=%d\n", removed, head->value);
return 0;
}
removeValue ← 20, third ← (empty), second ← (empty), first ← (empty)
8int main(void) {9 int removeValue→ 20 = 20; //@removeValue=10, 3010 struct Node third→ (empty) = {30, 0};11 struct Node second→ (empty) = {20, &third(empty)};12 struct Node first→ (empty) = {10, &second(empty)};13 struct Node *head→ ⟨addr A⟩ = &first(empty);14 struct Node *previous→ 0 = 0;15 struct Node *current→ ⟨addr A⟩ = head⟨addr A⟩;16 int removed→ 0 = 0;while (current != 0 && removed == 0)
pass 1 of 218while (current⟨addr A⟩ != 0 && removed0 == 0) {19 if (current->value == removeValue) {previous ← ⟨addr A⟩, current ← ⟨addr B⟩, current->next ← ⟨addr C⟩
25 removed = 1;26} else {27 previous→ ⟨addr A⟩ = current⟨addr A⟩;28 current→ ⟨addr B⟩ = current->next→ ⟨addr C⟩;29}while (current != 0 && removed == 0)
pass 2 of 218while (current⟨addr B⟩ != 0 && removed0 == 0) {19 if (current->value == removeValue) {if (current->value == removeValue)
18while (current != 0 && removed == 0) {19 if (current->value20 == removeValue20) {20 if (previous == 0) {previous->next ← ⟨addr C⟩
21 head = current->next;22} else {23 previous->next→ ⟨addr C⟩ = current->next⟨addr C⟩;24}removed ← 1
24 }25 removed→ 1 = 1;26} else {printf("removed=%d head=%d ", removed, head->value);
32 printf("removed=%d head=%d\n", removed1, head⟨addr A⟩->value);33 return 0;34}outputremoved=1 head=10
removeValue ← 10, third ← (empty), second ← (empty), first ← (empty)
8int main(void) {9 int removeValue→ 10 = 10;10 struct Node third→ (empty) = {30, 0};11 struct Node second→ (empty) = {20, &third(empty)};12 struct Node first→ (empty) = {10, &second(empty)};13 struct Node *head→ ⟨addr A⟩ = &first(empty);14 struct Node *previous→ 0 = 0;15 struct Node *current→ ⟨addr A⟩ = head⟨addr A⟩;16 int removed→ 0 = 0;while (current != 0 && removed == 0)
18while (current⟨addr A⟩ != 0 && removed0 == 0) {19 if (current->value == removeValue) {if (current->value == removeValue)
18while (current != 0 && removed == 0) {19 if (current->value10 == removeValue10) {20 if (previous == 0) {head ← ⟨addr B⟩
19if (current->value == removeValue) {20 if (previous0 == 0) {21 head→ ⟨addr B⟩ = current->next⟨addr B⟩;22 } else {removed ← 1
24 }25 removed→ 1 = 1;26} else {printf("removed=%d head=%d ", removed, head->value);
32 printf("removed=%d head=%d\n", removed1, head⟨addr B⟩->value);33 return 0;34}outputremoved=1 head=20
removeValue ← 30, third ← (empty), second ← (empty), first ← (empty)
8int main(void) {9 int removeValue→ 30 = 30;10 struct Node third→ (empty) = {30, 0};11 struct Node second→ (empty) = {20, &third(empty)};12 struct Node first→ (empty) = {10, &second(empty)};13 struct Node *head→ ⟨addr A⟩ = &first(empty);14 struct Node *previous→ 0 = 0;15 struct Node *current→ ⟨addr A⟩ = head⟨addr A⟩;16 int removed→ 0 = 0;while (current != 0 && removed == 0)
pass 1 of 318while (current⟨addr A⟩ != 0 && removed0 == 0) {19 if (current->value == removeValue) {All 3 passes — pass 1 is the card above pass current->valueremoveValuepreviouscurrentcurrent->nextprevious->next1 — — 0 → ⟨addr A⟩ ⟨addr A⟩ → ⟨addr B⟩ ⟨addr B⟩ → ⟨addr C⟩ — 2 — — ⟨addr A⟩ → ⟨addr B⟩ ⟨addr B⟩ → ⟨addr C⟩ ⟨addr C⟩ → 0 — 3 30 30 — ⟨addr C⟩ 0 ⟨addr C⟩ → 0 previous ← ⟨addr A⟩, current ← ⟨addr B⟩, current->next ← ⟨addr C⟩
pass 1 of 225 removed = 1;26} else {27 previous→ ⟨addr A⟩ = current⟨addr A⟩;28 current→ ⟨addr B⟩ = current->next→ ⟨addr C⟩;29}previous ← ⟨addr B⟩, current ← ⟨addr C⟩, current->next ← 0
pass 2 of 225 removed = 1;26} else {27 previous→ ⟨addr B⟩ = current⟨addr B⟩;28 current→ ⟨addr C⟩ = current->next→ 0;29}if (current->value == removeValue)
18while (current != 0 && removed == 0) {19 if (current->value30 == removeValue30) {20 if (previous == 0) {previous->next ← 0
21 head = current->next;22} else {23 previous->next→ 0 = current->next0;24}removed ← 1
24 }25 removed→ 1 = 1;26} else {printf("removed=%d head=%d ", removed, head->value);
32 printf("removed=%d head=%d\n", removed1, head⟨addr A⟩->value);33 return 0;34}outputremoved=1 head=10