Practical Examples Of Common Data Structures In Javascript

Practical Examples Of Common Data Structures In Javascript

Many programmers have a thing or two to say about data structures. A vast majority of experienced programmers are confident in having conversations about this topic, while the less experienced programmers dread the mention of data structures, especially when algorithms get into the mix. If you're reading this article, I suppose you're one of those people who just can't seem to get their heads around this seemingly complex subject; or maybe you have encountered way too many programming problems that you couldn't solve because you didn't understand how the data was structured. If so, this article is for you. We will take a deep dive into the world of data structures, understand what they are all about, and learn how to implement them using JavaScript.

UNDERSTANDING DATA STRUCTURES

Data structures are a way of structuring and keeping data in a computer's memory in an organized fashion so that it can be accessed and changed quickly and easily.

By organizing data in a logical and structured way, data structures make it easier for computers to process and manipulate the data and for humans to understand and interpret the data. This is especially important when dealing with large amounts of data, as unorganized data can be difficult to work with and understand. Here are some instances of how data structures are utilized:

  • Storing and organizing large amounts of data: Large amounts of data, such as records in a database or items in an online store, are frequently stored and organized using data structures. By choosing the right data structure for your specific types of data and operations, you can greatly improve the efficiency of your system.

  • Searching for specific pieces of data: Data structures can be used to store data in a way that makes it simple to search for particular pieces of data. For example, a hash table can be used to store data in a way that allows for a fast lookup of values by key. A binary search tree is another data structure that can be used for the efficient searching of data.

  • Sorting data: It is possible to arrange data in a particular order with the help of data structures, for instance, to list names alphabetically or numbers from least to largest. Different data structures are ideal for different sorts of sorting operations, and making the right selection of data structures can make a significant difference in the effectiveness of the sort.

  • Implementing algorithms: Data structures are often used as the building blocks for implementing algorithms. For example, a stack can be used to implement a depth-first search algorithm, and a queue can be used to implement a breadth-first search algorithm.

  • Modeling real-world systems: Data structures can be used to model real-world systems and relationships. For example, a tree data structure can be used to represent a family tree, and a graph data structure can be used to represent a network of roads or a social network.

IMPLEMENTING COMMON DATA STRUCTURES WITH JAVASCRIPT

ARRAYS

Arrays are the most basic data structure. It allows for the storage of elements side by side in the computer's memory. Each element of an array has to be of the same type. They are immutable, which means they have a fixed length that cannot be changed.

Arrays in Javascript have a zero-based indexing system, meaning the first spot in memory is labeled "zero," and every spot following that increases in numerical order. To access the data stored in an array, you can call upon their respective indexes. For instance, say you have an array called "arr"; the first element can be accessed with "arr[0]," the second element with "arr[1]," and so on. There are several operations you can do with an array, including accessing elements.

ADDING ELEMENTS

To add an element to the end of an array, use the push method: arr.push(element).

// Add an element to the end of the array
arr.push('grape');
console.log(arr); // Outputs: ["apple", "banana", "orange", "grape"]
  • To add an element to the beginning of an array, use the unshift method: arr.unshift(element).
// Add an element to the beginning of the array
arr.unshift('strawberry');
console.log(arr); // Outputs: ["strawberry", "apple", "banana", "orange", "grape"]
  • You can use the splice method to add an element at a specific index in the array: arr.splice(index, 0, element).
// Add an element at a specific index in the array
arr.splice(2, 0, 'mango');
console.log(arr); // Outputs: ["strawberry", "apple", "mango", "banana", "orange", "grape"]

REMOVING ELEMENTS

  • You can use the pop method to remove the last element in the array: arr.pop().
// Remove the last element in the array
arr.pop();
console.log(arr); // Outputs: ["strawberry", "apple", "mango", "banana", "orange"]
  • You can use the shift method to remove the first element from the array: arr.shift().
// Remove the first element in the array
arr.shift();
console.log(arr); // Outputs: ["apple", "mango", "banana", "orange"]
  • Use the splice method to remove an element at a specific index in the array: arr.splice(index, 1).
// Remove an element at a specific index in the array
arr.splice(1, 1);
console.log(arr); // Outputs: ["apple", "banana", "orange"]

ITERATING OVER ELEMENTS

You can easily go through each element of an array using a for loop or a while loop

//Using a for loop
let arr = [1, 2, 3, 4, 5];

for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}

//Using a while loop
let arr = [1, 2, 3, 4, 5];

let i = 0;
while (i < arr.length) {
  console.log(arr[i]);
  i++;
}

SORTING ELEMENTS

You can arrange elements in an array by using the sort function. Typically, it will arrange the elements in numerical order for numbers or alphabetical order for strings. To decide how the elements should be sorted, you can offer a comparison function if necessary.

// Sort the elements in the array
arr.sort();
console.log(arr); // Outputs: ["apple", "banana", "orange"]

LINKED LISTS

Linked lists are another type of data structure used in computer programming. This structure stores a sequence of elements like arrays, but with a few key differences. One of which is that linked lists are dynamic, so elements don't necessarily have to be placed next to each other. Instead, linked lists are made up of individual nodes, each having two components (the data and a pointer). The pointer for each node is designed to point to the next element in the list.

Linked List

