Java Data Structure Review
Interesting Summary for inheritances and relationships of default Java Data Structure
I feel like it’s more fun to summarize built in Java 7 data structures using this kinda graph. This should be a on going project as well as I could prepare for my first year exams :)
Collection
(interface)
can’t be instantiated. i.e. Queue<Interger> queue = new Queue<Integer>(); // will print error
List (interface)
ArrayList
- Implemented with Array
- Common methods:
Method | Runtime | Description | Return Type |
---|---|---|---|
add(E e) | O(1) | Appends the specified element to the end of this list. | boolean |
add(int index, E element) | O(N) | Inserts the specified element at the specified position in this list. | void |
clear() | O(1)? | Removes all of the elements from this list. | void |
contains(Object o) | O(n) | Returns true if this list contains the specified element. | boolean |
get(int index) | O(1) | Returns the element at the specified position in this list. | E |
isEmpty() | O(1)? | Returns true if this list contains no elements | boolean |
remove(int index) | O(n) | Removes the element at the specified position in this list. | E |
remove(Object o) | O(n) | Removes the first occurrence of the specified element from this list, if it is present. | boolean |
size() | O(1) | return size | int |
toArray | O(n) | ArrayList<T> al = new ArrayList<>() then call al.toArray(new <T>[]) to convert it to primitive array |
<T>[] |
- Advantage:
- calls to get and set take constant time
- Disadvantage:
- insertion and removal are expensive unless changes are made at the end of arraylist
- inefficient for search
- notation of capacity (size of underlying array)
- insertion has to be done manually, there is no method written for insertion
LinkedList
- Implements both Queue (interface) and Deque (interface)
- Implemented with List
- Common Methods:
Method | Runtime | Description | Return Type |
---|---|---|---|
add(E e) | O(1) | Appends the specified element to the end of this list. | boolean |
add(int index, E element) | O(N) | Inserts the specified element at the specified position in this list. (equivalent to offer() /offerLast() ) or offerFirst when add(0, E ele) is called |
void |
contains(Object o) | O(n) | Returns true if this list contains the specified element. | boolean |
get(int index) | O(n) | Returns the element at the specified position in this list. | E |
indexOf(Object o) | O(n) | Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. | int |
offer(E e) | O(n) | Adds the specified element as the tail (last element) of this list. | boolean |
peek() | O(1) | Retrieves but doesn’t remove the head (first element) of this list. | E |
poll() | O(1) | Retrieves and removes the head (first element) of this list. | E |
pop() | O(1) | Pops an element from the stack represented by this list. | E |
push(E e) | O(1) | Pushes an element onto the stack represented by this list. | void |
remove() | O(1) | Retrieves and removes the head (first element) of this list. | E |
remove(int index) | O(N) | Removes the element at the specified position in this list. | E |
size() | O(1) | return size | int |
toArray() | O(n) | return array containing elements in the list | Object[] |
toArray(T[] a) | O(n) | return array with generic types |
- Advantage:
- insertion and removal is cheap(constant time), provided the position of the changes is known
- efficient space usage
- Disadvantage:
- not easily indexable (slow gets and sets)
- inefficient for search
*Stack
- Stack Implements Vector(sync), Vector implements List
- Anything you can do with Stack you can do with linkedlist, the only reason to use stack will be to utilize synchronous ability of Vector, since Stack implements a Vector
- common menthods:
empty() | O(1) | To test if this stack is empty | boolean |
---|---|---|---|
peek() | O(1) | looks at the top of the stack without removing it from the stack | E |
pop() | O(1) | Removes the object at the top of this stack and returns that object as the value of this function. | E |
push() | O(1) | Pushes an item onto the top of this stack. | E |
search(Object o) | O(n) | Returns the 1-based position where an object is on this stack. | int |
- implementation
- list: push is to add node to the front of list and pop is to remove from front of list
- array: topOfStack is initialized to -1, when push, arr[topOfStack++]=element; when pop, return arr[–topOfStack]; use topOfStack==-1 to check if emtpy
- applications
- balance symbols
- postfix expression
- infix to postfix conversion
- method calls
PriorityQueue
Implements Queue
Construction:
By Comparator class:
1
2
3
4
5
6PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare(Integer a, Integer b){
return a-b;
}
});By Lambda:
1
PriorityQueue<Integer> pq = new PriorityQueue<>((Integer a, Integer b) -> b-a);
Method | Runtime | Description | Return Type
– |:—:| — | :—:
add(E e)| O(log n) | Appends the specified element to the end of this list. | boolean
clear()| O(n) | removes all element| void
contains(Object o)| O(n) worst time| contains|boolean
iterator()|O(1)|creates a iterator|Iterator
offer(E e)| O(log n) | insert element (like add)| boolean
peek()| O(1) | retreves the head| E
poll()| O(n) | retrieves and remove the head| E
remove(Object o)| o(n)|removes a single instance of the specified value| boolean
size()| O(1) | return the size| int
toArray()/toArray(T[] a)| O(n) | return the array | []/ T[]
HashSet
Implements Set
Construction:
with predefined value (might contain duplicates)
1
Set<Integer> set = new HashSet<>(Arrays.asList(1,1,1,2,2,3));
Method | Runtime | Description | Return Type
– |:—:| — | :—:
add(E e)| O(log n) | Appends the specified element to the end of this list. | boolean
clear()| O(n) | removes all element| void
contains(Object o)| O(n) worst time| contains|boolean
iterator()|O(1)|creates a iterator|Iterator
offer(E e)| O(log n) | insert element (like add)| boolean
peek()| O(1) | retreves the head| E
poll()| O(n) | retrieves and remove the head| E
remove(Object o)| o(n)|removes a single instance of the specified value| boolean
size()| O(1) | return the size| int
toArray()/toArray(T[] a)| O(n) | return the array | []/ T[]