Data structures provide an easy way of organising, retrieving, managing, and storing data.
- Elements are arranged in one dimension ,also known as linear dimension.
- Example: lists, stack, queue, linked List etc.
- Elements are arranged in one-many, many-one and many-many dimensions.
- Example: tree, graph, table, etc.
- Array is a collection of items that are stored conductively in the memory.
- The idea is to store multiple items of the same type together.
- This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).
- Array Index: In an array, elements are identified by their indexes. Array index starts from 0.
- Array element: Elements are items stored in an array and can be accessed by their index.
- Array Length: The length of an array is determined by the number of elements it can contain.
// The syntax of declaring a static array is:
<data type><variable name>[]
= {<data1>, <data2>,…..<dataN> };
// Example:
int arr[] = { 2, 5, 6, 9, 7, 4, 3 }; // Static or compile time memory allocation - Static Array
int dyArr[10]; // Dynamic ArryaAssume there is a class of five students and if we have to keep records of their marks in examination then, we can do this by declaring five variables individual and keeping track of records but what if the number of students becomes very large, it would be challenging to manipulate and maintain the data.
- Traversal: Traverse through the elements of an array.
- Insertion: Inserting a new element in an array.
- Deletion: Deleting element from the array.
- Searching: Search for an element in the array.
- Sorting: Maintaining the order of elements in the array.
- What the address are how they work?
- what are some of the limitations?
- different operations you can perform on an array
- the complexity of those operations
- A linked list is a fundamental data structure in computer science.
- It consists of nodes where each node contains data and a reference (link) to the next node in the sequence. This allows for dynamic memory allocation and efficient insertion and deletion operations compared to arrays.
- Linear collection of items, are inserted and removed in a specific order.
- It follows LIFO principles
Uses of Stack
- Undo / Redo operations
- Back tracking(puzzle maze)
const stack = new Stack();
// stack = []
stack.isEmpty(); // returns boolean value
stack.push(1); // add value in stack [1]
stack.push(3); // add value in stack [1, 3]
stack.push(6); // add value in stack [1, 3, 6]
stack.peek(); // give last value (6) from the stack
stack.pop(); // remove value from stack- Linear collection of items, are inserted and removed in a specific order.
- It follows FIFO principles
const queue = new Queue();
queue.isEmpty(); // returns boolean value
queue.enqueue(1); // add value in queue
queue.enqueue(5); // add value in queue
queue.enqueue(7); // add value in queue
quere.peek(); // give top first value (1) from the queue
queue.dequeue(); // remove value from queueA tree is a hierarchical data structure that consists of nodes connected by edges. It resembles an upside-down tree, where each node has a parent-child relationship. The topmost node is called the root, and nodes with no children are called leaves.
A node is a fundamental unit of a tree that contains data and may have zero or more children nodes.
The root is the topmost node of a tree, from which all other nodes are descended.
A leaf is a node with no children, i.e., it is at the end of a branch.
A parent is a node that has one or more children, and a child is a node connected to a parent.
Nodes that share the same parent are called siblings.
A binary tree is a tree in which each node has at most two children: a left child and a right child.
graph TD;
A;
B;
C;
D;
E;
A --> B;
A --> C;
B --> D;
B --> E;
In a binary search tree, the left child of a node contains values less than the node, and the right child contains values greater than the node.
A heap is a specialized tree-based data structure that satisfies the heap property. It is commonly used to implement priority queues.
In a max heap, the value of each node is greater than or equal to the values of its children. The maximum element is at the root.
graph TD;
A(90);
B(80);
C(75);
D(65);
E(50);
F(45);
G(35);
H(20);
I(10);
A --> B;
A --> C;
B --> D;
B --> E;
C --> F;
C --> G;
D --> H;
D --> I;
In a min heap, the value of each node is less than or equal to the values of its children. The minimum element is at the root.
graph TD;
A(10);
B(20);
C(35);
D(45);
E(50);
F(65);
G(75);
H(80);
I(90);
A --> B;
A --> C;
B --> D;
B --> E;
C --> F;
C --> G;
D --> H;
D --> I;
Insert a new element at the next available position in the heap and then heapify to maintain the heap property.
Remove the root element (maximum in a max heap, minimum in a min heap), replace it with the last element, and then heapify.
Adjust the elements of the heap to maintain the heap property after an insertion or deletion operation.
- Priority queues
- Heap sort algorithm
- Dijkstra's shortest path algorithm