As shown in the image above, a linked list is a linear data structure in which each element is a separate object linked to the next element by a reference. Linked lists are not index-based, so you cannot access elements in a linked list by their index. Instead, you must follow the links between elements to access the data.

Some common operations that can be performed on a linked list are as follows:

TRAVERSAL

To traverse a linked list, you can start at the head of the list and follow the next references of each node until you reach the end of the list. Here is an example of how you might traverse a linked list in JavaScript:

let current = list.head;
while (current) {
  console.log(current.data);
  current = current.next;
}
//This will print the data of each node in the list to the console.

INSERTION

To insert a new node into a linked list, you can use the add method from the previous example to add the node to the end of the list. However, you can also insert a node at a specific position in the list by using the previous and next properties of the nodes. Here is an example of how you might insert a new node at the beginning of the list:

let node = new Node(data);
node.next = list.head;
list.head = node;
list.size++;
//This creates a new node with the given data, sets its next property to the current head of the list, and sets the head of the list to the new node.

DELETION

To remove a node from a linked list, you can make the most of the previous and next attributes of the nodes to remove the node from the list. As an illustration, here is an example of how you might delete the first node in the list:

list.head = list.head.next;
list.size--;

STACKS

A stack is a data structure that is ordered by piling elements on top of one another, allowing it to operate on a first-in, last-out (FILO) basis. The push method is used to add elements to a stack; the pop method is used to remove elements from a stack; and the peek method is used to search through the list and find specific elements. One vital use of stacks is to reverse the elements in them so that the last elements come out first.

Here is an example of a stack implemented in JavaScript:

class Stack {
  constructor() {
    this.items = [];
  }

  // Add an element to the top of the stack
  push(element) {
    this.items.push(element);
  }

  // Remove and return the top element from the stack
  pop() {
    return this.items.pop();
  }

  // Return the top element from the stack without removing it
  peek() {
    return this.items[this.items.length - 1];
  }
}

let stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // Outputs: 3
console.log(stack.peek()); // Outputs: 2

In the preceding example, the Stack class has three methods: push, pop, and peek. The push method adds an element to the top of the stack, the pop method removes and returns the top element from the stack, and the peek method returns the top element from the stack without removing it.

QUEUES

Queues are yet another vertically arranged linear data structure, similar to stacks. However, queues work according to 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 often implemented using arrays or linked lists.

Queue

The peek command searches through the queue for existing elements; the enqueue command adds an element to the queue; and the dequeue command removes elements from the data structure.

Here's an example of a queue implemented in JavaScript using an array:

class Queue {
  constructor() {
    this.items = [];
  }

  // Add an element to the end of the queue
  enqueue(element) {
    this.items.push(element);
  }

  // Remove and return the first element from the queue
  dequeue() {
    return this.items.shift();
  }
// Return the first element from the queue without removing it
peek() {
    return this.items[0];
  }
}

let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue()); // Outputs: 1
console.log(queue.peek()); // Outputs: 2

In this example, the queue class has three methods: enqueue, dequeue, and peek. The enqueue method adds an element to the end of the queue, the dequeue method removes and returns the first element from the queue, and the peek method returns the first element from the queue without removing it.

Stacks are great for operations that involve reversing the order of the data, like undo/redo or reading expressions. Queues are beneficial for operations that call for processing the data in the same order it was received, such as printing jobs or managing events.

TREES

Trees are a common data structure in computer science that represent hierarchical relationships. They are organized in nodes from top to bottom and linked together with pointers or references. Each node in a tree contains a value and a list of references to other nodes, which are referred to as its children. The references are unique and do not point back to the root node.

Trees are a great tool for clearly displaying hierarchical connections in different areas, like file systems, network systems, and decision trees. The tree data structure is ideal for many of these connections and is used for displaying a diverse range of information. Some common operations performed on trees include searching, insertion, and deletion. Trees can also be traversed in various ways, such as in-order, pre-order, and post-order.

Here's an example of a tree data structure in JavaScript:

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}

class Tree {
  constructor(rootValue) {
    this.root = new TreeNode(rootValue);
  }

  search(value) {
    let queue = [this.root];

    while (queue.length > 0) {
      let current = queue.shift();

      if (current.value === value) {
        return current;
      }

      queue.push(...current.children);
    }

    return null;
  }

  insert(value, parentValue) {
    let parent = this.search(parentValue);

    if (parent) {
      parent.children.push(new TreeNode(value));
} else {
     throw new Error('Parent node not found');
    }
  }
}

This implementation defines a TreeNode class with a value and an array of children. The Tree class, which has a root node, provides methods for searching for a node with a specific value and inserting a new node with a given value as a child of a parent node with a specific value.

To use this implementation, you can create a new tree and add nodes to it like this:

let tree = new Tree('A');
tree.insert('B', 'A');
tree.insert('C', 'A');
tree.insert('D', 'B');
tree.insert('E', 'B');

CONCLUSION

Understanding data structures is an important part of becoming a competent programmer, and JavaScript provides a flexible language for implementing them. Knowing the fundamentals of arrays, linked lists, stacks, queues, and trees allows you to write more efficient and effective problem-solving algorithms in your code. Remember that practice makes perfect, so continue to experiment and refine your approach.