Traversing Linked Lists In Javascript

A linked list is a data structure, that like an array can store elements. The elements are stored sequentially and can grow as needed. Unlike arrays though, the elements are not contiguous. We will review linked lists and how it can be used to traverse data stored in elements.

Array vs. Linked List

Arrays store elements in contiguous memory locations with an assigned index (starting with 0). This allows for faster data retrieval with the use of indexes. A linked list does not have the same structure. They use a reference tag with additional information about the elements.

Figure 1. A typical array data structure

A linked list does not support random access, whereas an array does. With arrays, you can select an element based on its index at any location within the array. A linked list uses pointers to reference the next element, but to get to one element you have to start from the first element.

Linked lists can grow dynamically and support ease of insertion and deletion of elements. Arrays can be faster though, because they don’t take as long to traverse through all the elements since you can use indexes to find them. While that is the case for querying large data sets, a linked list can be useful when it comes to memory usage. This is because with a linked list, the size is not pre-defined. That means that the linked list can increase or decrease in size during the run-time of a program.

Defining A Node

We first define a class called a Node. It has two properties:

• element
• next

Figure 2. Linked list data structure

The element stores the data of a node while next contains the pointer to the next node, initialized to the null. The following is a sample code (in Javascript).

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

Here is an example of a linked list with 3 nodes:

var head; 
class Node {
  constructor(a)
  {
   this.data = a;
   this.next = null;
  } // Constructor
 }
  var head = new Node(1);
  var second = new Node(2);
  var third = new Node(3);
  head.next = second; 
  second.next = third; 

Three nodes have been allocated dynamically, as variables: head (node 1),
second (node 2) and third (node 3).

The line head.next = second, links the first node to the second node.

The next line second.next = third, links the second node to the third node.

You cannot get to the third node without passing through the second node, which requires starting from the head (first node).

If there is no data in the next element after the last, it points to Null, which is the end of the list.

Traversing Nodes

The next example is how to traverse nodes in a linked list. We are going to traverse the list and print data stored in each of the elements. Building from the previous example, we will now use 4 nodes.

var head;
class Node {
  constructor(val) {
    this.data = val;
    this.next = null;
  }
}
function printListData()
{
   var n = head;
   while (n != null) {
      document.write(n.data + " ");
      n = n.next;
    }
}
   var head = new Node(1);
   var second = new Node(2);
   var third = new Node(3);
   var fourth = new Node(4);
   head.next = second; 
   second.next = third; 
   third.next = fourth;
printListData();

To traverse the linked list, we use a while statement to go from head to the last node (fourth). The statement will continue to traverse the linked list until it reaches a value that is null.

We also print the result of the data from each element using a function called printListData().

Here is the code tested on JS.do with the output result.

Figure 3. The code with the results using JS.do.

You should get the result:

1 2 3 4

You can never start from 3 to get to 1 to get to 4. It will always follow a sequence using pointers to the next node.

Synopsis

Linked list traversal allows us to get from the first node (head) to the last node and eventually the Null value. We cannot traverse the linked list from any random node, it must always start from the head. Notice that there is also no recursion, meaning you cannot go back to a previous node.

The major drawback of traversing a linked list is that it takes much more time, compared to having an index to find an element. Sometimes an application can use a linked list for enforcing a certain sequence of elements, but that is up to the developer.