---
description: Part 1
---

# Data Structures

## What is Big O notation ?

It is a special notaton that tells you how fast your algorithm grows.&#x20;

More specifically, it lets you compare the number of operatoins. &#x20;

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&#x20;

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.&#x20;

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

* Probing
  * (1) Linear probing : Disadvantage: clustering
  * (2) quadratic probing&#x20;

(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)&#x20;

## 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:&#x20;

* Insert/Delete: O (log n)
* Search:O(n)
* Search for max element: O(1)

## What is Heap (Memory)?

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

&#x20;Objects stored in the heap are globally accessible

## What is Stack (Memory)?

&#x20;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.&#x20;

## 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&#x20;

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.

