summaryrefslogtreecommitdiff
path: root/01-31.md
blob: cdf6bc3ea7ffa0de54ea318c75b73554e3593c2c (plain)
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
[\<- Notes 01/29](01-29.md)

---

# Linked Lists Continued

Recall: Linked List Declaration:

```
#define NODE struct node

struct node{
	char name[20];
	int number;
	NODE *next;
};

NODE *head = NULL;
```

## Deleting a Node

- if the Linked List only has one Node:

```
head->next = NULL;
free(p); //where p is a pointer to the deleted node
```

- if the Linked List has more than one Node and you want to delete the first Node:

| Visual Representation | | | | | | | | | |
|   -         |  -   | -  | -  | -  |   -    |  - | -  | - | - |
| **Before:** | head | -> | n1 | -> | n2 | -> | n3 |   |   |
| **After:**  | head | -> | n2 | -> | n3 |    |    |   |   | 

```
head = head->next;
free(p); //where p is a pointer to the deleted node
```

the order of steps is important (freeing memory should always be the last step)

- Find nodes with matching numbers 'n' (p and q are pointers pointing to the nodes they are in):

| Visual Representation | | | | | | | | | |
|   -         |  -   | -  | -  | -  |   -    |  - | -  | - | - |
| **Before:** | head | -> | n1 (p) (q)| -> | n2 | -> | n3 |   |   |

```
NODE *p, *q;
p = q = head;

while(p->number != n && p != NULL){
	q = p;
	p = p->next; //traverse in n1 until it finds 'n' or it gets to the end (NULL);
}
```

| Visual Representation | | | | | | | | | |
|   -         |  -   | -  | -  | -  |   -    |  - | -  | - | - |
| **After above While loop:** | head | -> | n1 | -> | n2 (q)| -> | n3 (p)|   |   |

```
//eventually...
q->next = NULL;
free(p);
```

Conditional Statements to determine info about the above Linked List (where we want to delete the Node 'p' is pointing to):

```
if(head->next == NULL){ //there is only one node (head)
	head = head->next;
	free(p);
}

else{
	if(p == head){ //this is the First Node
		head = head->next;
		free(p);
	}
	else if(p->next == NULL){ //this is the last node
		q->next = NULL;
		free(p);
	}
	else{ //the node is somewhere in the middle of the list
		q->next = p->next;
		free(p);
	}
}
```

- It can be helpful to define a tail pointer in addition to the head pointer
	- the tail pointer would point to the end of the list

---

[-> Notes 02/07](02-07.md)