DEV Community

DavidNNussbaum
DavidNNussbaum

Posted on

Building a Singly Linked List in JavaScript

Linked Lists are a linear collection of data elements whose order is not given by their physical placement in memory. Instead, it is a collection of nodes each one pointing to the next one which together represent a sequence. Each node consists of a pointer to the next node and a value that it contains. This value could be any type of data type. A singly linked list is unidirectional. The first node is called the head and the last node is called the tail and it points to null. Linked Lists represent a time saving over arrays in that with an array after the previously set size is reached an area of double the size is established in memory. In addition, when inserting or deleting items anywhere but at the end, all of the indices from the insertion point and onward must be changed. Both of these steps are time consuming for an array. Linked lists have an advantage over hash tables in that linked lists are ordered. A disadvantage that Linked Lists have compared to arrays is that the data is scattered in different memory locations and takes up more memory due to the pointers. Another disadvantage is that without indices, the nodes must be accessed sequentially.

In building the Linked List, it has nodes, the first one being the head and the last one being the tail. Each node has a value and a pointer which in the case of the tail points to null. We first create a class with a constructor that has a value as its parameter and has this.head containing a value which equals the argument value and the pointer (called β€œnext”) equaling null since at the outset the head is also the tail. The length is initialized as 1. In order to be able to add a node, the append method is created. This method creates a variable called newNode which represents the new node and has a value of the argument value and next (the pointer) with a value of null (since this is the new tail). The tail is now updated to be the new node, and the length of the Linked List is increased by 1.

To demonstrate this, a new Linked List will be built with node values of 30, 18, and 22. If one wants to further build the Linked List, then it would involve additional methods which should be covered in a future posting.

Image description

The results in the terminal are as follows:

Image description

Thanks for reading!

Top comments (0)