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