Post-class 05/06

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