Day 17: Data Structures Explained in a Beginner-Friendly Way
Screenshot:-
Understanding data structures is key to writing efficient code. Today, we’ll explore some fundamental data structures: Linked Lists, Stacks, Queues, Binary Trees, and optionally, Graphs. We’ll break down each data structure with simple examples and code.
Activity 1: Linked List
A Linked List is a collection of nodes where each node points to the next node in the sequence.
Task 1: Node Class
First, create a Node class to represent each element in the linked list.
Example Code:
class Node {
constructor(value) {
this.value = value; // Node value
this.next = null; // Pointer to the next node
}
}
Explanation:
value: Holds the data for the node.next: Points to the next node in the list (initially set tonull).
Task 2: LinkedList Class
Next, implement a LinkedList class with methods to add, remove, and display nodes.
Example Code:
class LinkedList {
constructor() {
this.head = null; // Start with an empty list
}
add(value) {
const newNode = new Node(value);
if (this.head === null) {
this.head = newNode;
} else {
let current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = newNode;
}
}
remove() {
if (this.head === null) return;
if (this.head.next === null) {
this.head = null;
return;
}
let current = this.head;
while (current.next.next !== null) {
current = current.next;
}
current.next = null;
}
display() {
let current = this.head;
while (current !== null) {
console.log(current.value);
current = current.next;
}
}
}
Explanation:
add(value): Adds a new node with the given value to the end of the list.remove(): Removes the last node from the list.display(): Prints the values of all nodes in the list.
Activity 2: Stack
A Stack is a collection of elements that follows Last-In-First-Out (LIFO) order.
Task 3: Stack Class
Implement a Stack class with methods to add, remove, and view the top element.
Example Code:
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
}
Explanation:
push(element): Adds an element to the top of the stack.pop(): Removes the top element from the stack.peek(): Returns the top element without removing it.
Task 4: Reverse a String Using Stack
Use the Stack class to reverse a string by pushing all characters onto the stack and then popping them off.
Example Code:
function reverseString(str) {
const stack = new Stack();
for (let char of str) {
stack.push(char);
}
let reversed = '';
while (stack.peek() !== undefined) {
reversed += stack.pop();
}
return reversed;
}
console.log(reverseString("hello")); // Output: "olleh"
Explanation:
Push each character of the string onto the stack.
Pop characters from the stack to form the reversed string.
Activity 3: Queue
A Queue is a collection of elements that follows First-In-First-Out (FIFO) order.
Task 5: Queue Class
Implement a Queue class with methods to add, remove, and view the first element.
Example Code:
class Queue {
constructor() {
this.items = [];
}
enqueue(element) {
this.items.push(element);
}
dequeue() {
return this.items.shift();
}
front() {
return this.items[0];
}
}
Explanation:
enqueue(element): Adds an element to the end of the queue.dequeue(): Removes the first element from the queue.front(): Returns the first element without removing it.
Task 6: Simulate a Printer Queue
Use the Queue class to simulate a printer queue where print jobs are added and processed.
Example Code:
function printJobs(jobs) {
const queue = new Queue();
for (let job of jobs) {
queue.enqueue(job);
}
while (queue.front() !== undefined) {
console.log(`Printing: ${queue.dequeue()}`);
}
}
printJobs(["Document1", "Document2", "Document3"]);
// Output:
// Printing: Document1
// Printing: Document2
// Printing: Document3
Explanation:
Add print jobs to the queue.
Process (print) jobs in the order they were added.
Activity 4: Binary Tree
A Binary Tree is a tree data structure where each node has at most two children (left and right).
Task 7: TreeNode Class
Create a TreeNode class to represent each node in the binary tree.
Example Code:
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
Explanation:
value: Holds the data for the node.left: Points to the left child node.right: Points to the right child node.
Task 8: BinaryTree Class
Implement a BinaryTree class with methods for inserting values and performing in-order traversal.
Example Code:
class BinaryTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
return;
}
let current = this.root;
while (true) {
if (value < current.value) {
if (current.left === null) {
current.left = newNode;
return;
}
current = current.left;
} else {
if (current.right === null) {
current.right = newNode;
return;
}
current = current.right;
}
}
}
inOrderTraversal(node = this.root) {
if (node === null) return;
this.inOrderTraversal(node.left);
console.log(node.value);
this.inOrderTraversal(node.right);
}
}
Explanation:
insert(value): Adds a value to the tree, ensuring it goes to the correct position.inOrderTraversal(node): Visits nodes in the left subtree, then the current node, and finally the right subtree.
Activity 5: Graph (Optional)
Graphs are used to represent networks where nodes (vertices) are connected by edges.
Task 9: Graph Class
Implement a Graph class with methods to add vertices, add edges, and perform breadth-first search (BFS).
Example Code:
class Graph {
constructor() {
this.vertices = {};
}
addVertex(vertex) {
if (!this.vertices[vertex]) {
this.vertices[vertex] = [];
}
}
addEdge(vertex1, vertex2) {
if (this.vertices[vertex1] && this.vertices[vertex2]) {
this.vertices[vertex1].push(vertex2);
this.vertices[vertex2].push(vertex1); // For undirected graph
}
}
bfs(start) {
const visited = new Set();
const queue = [start];
while (queue.length > 0) {
const vertex = queue.shift();
if (!visited.has(vertex)) {
visited.add(vertex);
console.log(vertex);
queue.push(...this.vertices[vertex]);
}
}
}
}
Explanation:
addVertex(vertex): Adds a vertex to the graph.addEdge(vertex1, vertex2): Connects two vertices with an edge.bfs(start): Performs a breadth-first search starting from a vertex.
Task 10: Simple Network Example
Use the Graph class to represent a simple network and perform BFS.
Example Code:
const network = new Graph();
network.addVertex("A");
network.addVertex("B");
network.addVertex("C");
network.addEdge("A", "B");
network.addEdge("A", "C");
network.bfs("A"); // Output: A B C
Explanation:
Add vertices to represent nodes in the network.
Add edges to represent connections.
Perform BFS to explore nodes starting from a given node.
Conclusion
By implementing and using these data structures, you'll gain a solid understanding of how to manage and manipulate data efficiently. Practice these concepts to build a strong foundation in computer science. Happy coding!