LinkedList and Javascript

As I continue my journey to become a software engineer after graduating from The Flatiron School Software Engineering Program and keep on learning new things, I ran into LinkedList.

A LinkedList is a linear data structure similar to arrays in that aspect, with the difference that elements are not saved in contiguous space in memory but instead, each element on the list points to the next, which makes it different than an array. Elements on the list are commonly called nodes. These nodes are composed of a value and a pointer to the next element, therefore, needing more space in memory than elements in an array.

Since the nodes of a LinkedList can be located anywhere in memory, it makes insertion and deletion of the nodes very easy compared to elements in an array. Let’s have a simple visualization of how elements are added and removed from a LinkedList.

Deleting from a LinkedList

Adding to a LinkedList

It also means that to randomly access the data is not allowed nor the use of indices. In order to access an element on the LinkedList, we have to iterate from the beginning of the list until we find what we want.

Types of LinkedList

• Singly LinkedList, each node has a value and a pointer to the next node. The one this post is focusing on.
• Doubly LinkedList, each node has a value and two pointers, one to the next node and another one to the previous node.
• Circular LinkedList, it’s similar to the singly LinkedList with the difference that the last node points to the first one.

Implementing a Singly LinkedList in javascript

JavaScript does not provide us with a LinkedList class to use like other programming languages, such as Java do, therefore, if we want to use a link list we have to implement it ourselves. The following implementation uses two classes a LinkedList class and a ListNode,

Knowing that a node in a list is compound by two parts the value and a pointer to the next element, this class can be implemented as followed.

One we have this class he can implement our LinkedList.

Now we can add some methods that make the LinkedList easier to use.

1.first()

Return the first node in the list.

2.last()

Return the last node in the list.

3. size()

Return the number of nodes in the list.

4.clear()

Clears the list.

5.getNth(nth)

Returns the nth node of the list.

Using the LinkedList.