Data Structures in JavaScript
Data structures are fundamental building blocks in computer science, and understanding them is crucial for writing efficient and organized code. JavaScript, while often perceived as a high-level language primarily focused on web development, provides the tools necessary to implement and work with various data structures. Two of the most foundational structures are arrays and linked lists. This article will explore both, comparing their characteristics, use cases, and implementations in JavaScript. We’ll see how their underlying structures affect their performance for different operations.
What is an Array?
In JavaScript, an array is a dynamic, ordered collection of elements. “Dynamic” means that the size of the array can grow or shrink as needed. “Ordered” means that each element has a specific index (position) starting from 0. Arrays in JavaScript are heterogeneous, meaning they can store elements of different data types (numbers, strings, objects, even other arrays) within the same array. Crucially, JavaScript arrays are implemented as objects under the hood.
Creating Arrays
There are several ways to create arrays:
Array Literal: The most common and concise way.
const myArray = [1, "hello", true, { name: "Alice" }];
console.log(myArray); // Output: [1, "hello", true, { name: "Alice" }]
// This creates an array named "myArray" with the elements 1, "hello", true, and the object.
const emptyArray = []; // Creates an empty array.
console.log(emptyArray); //output: []
//This create a variable called emptyArray, where its value is an empty array.
Array Constructor: Less common, but useful in specific cases.
const myArray = new Array(1, 2, 3);
console.log(myArray); // Output: [1, 2, 3]
// This creates an array named "myArray" with the elements 1, 2, and 3.
const sizedArray = new Array(5); // Creates an array with 5 empty slots.
console.log(sizedArray); // Output: [empty × 5] (or similar, depending on the environment)
//This creates a new array with 5 empty slots.
//The array is initialized with 5 elements, all set to undefined.
console.log(sizedArray.length); // Output: 5
//The array has the length of 5.
sizedArray[0] = "first";
console.log(sizedArray); //Output: ['first', empty × 4]
//We assign the string "first" into the first position in the array.
Accessing Array Elements
Elements are accessed using their index within square brackets:
const myArray = ["apple", "banana", "cherry"];
console.log(myArray[0]); // Output: "apple" (The first element, at index 0)
console.log(myArray[1]); // Output: "banana" (The second element, at index 1)
console.log(myArray[2]); // Output: "cherry" (The third element, at index 2)
console.log(myArray[3]); // Output: undefined (There's no element at index 3)
Common Array Methods
JavaScript arrays come with a rich set of built-in methods:
push() and pop(): Add/remove elements from the end of the array.
const myArray = [1, 2, 3];
myArray.push(4); // Add 4 to the end
console.log(myArray); // Output: [1, 2, 3, 4] (4 is added to the end)
const lastElement = myArray.pop(); // Remove the last element
console.log(lastElement); // Output: 4 (The removed element)
console.log(myArray); // Output: [1, 2, 3] (The array after removal)
shift() and unshift(): Add/remove elements from the beginning of the array. These operations are generally slower than push() and pop() because they require shifting all subsequent elements.
const myArray = [1, 2, 3];
myArray.push(4); // Add 4 to the end
console.log(myArray); // Output: [1, 2, 3, 4] (4 is added to the end)
const lastElement = myArray.pop(); // Remove the last element
console.log(lastElement); // Output: 4 (The removed element)
console.log(myArray); // Output: [1, 2, 3] (The array after removal)
splice(): A versatile method for adding, removing, and replacing elements at any position.
const myArray = [1, 2, 3];
myArray.push(4); // Add 4 to the end
console.log(myArray); // Output: [1, 2, 3, 4] (4 is added to the end)
const lastElement = myArray.pop(); // Remove the last element
console.log(lastElement); // Output: 4 (The removed element)
console.log(myArray); // Output: [1, 2, 3] (The array after removal)
slice(): Creates a new array containing a portion of the original array, without modifying the original.
const myArray = [1, 2, 3, 4, 5];
const newArray = myArray.slice(1, 4); // Elements from index 1 up to (but not including) 4
console.log(newArray); // Output: [2, 3, 4]
console.log(myArray); // Output: [1, 2, 3, 4, 5] (Original array unchanged)
length: A property (not a method) that gives the number of elements in the array.
const myArray = [1, 2, 3];
console.log(myArray.length); // Output: 3
indexOf() and lastIndexOf(): Find the index of a given element.
const myArray = ["apple", "banana", "cherry", "banana"];
console.log(myArray.indexOf("banana")); // Output: 1 (First occurrence)
console.log(myArray.lastIndexOf("banana")); // Output: 3 (Last occurrence)
console.log(myArray.indexOf("grape")); // Output: -1 (Not found)
forEach(), map(), filter(), reduce(): Higher-order functions for iterating and transforming arrays (covered extensively in functional programming).
const numbers = [1, 2, 3, 4, 5];
// forEach: Execute a function for each element
numbers.forEach(number => console.log(number * 2)); // Output: 2, 4, 6, 8, 10 (on separate lines)
// map: Create a new array by applying a function to each element
const squaredNumbers = numbers.map(number => number * number);
console.log(squaredNumbers); // Output: [1, 4, 9, 16, 25]
// filter: Create a new array with elements that pass a test
const evenNumbers = numbers.filter(number => number % 2 === 0);
console.log(evenNumbers); // Output: [2, 4]
// reduce: Reduce the array to a single value
const sum = numbers.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
console.log(sum); // Output: 15
Array Performance
Accessing by index: Very fast (O(1) — constant time). JavaScript can directly calculate the memory location of the element.
push() and pop(): Generally fast (O(1) – constant time), as they operate at the end.
shift() and unshift(): Slower (O(n) – linear time), as they require shifting all subsequent elements.
splice() (insertion/deletion in the middle): O(n) – linear time, as elements may need to be shifted.
Searching (indexOf, includes): O(n) – linear time in the worst case (element not found or at the end).
Linked Lists in JavaScript
What is a Linked List?
A linked list is a linear data structure, but unlike arrays, elements are not stored in contiguous memory locations. Instead, each element (called a node) contains a value and a pointer (reference) to the next node in the sequence. The first node is called the head, and the last node’s pointer points to null (or sometimes a special “tail” node).
Why Use a Linked List?
Linked lists excel in scenarios where frequent insertions and deletions are needed, especially at the beginning or in the middle of the list. Unlike arrays, these operations don’t require shifting other elements.
Implementing a Linked List in JavaScript
JavaScript doesn’t have a built-in linked list data structure. We need to implement it ourselves using objects and references. Here’s a basic implementation:
class Node {
constructor(data) {
this.data = data;
this.next = null; // Pointer to the next node, initially null
}
}
class LinkedList {
constructor() {
this.head = null; // Initially, the list is empty
this.size = 0; // Keep track the size
}
// Add a node to the end of the list
append(data) {
const newNode = new Node(data);
if (!this.head) {
// If the list is empty, the new node becomes the head
this.head = newNode;
} else {
// Traverse to the end of the list
let current = this.head;
while (current.next) {
current = current.next;
}
// Attach the new node to the last node
current.next = newNode;
}
this.size++;
}
// Add a node to the beginning of the list
prepend(data) {
const newNode = new Node(data);
newNode.next = this.head; // The new node points to the current head
this.head = newNode; // The new node becomes the head
this.size++;
}
// Insert a node at a specific index
insertAt(data, index) {
if (index < 0 || index > this.size) {
return false; // Invalid index
}
if (index === 0) {
this.prepend(data); // Inserting at the beginning
return true;
}
const newNode = new Node(data);
let current = this.head;
let previous = null;
let count = 0;
while (count < index) {
previous = current;
current = current.next;
count++;
}
newNode.next = current;
previous.next = newNode;
this.size++;
return true;
}
// Remove a node at a specific index
removeAt(index) {
if (index < 0 || index >= this.size) {
return null; // Invalid index
}
let current = this.head;
let previous = null;
let count = 0;
if (index === 0) {
this.head = current.next; // Remove the head
this.size--;
return current.data;
}
while (count < index) {
previous = current;
current = current.next;
count++;
}
previous.next = current.next; // Bypass the node to be removed
this.size--;
return current.data;
}
// Get the data at a specific index
getAt(index) {
if (index < 0 || index >= this.size) {
return null; // Invalid Index
}
let current = this.head;
let count = 0;
while (count < index) {
current = current.next;
count++
}
return current.data
}
// Print the list
printList() {
let current = this.head;
let str = "";
while (current) {
str += current.data + " -> ";
current = current.next;
}
str += "null";
console.log(str);
}
//get size of the linked list
getSize() {
return this.size;
}
}
// Example Usage
const myList = new LinkedList();
myList.append(10);
myList.append(20);
myList.prepend(5);
myList.insertAt(15, 2);
myList.printList(); // Output: 5 -> 10 -> 15 -> 20 -> null
console.log(myList.getSize()); // Output: 4
console.log("Removed data:", myList.removeAt(1)); // Output: Removed data: 10
myList.printList(); // Output: 5 -> 15 -> 20 -> null
console.log(myList.getAt(1)); // Output: 15
console.log(myList.getSize()); // Output: 3
Linked List Performance
- Accessing by index: O(n) — linear time. You need to traverse the list from the head to reach the desired index.
- Insertion/Deletion at the beginning: O(1) — constant time. You only need to update the head pointer.
- Insertion/Deletion at the end: O(n) — linear time (in the worst case, you have to traverse the entire list to find the last node). This can be improved to O(1) if you maintain a separate tail pointer.
- Insertion/Deletion in the middle: O(n) — linear time (you need to traverse to the insertion/deletion point). However, once you have a reference to the node before the insertion/deletion point, the actual insertion/deletion is O(1). This is a key advantage over arrays.
- Searching: O(n) — linear time.
Arrays and linked lists are fundamental data structures with distinct strengths and weaknesses.
- Arrays are excellent for scenarios where you need fast access to elements by index and where the size of the data is known beforehand or changes infrequently. They are the default choice for many situations in JavaScript due to their simplicity and built-in methods.
- Linked Lists shine when frequent insertions and deletions are required, particularly at the beginning or middle of the list. They are less efficient for random access but offer flexibility in managing dynamically sized collections. While not built-in, they can be readily implemented.
As a Developer, understanding the trade-offs between these two data structures is essential for choosing the right tool for the job and optimizing the performance of your code. Knowing when to consider a linked list, even though it requires custom implementation, can significantly impact the efficiency of certain algorithms. Choosing the right data structure can be the difference between a sluggish application and a highly responsive one.
Arrays and Linked Lists was originally published in CarlosRojasDev on Medium, where people are continuing the conversation by highlighting and responding to this story.