arraylist,
admin
11月 30, 2020
0
ArrayList
- resize function:
- int [] data = new int[0];
- int [] newdata = new int [data.length * 2 + 1];
- data = new data
- realization : 00:20:57
time complexity
- executing time cost and input scale (worst case analysis)
maintaining cost and using cost
- Unsorted data structrue has low maintaining cost, but higher using cost, like linked list;
- Sorted data structrue has high maintaining cost, but high lower using cost, you can find any element by index, like sorted array
Stack
- Last in First Out (LIFO)
- low maintaining cost
Operation :Build-in java function
- (add)push
- (removw)pop
- (get)peek
- isEmpty
- empty
realization
- using arraylist: find the basic data structure function and the realized data structure function rationship
- Using LinkedList: add element as head, it is a better way to realize stack by linked list, time complexity is smaller
Queue
- First in First out (FIFO)
- LinkedList to realize
- queue in System: message Queue
Operation : Build-in Java function
- enqueue
- dequeue
example of using
|
arraylist |
linked list |
stack |
BST |
| add(head) |
O(n) |
O(1) |
|
O(log(n) |
| add(tail) |
O(1) |
O(n) |
|
|
| get |
O(1) |
O(n) |
|
|
|
|
|
|
|
|
|
|
|
|
近期评论