JavaScript Data Structures: Singly Linked List: Get

November, 2019

Intro

Last time, we learned how to shift / remove a node from the beginning of our Singly Linked List.

Today, we learn how to get any specific node by its index.

Current Code

We start with the code after we added push(), because we want to keep the code as simple as possible to understand. We need push() to add some nodes to the List.

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

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

  push(value) {
    const newNode = new Node(value);
    if (this.length > 0) {
      this.tail.next = newNode;
    } else {
      this.head = newNode;
    }
    this.tail = newNode;
    this.length += 1;
    return newNode;
  }
}

Thoughts

First, we should think about the constraints and possibilities:

If the index is negative or equal to or greater than the length of the List:

return null

Else:

start at the beginning of the List
go to the next node [index]-times
return this node

Examples:

index < 0: return null
index = 0: return head
index >= List.length: return null
remaining cases: go to head, go index-times to the next node & return this node

Differences:

return null if the List doesn’t have the desired node or go index-times to the next node

Implementation (Short version, DRY)

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

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

  push(value) {
    const newNode = new Node(value);
    if (this.length > 0) {
      this.tail.next = newNode;
    } else {
      this.head = newNode;
    }
    this.tail = newNode;
    this.length += 1;
    return newNode;
  }

  get(index) {
    // return null if index is negative or equal to or greater than the length of the List
    if (index < 0 || index >= this.length) {
      return null;
    } else {
      // start at the beginning of the List
      let currentNode = this.head;
      // keep track how many times we went to the next node
      let count = 0;

      // as long as the current count is smaller than the desired node's index
      while (count < index) {
        // set the next node as the currentNode
        currentNode = currentNode.next;
        // increase the count by 1
        count += 1;
      }

      // return this node
      return currentNode;
    }
  }
}

Result

Let’s have a look how to use the Singly Linked List’s get method and its results.

const newSLL = new SinglyLinkedList();

// show List, should be empty
console.log(newSLL);
// SinglyLinkedList { length: 0, head: null, tail: null }

// add three nodes
newSLL.push("0");
newSLL.push("1");
newSLL.push("2");

// there is no node with a negative index
console.log(newSLL.get(-1));
// null

// there is no node with that high of an index
console.log(newSLL.get(3));
// null

// show me the first node
console.log(newSLL.get(0));
// Node {
//   value: '0',
//   next: Node { value: '1', next: Node { value: '2', next: null } }
// }

// show me the second node
console.log(newSLL.get(1));
// Node { value: '1', next: Node { value: '2', next: null } }

// show me the third node
console.log(newSLL.get(2));
// Node { value: '2', next: null }

Next Part

We will implement how to give a specific node a new value. If you want to be notified, subscribe :)

Hi! I'm Michael 👋 I'm a problem solver and mentor. My goal is to build great products and help you to become a better developer.