0xCODE
Published in

0xCODE

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.

--

--

--

Essays and Articles on software engineering, development and computer science.

Recommended from Medium

Create a PokeDex with Vanilla JS

Using GameMaker and Electron together: A Practical Introduction

Learn GatsbyJS by creating a tourism site -20

OSB-380001 Internal Server Error

Build a Dog Classifier with React and TensorFlow JS in Minutes

Atomic Design and Our Component Library

6 Cool APIs for Your Next JavaScript Project

Circle Ci configuration — React js/Angular js

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Vincent Tabora

Vincent Tabora

Editor HD-PRO, DevOps Trusterras (Cybersecurity, Blockchain, Software Development, Engineering, Photography, Technology)

More from Medium

learning JS weekly updates[3/17/22]

Leetcode: Two Sum (JS)

Doubly Linked List in Javascript (Data Structures)

Doubly Linked List Implementation using JavaScript