Java-Data-Structure

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
  • 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

  • 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. 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
  • 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

Queue (interface)

Deque (interface)

Set (interface)

  • No duplicates

Map (interface)