Data Structures With JavaScript: Singly-Linked List and Doubly-Linked List

This article explores singly and doubly linked lists, two fundamental data structures in computer science. Often misunderstood, these structures are best understood through a relatable analogy: a scavenger hunt.

Understanding Singly-Linked Lists

A singly-linked list is a sequence of interconnected nodes. Each node holds data and a pointer referencing the next node in the sequence. This mirrors a scavenger hunt: each clue (node) contains a message (data) and instructions (pointer) leading to the next clue. The entire sequence of clues forms the complete hunt.

Singly-Linked List Operations

We'll examine operations for both the Node and SinglyList (or, in our case, DoublyList) constructors.

• Node: A basic building block containing data.
• DoublyList:
  • _length: Tracks the number of nodes.
  • head: Points to the first node.
  • tail: Points to the last node (a key difference from singly-linked lists).
  • add(value): Adds a new node.
  • searchNodeAt(position): Finds a node at a specific index.
  • remove(position): Deletes a node at a specific index.

Doubly-Linked List Implementation

Let's implement a DoublyList in JavaScript.

First, the Node constructor:

class Node {
  constructor(value) {
    this.data = value;
    this.previous = null; // Pointer to the previous node
    this.next = null;     // Pointer to the next node
  }
}

The DoublyList constructor:

class DoublyList {
  constructor() {
    this._length = 0;
    this.head = null;
    this.tail = null;
  }
}

Doubly-Linked List Methods

Here are implementations of add(value), searchNodeAt(position), and remove(position), modified for bidirectional traversal.

add(value):

add(value) {
  const node = new Node(value);
  if (this._length) {
    this.tail.next = node;
    node.previous = this.tail;
    this.tail = node;
  } else {
    this.head = node;
    this.tail = node;
  }
  this._length  ;
  return node;
}

searchNodeAt(position): (Identical to the singly-linked list version)

searchNodeAt(position) {
  // ... (Implementation remains the same) ...
}

remove(position):

remove(position) {
  // ... (Implementation is more complex, handling four cases: invalid position, removing head, removing tail, removing a middle node.  Refer to the original article for the detailed implementation.) ...
}

Conclusion

This article provided a clear explanation of singly and doubly linked lists, using the scavenger hunt analogy. The provided JavaScript code demonstrates the implementation of a doubly-linked list, highlighting the key differences and complexities compared to a singly-linked list. Remember to experiment with the code to solidify your understanding.

The above is the detailed content of Data Structures With JavaScript: Singly-Linked List and Doubly-Linked List. For more information, please follow other related articles on the PHP Chinese website!