diff options
| -rw-r--r-- | 05-01.md | 5 | ||||
| -rw-r--r-- | 05-04.md | 246 | ||||
| -rw-r--r-- | 05-06.md | 215 |
3 files changed, 466 insertions, 0 deletions
@@ -186,3 +186,8 @@ pNew->next = NULL; ``` - We need to allocate memory **every time** when we generate a new node. It's the same process. So we omit it in the later discussions + +--- + +[05/04 ->](05-04.md) + 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) diff --git a/05-06.md b/05-06.md new file mode 100644 index 0000000..1a7ae0b --- /dev/null +++ b/05-06.md @@ -0,0 +1,215 @@ +[\<- 05/04](05-04.md) + +--- + +## BigO + +- **When given pPrev** (the address of the previous node), it takes us **O(1)** to insert/delete a node in a linked list +- Then how do we find pPrev? + +## Linked List - Search + +- To search a linked list, **no matter if it's ordered or not**, we have to do sequential search. Why? + - Because there's no **physical relationship** among nodes + +- What is the bigO? -> O(n) + +## Search - Exercise 1 + +- What is the bigO run time for the following tasks? + - In an **unsorted** singly linked list + +|Task|Runtime| +|----|-------| +|Find a specific value |O(n)| +|Find the largest value |O(n)| +|Find the smallest value |O(n)| +|Remove the largest value |O(n)| +|Remove the smallest value |O(n)| +|Insert a new value at the end of the list|O(n)| + +- How about an unsorted singly linked **circular** list? + +|Task|Runtime| +|----|-------| +|Find a specific value |O(n)| +|Find the largest value |O(n)| +|Find the smallest value |O(n)| +|Remove the largest value |O(n)| +|Remove the smallest value |O(n)| +|Insert a new value at the end of the list|O(n)| + +- It will still give us O(n) for all, circular or not + +## Search - Exercise 2 + +- What is the bigO runt time for the following tasks? + - In a **sorted** singly linked list (ascending order) + +|Task|Runtime| +|----|-------| +|Find a specific value |O(n)| +|Find the largest value |O(n)| +|Find the smallest value |O(1)| +|Remove the largest value |O(n)| +|Remove the smallest value|O(1)| +|Insert a new element |O(n)| + +- How about a sorted **circular doubly-linked** list + +|Task|Runtime| +|----|-------| +|Find a specific value |O(n)| +|Find the largest value |O(1)| +|Find the smallest value |O(1)| +|Remove the largest value |O(1)| +|Remove the smallest value|O(1)| +|Insert a new element |O(n)| + +--- + +- Given a **sorted** singly linked list (ascending order), what to return? + - Found - true? or false? + - If the node is **found** in the list, return **its location (i.e. pCur)** + - If the node is **not found** in the list, for insertion and eletion purpose, we also need to return the **location of the previous node** (i.e. pPrev). Therefore, pCur represents the node's successor if it is inserted + +|Condition|pPrev|pLoc|Return| +|---------|-----|----|------| +|Target < first node |NULL/dummy node |First node |False| +|Target = first node |NULL/dummy node |First node |True | +|first < Target < last|Largest node < Target|First node > Target|False| +|Target = middle node |Node's predecessor |Equal node |True | +|Target = last node |Last's predecessor |Last node |True | +|Target > last node |Last node |NULL |False| + +``` +bool ListSearch(struct list *pList, struct node *pPrev, struct node *pLoc, struct node *pTarget){ + assert(pList != NULL && pTarget != NULL); + pPrev = NULL; //or dummy node, depending on how you create the linked list + pLoc = pList->head; + while(pLoc != NULL && pTarget->data > pLoc->data){ + pPrev = pLoc; + pLoc = pLoc->next; + } + if(pLoc == NULL) return false; + if(pTarget->data == pLoc->data) return true; + return false; +} +``` + +## Linked List with a Tail Pointer + +- Advantage: make it possible to directly access the last element in the list + 1. Adding a new element to the end of the list + 2. Accessing the max/min (assuming the list is sorted) +- Question: If we want to access the element right before the last element in the list, will the tail pointer make it easier? + - It doesn't help (assuming the list is singly-linked) -> still O(n) +- Further Question: How about if we want to remove the last element? + - It doesn't help (assuming the list is singly-linked) since you still need to change where the previous node is pointing + +## Exercise 3 + +- What is the bigO run time for the following tasks in a **sorted singly linked list with a tail pointer** (ascending order) + +|Task|Runtime| +|----|-------| +|Find a specific value |O(n)| +|Find the largest value |O(1)| +|Remove the largest value |O(n)| +|Find the smallest value |O(1)| +|Remove the smallest value|O(1)| +|Insert a new element |O(n)| + +## Traverse List + +- Start at the first node and examine each node in succession until the last node has been processed. +- When to use it? + - Change the value of each node + - Print the list + - Sum/Average, etc. +- We need a walking pointer moving from node to node + +``` +void printList(struct list *pList){ + assert(pList != NULL); + NODE *pCur = pList->head; //current pointer + + while(pCur != NULL){ + printf("%d", pCur->data); + pCur = pCur->next; + } +} +``` + +## Destroy List + +- What to do? - No dummy node + - Delete all the nodes in the list + - Recycle their memory + +``` +void destroyList(struct list *pList){ + assert(pList != NULL); + NODE *pDel = pList->head; + + while(pList->head != NULL){ + pDel = pList->head; + pList->head = pDel->next; + free(pDel); + pList->count--; + } + + free(pList); +} +``` + +# Use Linked List to Implement Different ADT + +## Big-O Analysis + +- Let's use a **singly-linked list** to implement a **queue** and a **stack** + +Stack + +| |Push|Pop |Top | +|-----------------------|----|----|----| +|**Head pointer only** |O(1)|O(1)|O(1)| +|**Head & Tail pointer**|O(1)|O(1)|O(1)| + +Queue + +| |Enqueue |Dequeue | +|-----------------------|---------|---------| +|**Head pointer only** |O(1)/O(n)|O(n)/O(1)| +|**Head & Tail pointer**|O(1) |O(1) | + +--- + +- Let's use a singly-linked list to implement a SET and a BAG + +A SET + +| | |HAS |Add |Remove|Min |Max | +|------------|-----------|----|----|------|----|----| +|**Unsorted**|Head only |O(n)|O(n)|O(n) |O(n)|O(n)| +|**Unsorted**|Head & Tail|O(n)|O(n)|O(n) |O(n)|O(n)| +|**Sorted** |Head only |O(n)|O(n)|O(n) |O(1)|O(n)| +|**Sorted** |Head & Tail|O(n)|O(n)|O(n) |O(1)|O(1)| + +A BAG + +| | |HAS |Add |Remove| +|------------|-----------|----|----|------| +|**Unsorted**|Head only |O(n)|O(1)|O(n) | +|**Unsorted**|Head & Tail|O(n)|O(1)|O(n) | +|**Sorted** |Head only |O(n)|O(n)|O(n) | +|**Sorted** |Head & Tail|O(n)|O(n)|O(n) | + +--- + +|SET |Unsorted Array|Sorted Array|Hash Table|Unsorted Linked List|Sorted Linked List| +|---------------|--------------|------------|----------|--------------------|------------------| +|**Search/Find**|O(n) |O(log(n)) |O(n) |O(n) |O(n) | +|**Add** |O(n) |O(n) |O(n) |O(n) |O(n) | +|**Remove** |O(n) |O(n) |O(n) |O(n) |O(n) | +|**Min/Max** |O(n) |O(1) |O(1) |O(n) |O(1) (assuming fast access to tail)| |