Data Structure & Algorithm
===
## Basic of Data Structure and Algorithm
### What's Data Structure?
Data structure is a way to "organize data" in a way that enables it to be processed in an efficient time.
- Array
- Linked List
- Stack
- Queue
- Tree
- Hashing
- Graph, etc.
### What's Algorithm?
Algorithm is a set of rules with a data structure to be followed to solve a problem.
### Types of Data Structure:
- Primitive DS:
- String
- Integer
- Boolean
- Float
- etc
- Non-Primitive DS:
- Physical DS:
- Array
- Linked List
- Logical DS: The follows types only based on Array or Linked List, no third physical data structure.
- Stack
- Queue
- Hashing
- Tree
- Graph
- etc
## Recursion
### Properties of recursion:
- Some operation is performed multiple times with different input.
- In every step we try to make the problem smaller.
- We mandatorily need to have a base condition, which tells system when to stop the recursion.
Example from Non-computing World:
Pseudo code for unpacking gift:
```
function unpackGift(giftBox) {
if (giftBox equals null) return null // match properties 3
else if (giftBox equals gift) return giftBox // match properties 3
else
unpackGift(open(giftBox)) // match properties 1, 2
}
```
### Why should we learn "Recursion"?
1. Because it makes the code easy to write (compared to "iterative(loop)") whenever a given problem can be broken down into a similar sub-problem.
2. Because it is heavily used in Data Structure like Tree, Graph, etc.
- Although Tree or Graph can be used with iterative but it will make the code to become more complicated.
3. It is heavily used in techniques like "Divide and Conquer", "Greedy" and "Dynamic Programming".
### Format of a Recursive Function
- Recursive case: case where the function recur.
- Base case: case where the function does not recur.
- Stop the function.
- Avoid infinite loop.
Example:
```
function sampleRecursive(parameter) {
if (base case is satisfied) {
return some base case value
} else {
sampleRecursive(modified parameter)
}
}
```
### How 'Recursion' works internally?
- Stack mechanism
- LIFO (Last In First Out)
```
function foo(n) {
if (n < 1) return
else
foo(n - 1)
print "Hello world" + n
}
main() {
foo(2) // call foo(2), and main function is not completed.
// so system will push main() into stack.
}
```
Step:1 push main into stack
| stack |
| ------ |
| |
| |
| |
| main() |
```
function foo(n) { // n = 2
if (n < 1) return
else
foo(n - 1) // call foo(1)
print "Hello world" + n // Because foo(2) is not completed
// so push foo(2) into stack.
}
```
Step:2 push foo(2) into stack
| stack |
| ------ |
| |
| |
| foo(2) |
| main() |
```
function foo(n) { // n = 1
if (n < 1) return
else
foo(n - 1) // call foo(0)
print "Hello world" + n // Because foo(1) is not completed
// so push foo(1) into stack.
}
```
Step:3 push foo(1) into stack
| stack |
| ------ |
| |
| foo(1) |
| foo(2) |
| main() |
```
function foo(n) { // n = 0
if (n < 1) return // stop and complete the function.
else
foo(n - 1)
print "Hello world" + n
}
```
Step:4 finish foo(0) function.
```
function foo(n) { // n = 1
if (n < 1) return
else
foo(n - 1) // foo(0)
print "Hello world" + n // Hello world1
}
```
Step:5 pop foo(1) and finish the function.
| stack |
| ---------- |
| |
| ~~foo(1)~~ |
| foo(2) |
| main() |
```
function foo(n) { // n = 2
if (n < 1) return
else
foo(n - 1) // foo(1)
print "Hello world" + n // Hello world2
}
```
Step:6 pop foo(2) and finish the function.
| stack |
| ---------- |
| |
| ~~foo(1)~~ |
| ~~foo(2)~~ |
| main() |
Step:7 pop main and finish the function.
| stack |
| ---------- |
| |
| ~~foo(1)~~ |
| ~~foo(2)~~ |
| ~~main()~~ |
### Factorial with recursion
Definition:
- Factorial of a non-negative integer n
- denoted by n!
- is the product of all positive integers from 1 to n
Example:
5! = 5 * 4 * 3 * 2 * 1 = 120
```
function factorial(n) {
if n equals 0
return 1
return n * factorial(n - 1)
}
```
### Fibonacci Series with recursion
Definition:
- A series of numbers in which each number is the sum of the two proceding numbers
- First two numbers by definition are 0 and 1
Example: 0, 1, 1, 2, 3, 5, 8, 13, 21,...
```
function fib(n) {
if n is less than 1
return error message
else if n equals 1 or 2
return n - 1
else
return fib(n - 1) + fib(n - 2)
}
```
### Recursion vs Iteration
| Particulars | Recursion | Iteration |
|:---------------:|:-----------------------------------------------------------:|:---------:|
| Space Efficient | No (Because it needs system stack to store function) | Yes |
| Time Efficient | No (Because it needs taking more time for push() and pop()) | Yes |
| Ease of Code | Yes | No |
### When to Use/Avoid Recursion?
**When to use:**
- When we can easily breakdown a problem into similar subproblem.
- When we are ok with extra overhead (both time and space) that comes with it.
- When we need a quick working solution instead of efficient one.
**When not to use:**
- If the response to any of the above statments is NO, we should not go with recursion.
### Practical use of 'Recursion':
- Stack
- Tree - Traversal/Searching/Insertion/Deletion
- Sorting - Quick Sort, Merge Sort
- Divide and Conquer
- Dynamic Programming
- etc...
## Algorithm Run Time Analysis
### What & Why of 'Algorithm Run Time Analysis'
**What is 'Algorithm Run Time Analysis':**
- It is a study of a given algorithm's running time, by identifying its behavior as the input size for the algorithm increases. In a layman's language we can say, 'how much time will the given algorithm will take to run'.
**Why should we learn this?**
- To measure 'efficiency (performance)' of a given algorithm.
### Notations for 'Algorithm Run Time Analysis'
- **Omega(Ω) - Base case**:
- This Notation gives the tighter lower bound of a given algorithm.
- In a layman's language we can say that for any given input, running time of a given algorithm will not be **less than** given time.
- Using situation: Sometimes what happens we need to know that for any given algorithm how much time **minimum** is required.
- **Big-o(O) - Worst case**:
- This Notation gives the tighter upper bound of a given algorithm.
- In a layman's language we can say that for an given input, running time of a given algorithm will not be **more than** given time.
- Using situation: Sometimes what happens we need to know that for any given algorithm how much time **maximum** is required.
- **Theta(ϴ) - Average case**:
- This Notation decides whether upper bound or lower bound of a given algorithm are same or not.
- In a layman's language we can say that for an given input, running time of a given algorithm will **on an average** be equal to given time.
### Example of Notation
1. Find a target number from below given array.
2. `...` stands for many amount of elements around billion.
| 5 | 18 | 3 | 54 | 26 | ... | 55 | 41 | ... | 19 | 10 |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
Ans:
- We need to find the target number in which one by one from given unsorted array.
- Omega(Ω):
- In the best case we can say that for any given input, ruuning time of a given algorithm will not less than given time.
- Ω(1) if target number is 5.
- Big-o(O):
- In the worst case we can say that for any given input, running time of a given algorithm will no more than given time.
- O(n) if target number is 10.
- Theta(ϴ):
- In the average case we can say that for any given input, running time of a given algorithm will on an average be equal to given time.
- ϴ(n/2)
### Examples of 'Algorithm Run Time Complexities'
| Time Complexity | Name | Example |
|:---------------:|:---------------------------:|:-----------------------------------------:|
| O(1) | Constant (常數) | Adding an element at front of linked list |
| O(logN) | Logarithm (對數) | Finding an element in sorted array |
| O(N) | Linear (線性) | Finding an element in unsorted array |
| O(NlogN) | Linear Logarithm (線性對數) | Merge sort |
| O(N^2) | Quadratic (二次方) | Shortest path between 2 nodes in a graph |
| O(N^3) | Cubic (立方) | Matrix Multiplication |
| O(2^N) | Exponential (指數) | Tower of Hanoi Problem |
### Eample#1 Finding the biggest number: Time Complexity of 'Iterative Algorithm'
| 5 | 18 | 3 | 54 | 26 | ... | 55 | 41 | ... | 19 | 10 |
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
```
function findBiggestNumber(int[] array) { ----------- input n
biggestNumber = array[0] ----------------------- O(1)
loop: i = 1 - array.lenght - 1 ------------------ O(n-1) => O(n)
if (array[i] > biggestNumber) ------------------ O(1)
biggestNumber = array[i] ------------------ O(1)
return biggestNumber ------------------ O(1)
}
```
The Time Complexity is:
O(2n) + O(1)
--> We can eliminate the constant time complexity because it is really not important.
--> Finally Time Complexity: O(n)
### Example#2 Finding the biggest number: Time Compexity of 'Recursive Algorithm'
```
function findBiggestNumber(int[] array, int index) { -------- T(n)
static biggestNumber = Integer.Min ---------------- O(1)
if (index == -1) ---------------- O(1)
return biggestNumber ---------------- O(1)
if (array[index] > biggestNumber) ---------------- O(1)
biggestNumber = array[index] ---------------- O(1)
return findBiggestNumber(array, index - 1) ---------------- T(n-1)
}
```
**Back Substitution:**
```
T(n) = O(1) + T(n-1) ---------- Equation#1
T(-1) = O(1) ---------- Base Condition
T(n-1) = O(1) + T((n-1) - 1)
= O(1) + T(n-2) ---------- Equation#2
T(n-2) = O(1) + T((n-2) - 1)
= O(1) + T(n-3) ---------- Equation#3
-----------------------------------------------------------
T(n) = 1 + T(n-1) // T(n-1) = O(1) + T(n-2)
= 1 + (1 + T(n-2))
= 2 + T(n-2) // T(n-2) = O(1) + T(n-3)
= 2 + (1 + T(n-3))
= 3 + T(n-3)
= ...
= ...
= k + T(n-k) // let n-k = -1, so k = n + 1
= (n+1) + T(n-(n+1))
= n + 1 + T(-1) // T(-1) = O(1)
= n + 1 + 1
= O(n)
```
### Example#3 Finding the target number in a given sorted array: Time Complexity of 'Recursive Algorithm'
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 | 110 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
Problem Statement: Given a sorted array of 11 numbers, find number 110.
Solution: Using binary search
```
function findNumber(int[] array, start, end, target) { --------- T(n)
if (start == end) { --------- O(1)
if (array[start] == target) --------- O(1)
return start --------- O(1)
else
return Error("Not find the target number") --------- O(1)
}
mid = findMid(array, start, end) --------- O(1)
if (array[mid] == target) --------- O(1)
return mid --------- O(1)
else if (array[mid] > target) --------- O(1)
return findNumber(array, start, mid, target) --------- O(n/2)
else
return findNumber(array, mid, end, target) --------- O(n/2)
}
```
**Back Substitution:**
```
T(n) = O(1) + T(n/2) --------- Equation#1
T(1) = O(1) --------- Base Condition
T(n/2) = O(1) + T(n/4) --------- Equation#2
T(n/4) = O(1) + T(n/8) --------- Equation#3
---------------------------------------------------
T(n) = 1 + T(n/2) // T(n/2) = O(1) + T(n/4)
= 1 + (1 + T(n/4))
= 2 + T(n/4) // T(n/4) = O(1) + T(n/8)
= 2 + (1 + T(n/8))
= 3 + T(n/8)
= ...
= ...
= k + T(n/2^k) // let n/2^k = 1, n = 2^k, k = logn
= logn + T(1)
= logn + 1
= O(logn)
```
## Physical Data Structure - Array
### What is Array?
| 10 | 20 | 30 | 40 | 50 | 60 |
| --- | --- | --- | --- | --- | --- |
Definition:
Array is a data structure consisting of a collection of elements, each identified by array index. An array is stored such that the position of element can be computed from its index cell by a mathematical formula.
Properties of Array:
- Array can store data of specified data type.
- It has contiguous memory locaion.
- Every 'cell' of an array has an unique 'index'.
- Index starts with 0.
- 'Size of array' needs to be specified mandatorily and can not be modified.
### Types of Array
- One Dimention Array
- Multi Dimention Array
- 2 Dimention Array
- 3 Dimention Array
- etc
**Representation of One Dimention Array**
| index | 0 | 1 | 2 | 3 | 4 | 5 |
| ----- | --- | --- | --- | --- | --- | --- |
| | 10 | 20 | 30 | 40 | 50 | 60 |
Array[column]
Getting 60 from array => arr[5]
Getting 20 from array => arr[1]
**Representation of 2 Dimention Array**
| index | 0 | 1 | 2 | 3 | 4 | 5 |
| ----- | --- | --- | --- | --- | --- | --- |
| 0 | 10 | 20 | 30 | 40 | 50 | 60 |
| 1 | 110 | 120 | 130 | 140 | 150 | 650 |
| 2 | 210 | 220 | 230 | 240 | 250 | 260 |
Array[row][column]
Getting 110 from array => arr[1][0]
Getting 230 from array => arr[2][2]
**Representation of 3 Dimention Array**
Array[depth][row][column]
Getting 30 from array => arr[0][0][2]
Getting 90 from array => arr[1][0][1]
Getting 700 from array => arr[2][1][1]
### Common Operations of an Array:
- Declaring, Instantiating, Initializing an Array
- Inserting a given value
- Traversing a given array
- Accessing a given cell#
- Searching a given value
- Deleting a value
- Updating a given value
### Declaring, Instantiating, Initializing an 1D Array
**Time Complexity - Declaring, Instantiating, Initializing**
```
Declaring:
- dataType[] arr -------------------- O(1)
- Example: int[] arr
Instantiating:
- arrayRefVar = new dataType[size] ------- O(1)
- Example: arr = new int[10]
Initializing:
arr[0] = 1 -------------------- O(1)
arr[1] = 2 -------------------- O(1)
arr[2] = 3 -------------------- O(1)
...
arr[9] = 10 -------------------- O(1)
// sum of all initialzation is O(n)
Declaring & Instantiating & Initializing:
int[] arr = {1,2,3,4,5,6,7,8,9} ---------- O(1)
```
**Space Time Complexity: O(n)**
### Inserting a given value in 1D Array
```
function InsertValueIntoArrayIndex(arr, value, insertionIndex) {
if (insertionIndex < 1 || insertionIndex > arr.lenght)
return "Wrong InsertIndex Error";
int[] newArray = new int[arr.lenght + 1]
physicalArrayIndex = insertionIndex - 1;
for (int i = 0, size = newArray.length; i < size; i++) {
if (i == physicalArrayIndex)
newArray[i] = value;
else if (i < physicalArrayIndex)
newArray[i] = arr[i];
else
newArray[i] = arr[i - 1];
}
return newArray;
}
```
**Time Complexity - Inserting a given value**
```
if (insertionIndex < 1 || insertionIndex > arr.lenght) --------------- O(1)
return "Wrong InsertIndex Error"; ---------------------------------- O(1)
int[] newArray = new int[arr.lenght + 1]; ----------------------------- O(1)
physicalArrayIndex = insertionIndex - 1; ----------------------------- O(1)
for (int i = 0, size = newArray.length; i < size; i++) { -------------- O(n)
if (i == physicalArrayIndex) --------------------------------------- O(1)
newArray[i] = value; --------------------------------------------- O(1)
else if (i < physicalArrayIndex) ----------------------------------- O(1)
newArray[i] = arr[i]; -------------------------------------------- O(1)
else --------------------------------------------------------------- O(1)
newArray[i] = arr[i - 1]; ---------------------------------------- O(1)
}
return newArray; ----------------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(n), because need to create a new array**
### Traversing a given 1D array
```
function traverseArray(arr) {
for (int i = 0, size = arr.length; i < size; i++) {
print arr[i];
}
}
```
**Time Complexity - Traversing a given array**
```
for (int i = 0, size = arr.length; i < size; i++) { ------------------ O(n)
print arr[i]; ------------------------------------------------------ O(1)
}
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Accessing a given cell#
```
function accessCell(arr, cellIndex) {
if (cellIndex < 0 || cellIndex > arr.lenght - 1)
return "Index Out of Bound Error";
return arr[cellIndex];
}
```
**Time Complexity - Accessing a given cell# in 1D Array**
```
if (cellIndex < 0 || cellIndex > arr.lenght - 1) ------------------- O(1)
return "Index Out of Bound Error"; ------------------------------- O(1)
return arr[cellIndex]; --------------------------------------------- O(1)
```
**Time Complexity: O(1)**
**Space Complexity: O(1)**
### Search a given value an 1D Array
```
function search(arr, targetValue) {
for (int i = 0, size = arr.length; i < size; i++) {
if (arr[i] == targetValue)
return i;
}
return -1;
}
```
**Time Complexity: Searching a given value**
```
for (int i = 0, size = arr.length; i < size; i++) { ------------------ O(n)
if (arr[i] == targetValue) ----------------------------------------- O(1)
return i; -------------------------------------------------------- O(1)
}
return -1; ----------------------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Deleting a value an 1D Array
```
function delete(arr, targetIndex) {
if (targetIndex < 1 || targetIndex > arr.lenght)
return "Index Out of Bound Error";
int[] newArray = new int[arr.length - 1];
physicalTargetIndex = targetIndex - 1;
for (int i = 0, size = newArray.length; i < size; i++) {
if (i < physicalTargetIndex)
newArray[i] = arr[i];
else {
newArray[i] = arr[i + 1];
}
}
return newArray;
}
```
**Time Complexity: Deleting a value**
```
if (targetIndex < 1 || targetIndex > arr.lenght) --------------------- O(1)
return "Index Out of Bound Error"; --------------------------------- O(1)
int[] newArray = new int[arr.length - 1]; ---------------------------- O(1)
physicalTargetIndex = targetIndex - 1; ------------------------------- O(1)
for (int i = 0, size = newArray.length; i < size; i++) { ------------- O(n)
if (i < physicalTargetIndex) --------------------------------------- O(1)
newArray[i] = arr[i]; -------------------------------------------- O(1)
else { ------------------------------------------------------------- O(1)
newArray[i] = arr[i + 1]; ---------------------------------------- O(1)
}
}
return newArray; ----------------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(n)**
### Updating a given value in an 1D Array
```
function updateValueFromArray(arr, value, targetIndex) {
if (targetIndex < 0 || targetIndex > arr.lenght - 1)
return "Index Out of Bound Error";
arr[targetIndex] = value;
}
```
**Time Complexity: Updating a given value**
```
if (targetIndex < 0 || targetIndex > arr.lenght - 1) ----------------- O(1)
return "Index Out of Bound Error"; --------------------------------- O(1)
arr[targetIndex] = value; -------------------------------------------- O(1)
```
**Time Complexity: O(1)**
**Space Complexity: O(1)**
### Declaring, Instantiating, Initializing an 2D Array
```
Declaring:
- dataType[][] arr --------------------------------- O(1)
- Example: int[][] arr
Instantiating:
- arrayRefVar = new dataType[rowSize][columnSize] ------- O(1)
- Example: arr = new int[3][10]
Initializing:
arr[0][] = 1 --------------------------------- O(1)
arr[1][] = 2 --------------------------------- O(1)
arr[2][] = 3 --------------------------------- O(1)
...
arr[2][9] = 30 --------------------------------- O(1)
// sum of all initialzation is O(m*n)
```
### Updating a given value in a 2D Array
```
function updateValue(arr, targetValue, rowIndex, columnIndex) {
if (rowIndex > arr's row size || columnIndex > arr's column size)
return "Index Out of Bounds Exception";
arr[rowIndex][columnIndex] = targetValue;
}
```
**Time Complexity: Updating a given value**
```
if (rowIndex > arr's row size || columnIndex > arr's column size) ---- O(1)
return "Index Out of Bounds Exception"; ---------------------------- O(1)
arr[rowIndex][columnIndex] = targetValue; ---------------------------- O(1)
```
**Time Complexity: O(1)**
**Space Complexity: O(1)**
### Traversing a given 2D Array
```
function traverseArray(arr) {
loop: i = 0 to arr's row size
loop: j = 0 to arr's column size
print arr[i][j]
}
```
**Time Complexity: Traversing a given 2D Array**
```
loop: i = 0 to arr's row size ---------------------------------------- O(m)
loop: j = 0 to arr's column size ----------------------------------- O(n)
print arr[i][j] -------------------------------------------------- O(1)
```
**Time Complexity: O(m*n)**
**Space Complexity: O(1)**
### Searching a value in a given 2D Array
```
function searchValue(arr, targetValue) {
loop: i = 0 to arr's row size
loop: j = 0 to arr's column size
if targetValue equals arr[i][j]
return [i, j]
return "TargetValue Not Found"
}
```
**Time Complexity: Searching a value in a given 2D Array**
```
loop: i = 0 to arr's row size ---------------------------------------- O(m)
loop: j = 0 to arr's column size ----------------------------------- O(n)
if targetValue equals arr[i][j] ---------------------------------- O(1)
return [i, j] -------------------------------------------------- O(1)
return "TargetValue Not Found" --------------------------------------- O(1)
```
**Time Complexity: O(m*n)**
**Space Complexity: O(1)**
### When to Use/Avoid Array
- When to Use:
- When there is a need to store multiple similar type of data.
- When random access is regular affair.
- When to Avoid:
- Data can be stored are non-homogenous.
- When number of data to be stored is not known in advance.
## Physical Data Structure - Linked List
### What is Linked List?
**Definition:** A linked list is a linear data structure where each element is a separate object. Each element (node) of a list comprises of two items - the data and a reference to the next node. The most powerful feature of Linked List is that it is of variable size.
**Components of Linked List:**
- Node: Contains Data & Reference to the next Node.
- Head: Reference to the first node in the list.
- Why we need the Head?
- Bascue we need to traverse Linked List from the first node.
- Tail: Reference to the last node in the list.
- Why we need the Tail?
- We can easily add a node into the end of the list using the tail.
**Example:**
### Types of Linked List:
- Single Linked List: In a single linked list each node in the list stores the data of the node and a reference to the next node in the list. It does not store any reference to the previous node.
- Why Use Single Linked List?
- It is most basic form of linked list which give the flexibility to add/remove nodes at runtime.
- Circular Single Linked List: In the case of circular single linked list, the only change that occurs is that the end of the given list is linked back to the front.
- Why Use Circulr Single Linked List?
- When we wnat to loop through the list indefinitely until the list exists.
- Example: Multiplayer board game. If we are tracking player's turn in linked list.
- Double Linked List: In a double linked list each node contains two references, that references to the previous node and the next node.
- Why Use Double Linked List?
- When we want to move in both direction depending on requirement.
- Example: Music player which has next and previous buttons.
- Circular Double Linked List: In case of the circular double linked list, the only change that occurs is that the end of the given list is linked back to the front of the list and vice versa.
- Why Use Circular Double Linked List?
- When we want to loop through the list indefinitely until the list exists. We also want to move both forward and backward.
- Example: "Alt + Tab" button in Windows.
### Creation of Single Linked List
**Pseudo code of cration of single linked list**
```
function createSingleLinkedList(nodeValue) {
create a head, tail pointer and initialize with null
create a blank node
node.value = nodeValue
node.next = null
head = node
tail = node
}
```
**Time Complexity: Creation of Single Linked List**
```
create a head, tail pointer and initialize with null ----------------- O(1)
create a blank node -------------------------------------------------- O(1)
node.value = nodeValue ----------------------------------------------- O(1)
node.next = null ----------------------------------------------------- O(1)
head = node ---------------------------------------------------------- O(1)
tail = node ---------------------------------------------------------- O(1)
```
**Time Complexity: O(1)**
**Space Complexity: O(1)**
### Insertion in Single Linked List
- Insert at start of Linked List
- Insert at end of Linked List
- Insert at a specified location in Linked List
**Pseudo code of insertion in Single Linked List**
```
function insertInLinkedList(nodeValue, location, head)
if head == null return error
create a blank node
node.value = nodeValue
if location equals 0 // insert at first position
node.next = head.next
head = node
else if location equals tail // insert at last position
tail.next = node
tail = node
else
loop: tmpNode = 0 to location - 1 // insert at specified position
node.next = tmpNode.next
tmpNode.next = node
```
**Time Complexity: Insertion in Single Linked List**
```
if head == null return error ----------------------------------------- O(1)
create a blank node -------------------------------------------------- O(1)
node.value = nodeValue ----------------------------------------------- O(1)
if location equals head ----------------------------------------------- O(1)
node.next = head.next ----------------------------------------------- O(1)
head = node -------------------------------------------------------- O(1)
else if location equals tail ----------------------------------------- O(1)
tail.next = node --------------------------------------------------- O(1)
tail = node -------------------------------------------------------- O(1)
else ----------------------------------------------------------------- O(1)
loop: tmpNode = 0 to location - 1 ---------------------------------- O(n)
node.next = tmpNode.next ----------------------------------------- O(1)
tmpNode.next = node ---------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(n)**
### Traversal of Single Linked List
**Pseudo code of traversal of Single Linked List**
```
function traverseLinkedList(head) {
if head == NULL, then return
loop: head to tail
print currentNode.value
}
```
**Time Complexity: Traversal of Single Linked List**
```
if head == NULL, then return ----------------------------------------- O(1)
loop: head to tail --------------------------------------------------- O(n)
print currentNode.value -------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Searching a node in Single Linked List
**Pseudo code of searching a node in Single Linked List**
```
function searchFromLinkedList(head, targetValue) {
if head == NULL, then return NULL // Not Found
loop: currentNode = head to tail
if currentNode.value equals to targetValue
return currentNode
return NULL // Not Found
}
```
**Time Complexity: Searching a node in Single Linked List**
```
if head == NULL, then return NULL // Not Found ----------------------- O(1)
loop: currentNode = head to tail ------------------------------------- O(n)
if currentNode.value equals to targetValue ------------------------- O(1)
return currentNode ----------------------------------------------- O(1)
return NULL // Not Found --------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Deletion of node from Single Linked List
- Delete first element
- Delete last element
- Delete any node
**Pseudo code of deletion of node from Single Linked List**
```
function deleteInLinkedList(head, location) {
if head == null return error
if location equals head // delete at first position
head = head.next
if !(existLinkedList(head)) tail = null
else if location equals tail // delete at last postion
if head equals tail, then head = tail = null, return
loop: the 2th last node (tmpNode)
tmpNode.next = null
tail = tmpNode
else
loop: tmpNode = 0 to location - 1
tmpNode.next = tmpNode.next.next
}
```
**Time Complexity: Deletion of node from Single Linked List**
```
if head == null return error ----------------------------------------- O(1)
if location equals head ---------------------------------------------- O(1)
head = head.next --------------------------------------------------- O(1)
if !(existLinkedList(head)) tail = null ---------------------------- O(1)
else if location equals tail ----------------------------------------- O(1)
if head equals tail, then head = tail = null, return --------------- O(1)
loop: the 2th last node (tmpNode) ---------------------------------- O(n)
tmpNode.next = null ---------------------------------------------- O(1)
tail = tmpNode --------------------------------------------------- O(1)
else ----------------------------------------------------------------- O(1)
loop: tmpNode = 0 to location - 1 ---------------------------------- O(n)
tmpNode.next = tmpNode.next.next --------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Deletion of entire Single Linked List
**Pseudo code of deleting entire Single Linked List**
```
function deleteEntireLinkedList() {
head = tail = null
}
```
**Time Complexity: Deleting entire Single Linked List**
```
head = tail = null --------------------------------------------------- O(1)
```
**Time Complexity: O(1)**
**Space Complexity: O(1)**
### Creation of Circular Single Linked List
**Pseudo code of creation of Circular Single Linked List**
```
function CreateCircularSingleLinkedList(nodeValue) {
create head, tail and initialize to NULL
create a blank node
node.value = nodeValue
node.next = node
head = node
tail = node
}
```
**Time Complexity: Creation of Circular Single Linked List**
```
create head, tail and initialize to NULL ----------------------------- O(1)
create a blank node -------------------------------------------------- O(1)
node.value = nodeValue ----------------------------------------------- O(1)
node.next = node ----------------------------------------------------- O(1)
head = node ---------------------------------------------------------- O(1)
tail = node ---------------------------------------------------------- O(1)
```
**Time Complexity: O(1)**
**Space Complexity: O(1)**
### Insertion in Circular Single Linked List
- Insert at start of Linked List
- Insert at a specified location in Linked List
- Insert at end of Linked List
**Pseudo code of Insertion in Circular Single Linked List**
```
function insertInCircularSingleLinkedList(head, nodeValue, location) {
if head equals null, then return error
create a blank node
node.value = nodeValue
if location equals head
node.next = head
head = node
tail.next = node
else if location equals tail
tail.next = node
node.next = head
tail = node
else
loop: tmpNode = 0 to location - 1
node.next = tmpNode.next
tmpNode.next = node
}
```
**Time Complexity: Insertion in Circular Single Linked List**
```
if head equals null, then return error ------------------------------- O(1)
create a blank node -------------------------------------------------- O(1)
node.value = nodeValue ----------------------------------------------- O(1)
if location equals head ---------------------------------------------- O(1)
node.next = head --------------------------------------------------- O(1)
head = node -------------------------------------------------------- O(1)
tail.next = node --------------------------------------------------- O(1)
else if location equals tail ----------------------------------------- O(1)
tail.next = node --------------------------------------------------- O(1)
node.next = head --------------------------------------------------- O(1)
tail = node -------------------------------------------------------- O(1)
else ----------------------------------------------------------------- O(1)
loop: tmpNode = 0 to location - 1 ---------------------------------- O(n)
node.next = tmpNode.next ----------------------------------------- O(1)
tmpNode.next = node ---------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Traversal of Circular Single Linked List
**Pseudo code of traversal of Circular Single Linked List**
```
function traverseCircularSingleLinkedList(head) {
if head == NULL, then return
loop: head to tail
print currentNode.value
}
```
**Time Complexity: Traversal of Circular Single Linked List**
```
if head == NULL, then return ----------------------------------------- O(1)
loop: head to tail --------------------------------------------------- O(n)
print currentNode.value -------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Search a Node in Circular Single Linked List
**Pseudo code of searching a node in Circular Single Linked List**
```
function searchFromLinkedList(head, targetValue) {
if head == NULL, then return NULL // Not Found
loop: currentNode = head to tail
if currentNode.value equals to targetValue
return currentNode
return NULL // Not Found
}
```
**Time Complexity: Searching a node in Circular Single Linked List**
```
if head == NULL, then return NULL // Not Found ----------------------- O(1)
loop: currentNode = head to tail ------------------------------------- O(n)
if currentNode.value equals to targetValue ------------------------- O(1)
return currentNode ----------------------------------------------- O(1)
return NULL // Not Found --------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Deletion a Node from Circular Single Linked List
- delete a node at first position
- delete a node at last postion
- delete any node apart from above 2
**Pseudo code of deletion a node from Circular Single List**
```
function deleteFromCircularSingleLinkedList(head, location) {
if head == null, then return error
if location equals head
head = head.next
if head equals null
tail.next = null
tail = null
else
tail.next = head
else if location equals tail
if head equals tail, then head = tail = head.next = null
loop: the 2nd last node (tmpNode)
tmpNode.next = head
tail = tmpNode
else
loop: tmpNode = 0 to location - 1
tmpNode.next = tmpNode.next.next
}
```
**Time Complexity: Deletion a node from Circular Single List**
```
if head == null, then return error ----------------------------------- O(1)
if location equals head ---------------------------------------------- O(1)
head = head.next --------------------------------------------------- O(1)
if head equals null ------------------------------------------------ O(1)
tail.next = null ------------------------------------------------- O(1)
tail = null ------------------------------------------------------ O(1)
else --------------------------------------------------------------- O(1)
tail.next = head ------------------------------------------------- O(1)
else if location equals tail ----------------------------------------- O(1)
if head equals tail, then head = tail = head.nex = null, return ---- O(1)
loop: the 2nd last node (tmpNode) ---------------------------------- O(n)
tmpNode.next = head ---------------------------------------------- O(1)
tail = tmpNode --------------------------------------------------- O(1)
else ----------------------------------------------------------------- O(1)
loop: tmpNode = 0 to location - 1 ---------------------------------- O(n)
tmpNode.next = tmpNode.next.next --------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Deletion of entire Circular Single Linked List
**Pseudo code of deletion of entire Circular Single Linked List**
```
function deleteEntireLinkedList() {
head = null
tail.next = null
tail = null
}
```
**Time Complexity: Deleting of entire Circular Single Linked List**
```
head = null ---------------------------------------------------------- O(1)
tail.next = null ----------------------------------------------------- O(1)
tail = null ---------------------------------------------------------- O(1)
```
**Time Complexity: O(1)**
**Space Complexity: O(1)**
### Creation of Double Linked List
**Pseudo code of creation of Double Linked List**
```
function createDoubleLinkedList(nodeValue) {
create head, tail and initialize to NULL
create a blank node
node.value = nodeValue
node.next = null
node.prev = null
head = node
tail = node
}
```
**Time Complexity: Creation of Double Linked List**
```
create head, tail and initialize to NULL ----------------------------- O(1)
create a blank node -------------------------------------------------- O(1)
node.value = nodeValue ----------------------------------------------- O(1)
node.next = null ----------------------------------------------------- O(1)
node.prev = null ----------------------------------------------------- O(1)
head = node ---------------------------------------------------------- O(1)
tail = node ---------------------------------------------------------- O(1)
```
**Time Complexity: O(1)**
**Space Complexity: O(1)**
### Insertion in Double Linked List
- Insert at start of Linked List
- Insert at end of Linked List
- Insert at any other place apart from above 2
**Pseudo code of insertion in Double Linked List**
```
function insertInDoubleLinkedList(head, nodeValue, location) {
if head equals null then return error
create a blank node
node.value = nodeValue
if location equals head
node.next = head
node.prev = null
head.prev = node
head = node
else if location equals tail
node.next = null
node.prev = tail
tail.next = node
tail = node
else
loop: tmpNode = 0 to location - 1
node.next = tmpNode.next
node.prev = tmpNode
tmpNode.next.prev = node
tmpNode.next = node
}
```
**Time Complexity: Insertion in Double Linked List**
```
if head equals null then return error -------------------------------- O(1)
create a blank node -------------------------------------------------- O(1)
node.value = nodeValue ----------------------------------------------- O(1)
if location equals head ---------------------------------------------- O(1)
node.next = head --------------------------------------------------- O(1)
node.prev = null --------------------------------------------------- O(1)
head.prev = node --------------------------------------------------- O(1)
head = node -------------------------------------------------------- O(1)
else if location equals tail ----------------------------------------- O(1)
node.next = null --------------------------------------------------- O(1)
node.prev = tail --------------------------------------------------- O(1)
tail.next = node --------------------------------------------------- O(1)
tail = node -------------------------------------------------------- O(1)
else ----------------------------------------------------------------- O(1)
loop: tmpNode = 0 to location - 1 ---------------------------------- O(n)
node.next = tmpNode.next ----------------------------------------- O(1)
node.prev = tmpNode ---------------------------------------------- O(1)
tmpNode.next.prev = node ----------------------------------------- O(1)
tmpNode.next = node ---------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Traversal in Double Linked List
**Pseudo code of traversal in Double Linked List**
```
function traverseInDoubleLinkedList() {
loop: head to tail (tmpNode)
print tmpNode.value
}
```
**Time Complexity: Traversal in Double Linked List**
```
loop: head to tail (tmpNode) ----------------------------------------- O(n)
print tmpNode.value ------------------------------------------------ O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Reverse Traversal in Double Linked List
**Pseudo code of reverse traversal of in Double Linked List**
```
function reverseTraverseInDoubleLinkedList() {
loop: tail to head (tmpNode)
print tmpNode.value
}
```
**Time Complexity: Reverse Traversal in Double Linked List**
```
loop: tail to head (tmpNode) ----------------------------------------- O(n)
print tmpNode.value ------------------------------------------------ O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Search a Node in Double Linked List
**Pseudo code of search a node in Double Linked List**
```
function searchInDoubleLinkedList(targetValue) {
loop: head to tail (tmpNode)
if tmpNode.value equals targetValue
return tmpNode
return null // Not Found
}
```
**Time Complexity: Search a Node in Double Linked List**
```
loop: head to tail (tmpNode) ---------------------------------------- O(n)
if tmpNode.value equals targetValue ------------------------------- O(1)
return tmpNode -------------------------------------------------- O(1)
return null --------------------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Deletion in Double Linked List
- Delete node at first position
- Delete node at last position
- Delete any node at any specified location apart from above 2.
**Pseudo code of deletion in Double Linked List**
```
function deleteInDoubleLinkedList(head, location) {
if head equals null then return error
if head equals tail
head = tail = null
else if location equals head
head = head.next
head.prev = null
else if location equals tail
tail = tail.prev
tail.next = null
else
loop: tmpNode = 0 to location - 1
tmpNode.next = tmpNode.next.next
tmpNode.next.prev = tmpNode
}
```
**Time Complexity: Deletion in Double Linked List**
```
if head equals null then return error -------------------------------- O(1)
if head equals tail -------------------------------------------------- O(1)
head = tail = null ------------------------------------------------- O(1)
else if location equals head ----------------------------------------- O(1)
head = head.next --------------------------------------------------- O(1)
head.prev = null --------------------------------------------------- O(1)
else if location equals tail ----------------------------------------- O(1)
tail = tail.prev --------------------------------------------------- O(1)
tail.next = null --------------------------------------------------- O(1)
else ----------------------------------------------------------------- O(1)
loop: tmpNode = 0 to location - 1 ---------------------------------- O(n)
tmpNode.next = tmpNode.next.next --------------------------------- O(1)
tmpNode.next.prev = tmpNode -------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Deletion Entire Double Linked List
**Pseudo code of deletion entire Double Linked List**
```
function deleteEntireDobuleLinkedList() {
loop: head to tail (tmpNode)
tmpNode.prev = null
head = tail = null
}
```
**Time Complexity: Deletion Entire Double Linked List**
```
loop: head to tail (tmpNode) ----------------------------------------- O(n)
tmpNode.prev = null ------------------------------------------------ O(1)
head = tail = null --------------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Creation of Circular Double Linked List
**Pseudo code of creation of Circular Double Linked List**
```
function createCircularDoubleLinkedList(nodeValue) {
create head, tail and initialize to NULL
create a blank node
node.value = nodeValue
head = node
tail = node
node.next = node
node.prev = node
}
```
**Time Complexity: Creation of Circular Double Linked List**
```
create head, tail and initialize to NULL ----------------------------- O(1)
create a blank node -------------------------------------------------- O(1)
node.value = nodeValue ----------------------------------------------- O(1)
head = node ---------------------------------------------------------- O(1)
tail = node ---------------------------------------------------------- O(1)
node.next = node ----------------------------------------------------- O(1)
node.prev = node ----------------------------------------------------- O(1)
```
**Time Complexity: O(1)**
**Space Complexity: O(1)**
### Insertion in Circular Double Linked List
- Insert at start of Linked List
- Insert at end of Linked List
- Insert at any other place apart from above 2
**Pseudo code of insertion in Circular Double Linked List**
```
function insertInCircularDoubleLinkedList(head, nodeValue, location) {
if head equals NULL then return error
create a blank node
node.value = nodeValue
if location equals head
node.next = head
node.prev = tail
head.prev = node
tail.next = node
head = node
else if location equals tail
node.next = head
node.prev = tail
tail.next = node
head.prev = node
tail = node
else
loop: tmpNode = 0 to location - 1
node.next = tmpNode.next
node.prev = tmpNode
tmpNode.next = node
node.next.prev = node
}
```
**Time Complexity: Insertion in Circular Double Linked List**
```
if head equals NULL then return error -------------------------------- O(1)
create a blank node -------------------------------------------------- O(1)
node.value = nodeValue ----------------------------------------------- O(1)
if location equals head ---------------------------------------------- O(1)
node.next = head --------------------------------------------------- O(1)
node.prev = tail --------------------------------------------------- O(1)
head.prev = node --------------------------------------------------- O(1)
tail.next = node --------------------------------------------------- O(1)
head = node -------------------------------------------------------- O(1)
else if location equals tail ----------------------------------------- O(1)
node.next = head --------------------------------------------------- O(1)
node.prev = tail --------------------------------------------------- O(1)
tail.next = node --------------------------------------------------- O(1)
head.prev = node --------------------------------------------------- O(1)
tail = node -------------------------------------------------------- O(1)
else ----------------------------------------------------------------- O(1)
loop: tmpNode = 0 to location - 1 ---------------------------------- O(n)
node.next = tmpNode.next ----------------------------------------- O(1)
node.prev = tmpNode ---------------------------------------------- O(1)
tmpNode.next = node ---------------------------------------------- O(1)
node.next.prev = node -------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Traversal in Circular Double Linked List
**Pseudo code of traversal in Circular Double Linked List**
```
function traverseInCircularDoubleLinkedList() {
loop: head to tail (tmpNode)
print tmpNode.value
}
```
**Time Complexity: Traversal in Circular Double Linked List**
```
loop: head to tail (tmpNode) ----------------------------------------- O(n)
print tmpNode.value ------------------------------------------------ O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Reverse Traversal in Double Linked List
**Pseudo code of reverse traversal of in Circular Double Linked List**
```
function reverseTraverseInCircularDoubleLinkedList() {
loop: tail to head (tmpNode)
print tmpNode.value
}
```
**Time Complexity: Reverse Traversal in Circular Double Linked List**
```
loop: tail to head (tmpNode) ----------------------------------------- O(n)
print tmpNode.value ------------------------------------------------ O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Search a Node in Circular Double Linked List
**Pseudo code of search a node in Circular Double Linked List**
```
function searchInCircularDoubleLinkedList(targetValue) {
loop: head to tail (tmpNode)
if tmpNode.value equals targetValue
return tmpNode
return null // Not Found
}
```
**Time Complexity: Search a Node in Circular Double Linked List**
```
loop: head to tail (tmpNode) ---------------------------------------- O(n)
if tmpNode.value equals targetValue ------------------------------- O(1)
return tmpNode -------------------------------------------------- O(1)
return null --------------------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Deletion in Circular Double Linked List
- Delete node at first position
- Delete node at last position
- Delete node any position apart from above 2
**Pseudo code of deletion in Circular Double Linked List**
```
function deleteInCircularDoubleLinkedList(head, location) {
if head equals NULL then return error
if head equals tail
head.next = head.prev = null
head = tail = null
else if location equals head
head = head.next
head.prev = tail
tail.next = head
else if location equals tail
tail = tail.prev
tail.next = head
head.prev = tail
else
loop: tmpNode = 0 to location - 1
tmpNode.next = tmpNode.next.next
tmpNode.next.prev = tmpNode
}
```
**Time Complexity: Deletion in Circular Double Linked List**
```
if head equals NULL then return error -------------------------------- O(1)
if head equals tail -------------------------------------------------- O(1)
head.next = head.prev = null --------------------------------------- O(1)
head = tail = null ------------------------------------------------- O(1)
else if location equals head ----------------------------------------- O(1)
head = head.next --------------------------------------------------- O(1)
head.prev = tail --------------------------------------------------- O(1)
tail.next = head --------------------------------------------------- O(1)
else if location equals tail ----------------------------------------- O(1)
tail = tail.prev --------------------------------------------------- O(1)
tail.next = head --------------------------------------------------- O(1)
head.prev = tail --------------------------------------------------- O(1)
else ----------------------------------------------------------------- O(1)
loop: tmpNode = 0 to location - 1 ---------------------------------- O(n)
tmpNode.next = tmpNode.next.next --------------------------------- O(1)
tmpNode.next.prev = tmpNode -------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
### Deletion Entire Circular Double Linked List
**Pseudo code of deletion entire Circular Double Linked List**
```
function deleteEntireCircularDoubleLinkedList() {
tail.next = null
loop: head to tail (tmpNode)
tmpNode.prev = null
head = null
tail = null
}
```
**Time Complexity: Deletion Entire Circular Double Linked List**
```
tail.next = null ----------------------------------------------------- O(1)
loop: head to tail (tmpNode) ----------------------------------------- O(n)
tmpNode.prev = null ------------------------------------------------ O(1)
head = null ---------------------------------------------------------- O(1)
tail = null ---------------------------------------------------------- O(1)
```
**Time Complexity: O(n)**
**Space Complexity: O(1)**
## Array vs Linked List
| Particulars | Array | Linked List |
| -------------------- |:-----:|:-----------:|
| Adding an element | Hard | Easy |
| Deleting an element | Hard | Easy |
| Accessing an element | Easy | Hard |
| Updating an element | Easy | Hard |
| Particulars | Array | Linked List |
| --------------------------------- |:----------------:|:-------------:|
| Create | O(1) | O(1) |
| Insertion at 1th position | O(1)/O(n) resize | O(1) |
| Insertion at Last position | O(1)/O(n) resize | O(1) |
| Insertion at Kth position | O(1)/O(n) resize | O(n) |
| Deletion from 1th position | O(1)/O(n) resize | O(1) |
| Deletion from Last Position | O(1)/O(n) resize | O(1)/O(n) SLL |
| Deletion from Kth position | O(1)/O(n) resize | O(n) |
| Searching in Unsorted Data | O(n) | O(n) |
| Searching in Sorted Data | O(log n) | O(n) |
| Accessing Nth element | O(1) | O(n) |
| Traversing | O(n) | O(n) |
| Deleting entire Array/Linked list | O(1) | O(1)/O(n) DLL/CDLL |
Note:
`resize` means that we need to re-allocate a new array.
`SLL` means that it is Single Linked List.
`DLL` means that it is Double Linked List.
`CDLL` means that it is Circular Double Linked List.
## Stack
**Definition**: `Stack` is a Logical Data Structure, its property is Last In First Out (FILO).
**Why need Stack**: When we need to create an application which utilizes 'last incoming data first processing'.
**Example**: Implemention of 'back' button in Browser.
Sign in with Wallet
Connect another wallet