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	T[]

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:

	PriorityQueue<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[]

Carl's Bonfire

Java-Data-Structure