DEV Community

miku86
miku86

Posted on

JavaScript Data Structures: Singly Linked List: Get

#webdev #javascript #beginners #tutorial

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; } }
Enter fullscreen mode Exit fullscreen mode

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; } } }
Enter fullscreen mode Exit fullscreen mode

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 }
Enter fullscreen mode Exit fullscreen mode

Next Part

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

Questions:

  • Any ideas how to improve the post or code?
  • Any specific questions?

Top comments (0)