diff options
Diffstat (limited to '05-04.md')
| -rw-r--r-- | 05-04.md | 246 |
1 files changed, 246 insertions, 0 deletions
diff --git a/05-04.md b/05-04.md new file mode 100644 index 0000000..e7269fb --- /dev/null +++ b/05-04.md @@ -0,0 +1,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) |