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