ADT

List

1. Consist of count (number of nodes on list), compare function, and reference to head node.
2. Each node has pointer to data and pointer to next node inside it.
3. get() O(N), insert() O(N), remove() O(N), removeAt() O(N), replace() O(N), int size() O(1), boolean isEmpty() O(1), boolean isFull() O(1)

Stack

1. FIFO all operation is O(1)
2. void push (x), pop(), top()
3.  Implementation
   1. Array Based
      1. If array-based stack is full, you can use array doubling (create new array 2x size of current then put all element inside.
   2. Linked List Based

Queue

1. LIFO all operation is O(1)
2. void enqueue(x), dequeue(), getFront()
3. Implementation
   1. Array Based
      1. Simpan item-item dalam suatu array dengan item
         terdepan pada index nol dan item terbelakang pada
         index back.
      2. Enqueue: Increment back
      3. Dequeue: There is shifting of data that could makes the operation O(N)
         1. Better Dequeue: Use front untuk mencatat index terdepan
            1. Dequeue dilakukan denga increment front, jadi O(1)
      4. Implementation using circular array, storing front and back value and if front and back value exceed array length, return to the start.
      5. 
   2. Linked List Based
      1. Store two references: front and back
      2. Enqueue:
         1.  Buat sebuah node baru N yang datanya x
             if queue sebelumnya empty, maka front = back = N
             else tambahkan N di akhir (dan update back)
      3. Dequeue:
         1. Hapus elemen pertama: front = front.next

Set

1. No duplication of data. Could be O(N) at worst.
2. add(x), remove(x), isMember(x)
3. Concrete implementation Java.util.TreeSet (sorted)/HashSet

Map

1. Keys (unique), values (not unique)
2. put(key,value), remove(key), get(key). O(1) if through java implementation)
3. Concrete implementation Java.util.TreeMap (sorted by key)/HashMap

Priority Queue

1. Setiap elemen yang dimasukkan memiliki nilai prioritas
2. insert(x), deleteMin(), findMin(). Insert not O(1) deleteMin and findMin could be O(1)