Data Structures

Part 1

What is Big O notation ?

It is a special notaton that tells you how fast your algorithm grows.

More specifically, it lets you compare the number of operatoins.

Is O(logn) always faster than O(n) ? NO

O(n^2): Big O n square/ Big O n to 2

What is Linked List?

A linked list is a dynamic data structure that contains a sequence of nodes. Each node has at least two items - the data and a reference to the next node.

Insert or delete an element in a linked list has time complexity O(1)

Search: O(n)

What is Hash Table?

Hash table is a data structure that stores keys and their corresponding values.

The underlying idea is based on a hash function to store keys in the array locations (slots).

It allows a null key.

If there are 2 keys that map to the same location in an array, a collision is said to occur.

In the average case, hast table takes O(1) for everything insert, delete and search operations.

How to avoid collision?

(1) A lower load factor

load factor: the number of items in hash table / total number of slots

A good rule of thumb is to resize the hash table when its load factor is greater than 0.7.

Averaged out, hash tables take O(1) even with resizing.

(2) A better hash function

How to resolve collision?

(1) Open addressing

Probing: when collision occurs, we try to find an empty slot that is available for the new key.

Open addressing can be done by (1) probing (2) double hashing

• Probing

  • (1) Linear probing : Disadvantage: clustering

  • (2) quadratic probing

(2) Separate chaining

The idea is to make each cell of hash table point to a linked list of records that have same hash function value.

Open Addressing	Separate Chaining
Open Addressing requires more computation.	Chaining is Simpler to implement
Open addressing provides better cache performance as everything is stored in the same table.	Cache performance of chaining is not good because keys are stored using linked list.
Extra care for to avoid clustering and load factor	Extra space is needed for link.

What is Stack (Data Structure)?

Stack is an abstract data type that serves as a collection of elements.

It supports first-in last-out semantics for two operations - push and pop.

It can be implemented using array or linked list. Time complexity O(1).

Used frequently with 3 basic types of non-recursive tree traversal - preorder, inorder, postorder.

Practice use of stack: (1) back bottom of browser (2) recent dialed numbers on mobile phone

What is Queue (Data Structure)?

Queue is an ordered collection of items.

It has two basic operations - enqueue and dequeue - using first-in first-out strategy

Used frequently with (1) BFS (breadth-first search) and (2) level-order tree traversal.

Time Complexity: O(1)

What is Heap (Data Structure)

Heap is a specialized binary tree.

The keys must satisfy the heap property. In other words, in a max heap, if P is a parent node of C, then the key (the value) of P is either greater than or equal to the key (the value) of C.

Time Complexity:

• Insert/Delete: O (log n)

• Search:O(n)

• Search for max element: O(1)

What is Heap (Memory)?

Heap is application based. In other words, heap memory lives from the start till the end of application execution.

Objects stored in the heap are globally accessible

What is Stack (Memory)?

Stack is thread based. Each thread may have its private thread.

It is always referenced in LIFO (Last-In-First-Out) order.

Local primitive variables are stored in the stack memory.

What is Binary Tree

Binary tree is a tree data structure in which each node has at most two children.

Time Complexity of Tree Traversals: O(n)

Space Complexity of Tree Traversals: O(h) # h: tree height

There are 3 + 1 types of Tree Traversals: (1) Pre-order (2) In-order (3) Post-order, and (4) Level-order.

The first 3 types of tree traversals Pre-order In-order and Post-order can be implemented with Stack.

Level-order traversal can be implemented with queue.