Linear Data Structures: Linked Lists, Stacks, and Queues in JS

As a programmer, it‘s essential to have a solid grasp of data structures. They provide a way of organizing and storing data that enables efficient access and modification. In this in-depth guide, we‘ll explore three fundamental linear data structures: linked lists, stacks, and queues.

What are Linear Data Structures?

Before diving into the specifics of linked lists, stacks, and queues, let‘s clarify what we mean by "linear" data structures. In a linear data structure, data elements are arranged sequentially or linearly where each element is attached to its previous and next adjacent elements. This differs from non-linear data structures like trees and graphs where each element can be attached to two or more other elements.

Some key characteristics of linear data structures:

• Elements can be traversed in a single run
• Element are stored in a sequential order
• There are two ends (front/back, top/bottom, head/tail)
• Basic operations are insertion, deletion, and search

Linear data structures are easy to implement and very efficient for certain use cases. Let‘s examine three commonly used linear data structures in JavaScript:

Linked Lists

A linked list is a linear data structure in which elements are stored in nodes, and each node points to the next one forming a chain-like structure. The head node points to the first node, and the final node points to null indicating the end of the list.

There are two main types of linked lists:

1. Singly Linked Lists – Each node only holds a reference to the next node. Traversal can only be done in one direction from head to tail.

2. Doubly Linked Lists – In addition to a reference to the next node, each node also holds a reference to the previous node. This allows traversal in both directions.

Some common operations performed on linked lists include:

• Insertion – Adding a new node at the head, tail, or middle of the list
• Deletion – Removing a node from the head, tail, or middle of the list
• Search – Finding a node that contains a specific value
• Access – Accessing a node at a specific position

The time complexity for these operations is as follows:

• Insertion/Deletion at head or tail: O(1)
• Insertion/Deletion in middle: O(n)
• Search: O(n)
• Access: O(n)

Linked lists have constant time O(1) insertion and deletion at the head and tail since you can directly change the head/tail pointers without traversing the list. However, accessing, searching, and modifying elements in the middle requires traversing, which takes linear time O(n) in the worst case.

Some advantages of linked lists:

• Dynamic size – Linked lists can grow and shrink as needed
• Efficient insertion and deletion – O(1) time complexity for head and tail operations
• No fixed size limitation – Unlike arrays, you don‘t need to specify capacity

Disadvantages of linked lists:

• No random access – You can‘t directly access elements by index like in an array
• Extra memory – Linked lists require extra memory for storing node pointers
• Not cache-friendly – Elements are not contiguous in memory, not good for locality of reference

Some common use cases for linked lists:

• Implementing stacks and queues
• Creating circular lists
• Representing sparse matrices
• Performing arithmetic operations on long integers
• Undo functionality in photo editors/word processors

Here‘s a basic implementation of a singly linked list in JavaScript:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Add node to end of list
  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  // Remove node from end of list
  pop() {
    if (!this.head) return undefined;
    let current = this.head;
    let newTail = current;
    while (current.next) {
      newTail = current;
      current = current.next;
    }
    this.tail = newTail;
    this.tail.next = null;
    this.length--;
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return current.value;
  }

  // Add node to beginning of list  
  prepend(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
  }
}

This linked list class allows you to append elements to the end, remove elements from the end with pop, and add elements to the beginning with prepend. You can build out additional functionality like inserting/deleting at a specific position, searching for a value, reversing the list, and more.

Stacks

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. Think of it like a stack of plates – you can only add or remove plates from the top of the stack.

The two primary operations for a stack are:

1. Push – Adds an element to the top of the stack
2. Pop – Removes the top element from the stack

Some other common stack operations:

• Peek – Returns the top element without removing it
• IsEmpty – Checks if the stack is empty
• Size – Returns the number of elements in the stack
• Clear – Removes all elements from the stack

All of these operations have O(1) time complexity since you‘re always working with the element at the top of the stack.

Advantages of stacks:

• Fast operations – All stack operations take O(1) time
• Simple to implement – Can be easily implemented using an array or linked list
• Used for solving many problems – Stacks are used in a variety of algorithms

