As a web developer, it is important to have a strong understanding of data structures. Data structures are used to organize, store, and retrieve data. They are the foundation upon which algorithms are built. There are many different types of data structures, but in this blog post, we will focus on seven essential data structures that every web developer should know.
Data Structure 1: Arrays
Arrays are one of the most basic data structures. An array is simply a collection of values of the same type. The values can be accessed by their index, which is their position in the array. Arrays are declared using square brackets, and values are separated by commas. For example:
const arr = [1, 2, 3]; console.log(arr[1]); // 2
Array as a Stack:
Arrays can be used as stacks. Arrays can be used as stacks because they maintain the order of insertion. This means that the last element added to the array will be the first element removed (LIFO).
const stackExmaple = () => {
const stack = [];
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
console.log(stack);
stack.pop();
stack.pop();
console.log(stack);
};
stackExmaple();
Array as a queue:
Arrays can also be used as queues. In a queue, elements are added to the end of the array and removed from the front. This is called a First-In-First-Out (FIFO) structure.
const queueExample = () => {
const queue = [];
queue.push(1);
queue.push(2);
queue.push(3);
queue.push(4);
queue.push(5);
console.log(queue);
queue.shift();
queue.shift();
console.log(queue);
}
queueExample();
Data Structure 2: Maps
Objects in JavaScript
The Object type represents one of JavaScript’s data types and is used to store various keyed collections and more complex entities. Objects can be created using the Object() constructor or the object initializer / literal syntax({}).
Nearly all objects in JavaScript are instances of Object; a typical object inherits properties (including methods) from Object.prototype, although these properties may be shadowed (a.k.a. overridden). However, an Object may be deliberately created for which this is not true (e.g. by Object.create(null)), or it may be altered so that this is no longer true (e.g. with Object.setPrototypeOf).
Changes to the Object prototype object are seen by all objects through prototype chaining, unless the properties and methods subject to those changes are overridden further along the prototype chain. This provides a very powerful although potentially dangerous mechanism to override or extend object behavior.
Objects are important in web development because they allow developers to store data in a structured way and access it easily. They also provide a way to create custom functionality that can be reused across different web applications and components.
const obj = {
name: "John",
age: 30,
city: "New York"
}
Map Object
A map is a data structure that stores key-value pairs. A map is different than an object because a map can store keys of any type, whereas an object can only store keys of the type string. In general, the Map object may be more suitable for applications that require a large number of key-value pairs, or that require complex keys (such as objects or arrays).
var map = new Map(); map.set([1,2,3], 'foo'); console.log(map.get([1,2,3])); // 'foo'
Data Structure 3: Linked List.
A linked list is a linear data structure in which elements are not stored in contiguous memory locations. It consists of a group of nodes, each of which has its own data and address to the next node. In an array, the elements are indexed, so you can instantly get to an element, but in a linked list, you have to start with the head and work your way through until you get to the desired element. The advantage of the linked list is that insertion and deletion are easier than with an array, because the elements in an array are stored in a consecutive location. Linked lists also have efficient memory consumption, because the size of the linked list can grow or shrink according to our requirements.
Linked List Tradeoffs:
There is no one method that is suited for all circumstances in computer programming and design. Depending on the situation, a linked list data structure might work well or cause problems. Some common tradeoffs involving linked list structures are listed below.
Linked lists have several advantages over dynamic arrays, including faster insertion and deletion of elements. With a reference to the desired node, insertion or deletion can be done in constant time. Without this reference, it would be a O(n) operation. Additionally, dynamic arrays can become fragmented over time, which impacts the performance of iteration.
Use Cases:
Linked lists are often used to implement stacks and queues. They can also be used to implement graphs and trees.
Here is a basic Linked List in JavaScript:
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor(value) {
this.head = {
value: value,
next: null,
};
this.tail = this.head;
this.length = 1;
}
append(value) {
const newNode = new Node(value);
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
prepend(value) {
const newNode = new Node(value);
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
printList() {
const array = [];
let currentNode = this.head;
while (currentNode !== null) {
array.push(currentNode.value);
currentNode = currentNode.next;
}
return array;
}
insert(index, value) {
//check params
if (index >= this.length) {
return this.append(value);
}
const newNode = new Node(value);
const leader = this.traverseToIndex(index - 1);
const holdingPointer = leader.next;
leader.next = newNode;
newNode.next = holdingPointer;
this.length++;
return this.printList();
}
traverseToIndex(index) {
//check params
let counter = 0;
let currentNode = this.head;
while (counter !== index) {
currentNode = currentNode.next;
counter++;
}
return currentNode;
}
remove(index) {
//check params
const leader = this.traverseToIndex(index - 1);
const unwantedNode = leader.next;
leader.next = unwantedNode.next;
this.length--;
return this.printList();
}
}
Other Linked List problems: Add Two Numbers
Data Structure 4: Trees:
Probably one of the most sought after data structures in computer science. A tree is a data structure that represents a hierarchical tree structure. It is composed of nodes, and each node can have one or more child nodes. The root node is the top node in the tree and does not have a parent node. Trees are useful for storing data that can be logically organized in a hierarchical manner.
There are many types of trees. Some examples.
1.) Binary Tree
2.) Binary Search Tree
3.) AVL Tree
4.) Balanced tree
5.) Red black tree
6.) 2-3 tree
7.) N-ary tree
If you’re a beginner we recommend focusing on 1 & 2 only. To implement a binary tree, read our post here
Data Structure 5: Graphs:
A graph data structure consists of a finite set of vertices, along with a set of unordered pairs of these vertices for an undirected graph, or a set of ordered pairs for a directed graph. These pairs are known as edges, and for a directed graph they may also be called arrows or arcs. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references. A graph data structure may also associate an edge value with each edge, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).
There are two common types of graphs:
Undirected Graphs: A graph in which edges have no direction. This means that each edge can be traversed in both directions
Directed Graphs: A directed graph is a graph in which edges have a direction. This means that each edge can only be traversed in one direction
Use Cases
– To represent a network of roads or a computer network
– To represent a social network
– To represent a database of relationships
Graph in JavaScript:
var underectedGraph = {
"a": ["c"],
"b": ["c", "e"],
"c": ["a", "b", "d", "e"],
"d": ["c"],
"e": ["c", "b"],
"f": []
}
// code an directed graph in JavaScript
var directedGraph = {
"a": ["c"],
"b": ["c", "e"],
"c": ["d"],
"d": ["c"],
"e": ["c"],
"f": []
}
For more resources check out our blog and connect with us on Twitter.