Summary

Linked List

     A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

A linked list consists of nodes where each node contains a data field and a reference to the next node in the list.

Types of linked list

1. Single Linked List

2. Double/Doubly Linked List

3. Circular Single Linked List

4. Circular Doubly Linked List

Stack and Queue

Stack

     A stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). Stack has two fundamental operations which are push and pop.
     A real-life example of a stack is when you stack a plate on top of each other. The plate which is at the top is the first one to be removed and the plate which has been placed at the bottommost position remains in the stack for the longest time. So, it can be seen to follow LIFO(Last In First Out) or FILO(First In Last Out) order.

Stack operations

• push(x): add item x to the top of the stack
• pop(): remove an item from the top of the stack
• top() [peek]: reveal or return the top item from the stack

Infix, Postfix, and Prefix notation

• prefix: operator is written before operands
• infix: operator is written between operands
• postfix: operator is written after operands
• Postfix should be scanned from left to right while prefix scanned oppositely

Depth First Search (DFS)

     DFS is an algorithm for traversing or searching in a tree or graph. We start at the root of the tree and explore as far as possible along each branch before backtracking.

DFS applications:

• Finding articulation point and bridge in a graph
• Finding connected component
• Topological sorting
• etc.

Queue

     A Queue is a linear structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A queue has two fundamental operations which are push and pop (similar to stack). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Queue operations

• push(x): add item x to the back of the queue
• pop(): remove an item from the front of the queue
• front() [peek]: reveal or return the frontest item from the queue

Types of queue

• Circular queue
• Deques
• Priority queue

Breadth-First Search (BFS)

     BFS like DFS is also an algorithm for traversing or searching in a tree or graph. We start at the root of the tree (or some arbitrary node in graph) and explore all neighboring nodes level per level until we find the goal. BFS has many applications, such as:

• Finding connected component in a graph
• Finding the shortest path in an unweighted graph
• Ford-Fulkerson method for computing maximum flow
• etc.

Hashing ad Hash Table

Hashing

     Hashing is an important Data Structure that is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends on the efficiency of the hash function used.

In hashing, a string of characters is transformed into a shorter length value or key that represents the original string.

Hash table

Hash table is a table (array) where we store the original string. The index of the table is the hashed key while the value is the original string. 

Hash function

     A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are used to index a fixed-size table called a hash table.

     There are many ways to hash a string into a key. The following are some of the important methods for constructing hash functions:

• Mid-square
• Division (common)
• Folding
• Digit Extraction
• Rotating Hash

Collision

     Since a hash function gets us a small number for a key which is a big integer or string, there is a possibility that two keys result in the same value. The situation where a newly inserted key maps to an already occupied slot in the hash table is called collision and must be handled using some collision handling technique.

     There are two general ways to handle collisions:

• Linear Probing: search the next empty slot and put the string there
• Chaining: Put the string in a slot as a chained list (linked list)

Binary Tree

     In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Binary tree concept:

• A binary tree is a rooted tree data structure in which each node has at most two children
• Those two children usually distinguished as the left child and right child
• The node which doesn't have any child is called a leaf
  

Types of binary tree

• Perfect binary tree: a binary tree which every level are at the same depth
• Complete binary tree: a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A perfect binary tree is a complete binary tree.
• Skewed binary tree: a binary tree in which each node has at most one child
• Balanced binary tree: a binary tree in which no leaf is much farther away from the root than any other leaf.