Some common use cases for stacks:

• Function call stack in programming languages
• Parsing expressions (infix to postfix)
• Backtracking algorithms
• Undo/Redo functionality
• Depth-First Search on a graph

Here‘s an implementation of a stack in JavaScript using an array:

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

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) return "Stack is empty";
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) return "Stack is empty";
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }

  print() {
    console.log(this.items.toString());
  }
}

You can also implement a stack using a linked list which may be more efficient for certain use cases.

Queues

A queue is another linear data structure that follows the First In First Out (FIFO) principle. It‘s similar to a line at a ticket counter – the first person to join the line is the first one to get served.

The two main operations for a queue are:

1. Enqueue – Adds an element to the back of the queue
2. Dequeue – Removes the element at the front of the queue

Additional common queue operations:

• Front – Returns the front element without removing it
• IsEmpty – Checks if the queue is empty
• Size – Returns the number of elements in the queue
• Clear – Removes all elements from the queue

Similar to stacks, these operations have O(1) time complexity since you‘re working with the front and back of the queue.

Benefits of queues:

• Fast operations – Enqueue, dequeue, front, isEmpty all take O(1) time
• Ordering is preserved – FIFO ensures ordering based on arrival time
• Common in real-world scenarios – Many real-life processes follow a queue structure

Typical applications of queues:

• CPU scheduling and Disk Scheduling
• Asynchronous data transfer (IO Buffers)
• Breadth-First Search graph traversal
• Cache implementation
• Applying operations in the correct sequence

Here‘s a sample queue implementation in JavaScript using an array:

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

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) return "Queue is empty";
    return this.items.shift();
  }

  front() {
    if (this.isEmpty()) return "Queue is empty";
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }

  print() {
    console.log(this.items.toString());
  }
}

A queue can also be implemented using a linked list for potentially better performance.

Comparing Linked Lists, Stacks and Queues

While linked lists, stacks, and queues are all linear data structures, they have some key differences:

Structure:

• Linked lists consist of nodes with data and next/prev pointers
• Stacks and queues can be implemented using an array or linked list

Element ordering and access:

• Linked lists – No inherent ordering, direct access not possible
• Stacks – LIFO, access restricted to most recently added element
• Queues – FIFO, access restricted to least recently added element

Main operations and time complexity:

• Linked lists – Insert/delete from head is O(1), search is O(n)
• Stacks – Push and pop are both O(1)
• Queues – Enqueue and dequeue are both O(1)

Typical use cases:

• Linked lists – Implementing stacks/queues, arithmetic operations, undo/redo
• Stacks – Function calls, parsing, tree/graph traversal
• Queues – Scheduling, asynchronous data transfer, cache, BFS

So when should you use each data structure? It depends on the specific needs of your application:

• Use a linked list if you need fast insertion/deletion at the ends and don‘t need direct element access
• Use a stack when you need LIFO ordering and fast push/pop operations
• Use a queue when FIFO ordering is needed and fast enqueue/dequeue is required

Conclusion

In this guide, we covered the fundamentals of three linear data structures in JavaScript – linked lists, stacks, and queues. We looked at how each one is structured, what operations they support, the time complexity of those operations, and common use cases.

To recap some key points:

• Linear data structures organize data sequentially with each element attached to its neighbors
• Linked lists consist of nodes storing data and next/prev pointers allowing for efficient insertion/deletion
• Stacks follow LIFO ordering and have O(1) push and pop operations
• Queues use FIFO ordering and have O(1) enqueue and dequeue operations
• The choice of data structure depends on your application‘s specific requirements

Linked lists, stacks and queues are essential tools in a programmer‘s toolkit. Having a solid understanding of these data structures, their tradeoffs, and how to implement them is crucial for writing efficient, well-structured code. Be sure to practice implementing them and consider how they can be applied to solve problems you encounter.

I hope this in-depth look at linked lists, stacks, and queues has been helpful! Let me know if you have any other questions.