[\<- 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