Explore comprehensive definitions and insights into essential data structures terminology, enhancing your understanding of key concepts in JavaScript programming.
In the realm of computer science and programming, understanding data structures is fundamental to developing efficient and effective software solutions. This section aims to provide a comprehensive overview of key data structures terminology, particularly within the context of JavaScript. By familiarizing yourself with these terms, you will be better equipped to tackle complex programming challenges and optimize your code for performance and scalability.
An Array is one of the most basic and widely used data structures in programming. It is an ordered collection of elements, each accessible by an index. Arrays are versatile and can store elements of any data type, including numbers, strings, and objects. In JavaScript, arrays are dynamic, meaning their size can change during runtime, and they come with a variety of built-in methods for manipulation.
let fruits = ['Apple', 'Banana', 'Cherry'];
console.log(fruits[0]); // Output: Apple
fruits.push('Date');
console.log(fruits); // Output: ['Apple', 'Banana', 'Cherry', 'Date']
A Linked List is a linear data structure consisting of nodes, where each node contains a data element and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not provide index-based access, which makes them more flexible in terms of memory allocation but less efficient for random access.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
append(data) {
let newNode = new Node(data);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
}
}
A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Stacks are used in various applications, such as expression evaluation, backtracking algorithms, and maintaining function calls in programming languages.
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isEmpty()) return "Underflow";
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
}
let stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.pop()); // Output: 20
A Queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Queues are used in scenarios where order needs to be preserved, such as task scheduling and handling requests in web servers.
class Queue {
constructor() {
this.items = [];
}
enqueue(element) {
this.items.push(element);
}
dequeue() {
if (this.isEmpty()) return "Underflow";
return this.items.shift();
}
front() {
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
}
let queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
console.log(queue.dequeue()); // Output: 10
A Tree is a hierarchical data structure consisting of nodes, where each node has zero or more child nodes. The top node is called the root, and nodes with no children are called leaves. Trees are used to represent hierarchical relationships, such as file systems and organizational structures.
class TreeNode {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
insert(data) {
const newNode = new TreeNode(data);
if (this.root === null) {
this.root = newNode;
} else {
this._insertNode(this.root, newNode);
}
}
_insertNode(node, newNode) {
if (newNode.data < node.data) {
if (node.left === null) {
node.left = newNode;
} else {
this._insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this._insertNode(node.right, newNode);
}
}
}
}
A Binary Tree is a specific type of tree where each node has at most two children, referred to as the left child and the right child. Binary trees are the foundation for more advanced tree structures like binary search trees, AVL trees, and heaps.
function inOrder(node) {
if (node !== null) {
inOrder(node.left);
console.log(node.data);
inOrder(node.right);
}
}
let tree = new BinaryTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
inOrder(tree.root); // Output: 5 10 15
A Graph is a data structure consisting of a set of vertices (or nodes) and a set of edges that connect pairs of vertices. Graphs can be directed or undirected, weighted or unweighted, and are used to represent complex relationships between entities.
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(v1, v2) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
}
let graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addEdge('A', 'B');
console.log(graph.adjacencyList); // Output: { A: ['B'], B: ['A'] }
A Hash Table is a data structure that stores key-value pairs and provides efficient lookup, insertion, and deletion operations. Hash tables use a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
class HashTable {
constructor(size = 53) {
this.keyMap = new Array(size);
}
_hash(key) {
let total = 0;
let WEIRD_PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96;
total = (total * WEIRD_PRIME + value) % this.keyMap.length;
}
return total;
}
set(key, value) {
let index = this._hash(key);
if (!this.keyMap[index]) {
this.keyMap[index] = [];
}
this.keyMap[index].push([key, value]);
}
get(key) {
let index = this._hash(key);
if (this.keyMap[index]) {
for (let i = 0; i < this.keyMap[index].length; i++) {
if (this.keyMap[index][i][0] === key) {
return this.keyMap[index][i][1];
}
}
}
return undefined;
}
}
let ht = new HashTable();
ht.set('hello', 'world');
console.log(ht.get('hello')); // Output: world
Understanding these fundamental data structures and their terminology is crucial for any programmer aiming to master algorithms and optimize their code. Each data structure has its unique characteristics, advantages, and use cases, making them suitable for different types of problems. By leveraging the power of these data structures, you can enhance the efficiency and effectiveness of your JavaScript applications.