diff options
Diffstat (limited to '05-06.md')
| -rw-r--r-- | 05-06.md | 215 |
1 files changed, 215 insertions, 0 deletions
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)| |