1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
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)|
|
