Basic Data Structures Keynotes

Small cheatsheet of data structures and the associated cost.

List ADT

The list abstract data structure is one of the basic data structures around. Allows you to dynamically insert and remove and access elements.

Linked List

boolean add(E e)

E get(int index)

E set(int index, E element)

E remove(int index)

Array List

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

boolean add(E e)

E get(int index)

E set(int index, E element)

E remove(int index)

Queue ADT

FIFO Queue

You can implement it efficiently with a Linked List or Array List.

boolean enqueue(E e)

E dequeue()

E peek()

LIFO Queue (Stack)

Can be implemented efficiently using an Array List or Linked List.

boolean push(E e)

E dequeue()

E peek()

Dequeue

Is a double ended queue, elements can be added to the front or the back. Can be implemented efficiently in both doubly linked list and Array List (with the circular array list implementation).

Binary Heaps

They help to implement priority queues efficiently. The binary heap is a binary tree that needs to be completed. They contain a heap property, Min Heap where are the childrens have a priority less or equal than the parent or Max heap (viceversa).

boolean add(E e)

E remove()

Set and Map ADT

They both can reuse the same implementation (a map is a set with an extra value field). The main caracteristic is that the elements never duplicates.

Binary Search Tree

Is important to note that this operations cost are only for self balance trees, like example AVL or Red-black trees. If they are regular trees, the operations can cost up to O(n).

BST allows you to manage the data in a sorted fashion (They produce Sorted Sets and Maps).

boolean add(E e)

boolean contains(E e)

boolean remove(E e)

traversal

Hash Table

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance’s size (the number of elements) plus the “capacity” of the backing HashMap instance (the number of buckets). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

boolean add(E e)

boolean contains(E e)

boolean remove(E e)

traversal