12 lines
1.3 KiB
Markdown
12 lines
1.3 KiB
Markdown
# Review DataStructure
|
|
|
|
* Hajin Ju, 2024062806
|
|
|
|
| * | Arrays<br>(not sorted) | Arrays<br>(sorted) | LinkedLists<br>(not sorted) | LinkedList<br>(sorted) | Binary ST<br>(avg) | Balanced ST | HashTables<br>(avg) |
|
|
| --------------------------- | ---------------------- | ------------------ | --------------------------- | ---------------------- | ------------------ | ----------- | ------------------- |
|
|
| Search($x$) | $O(n)$ | $O(\lg n)$ | $O(n)$ | $O(n)$ | $O(\lg n)$ | $O(\lg n)$ | $O(1)$ |
|
|
| Insert($x$) | $O(1)$ | $O(n)$ | $O(1)$ | $O(n)$ | $O(\lg n)$ | $O(\lg n)$ | $O(1)$ |
|
|
| Insert($x$)<br>(dup search) | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ | $O(\lg n)$ | $O(\lg n)$ | $O(1)$ |
|
|
| Delete($i$) | $O(1)$ | $O(n)$ | $O(1)$ | $O(1)$ | $O(\lg n)$ | $O(\lg n)$ | $O(1)$ |
|
|
| Delete($x$) | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ | $O(\lg n)$ | $O(\lg n)$ | $O(1)$ |
|