Does Javascript have linked lists?

Linked List in Javascript

Osgood Gunawan

Nội dung chính Show

• Linked List in Javascript
• What Is a Linked List?
• Linked List visualization in javascript:
• Disadvantage
• Three types of linked list
• Implementing a list node in Javascript
• Linked Lists Methods
• JavaScript (JS) Algorithms and Data Structures Masterclass
• Hi! I'm Colt. I'm a developer with a serious love for teaching. I've spent the last few years teaching people to
• Video liên quan

Aug 24, 2020·5 min read

Last time I wrote an article about stack and queue implementation in an array. At the end of the article, I mention that I am going to talk about stack and queue in the Link List. Hold on, but before implementing stack and queue in Linked List, lets understand what linked list is.

What Is a Linked List?

A linked list is similar to an array. The differences are that the linked list doesnt have a particular memory location/index, and its structure is a chain of nodes. Each node contains two items: a value and a pointer to the next node of the chain. Check the illustration down below:

The head pointing(reference) to the first node (element) in the linked list also includes the entry of the linked list. The last node of the list points to null, which is also the tail. The tail is a particular node, where the next pointer is always pointing or reference to null, indicating the end of the list. If the list is empty, the head points to the null.

Linked List visualization in javascript:

Advantage

• The insertion and deletion operation in the linked list is O(1) time complexity faster than the array. Unlike in an array, nodes are also easy to remove and add to the linked list without reorganizing the entire data structure.

Disadvantage

• The search operation is slower than the array since nodes need to access starting from the first node and go through each node at a time to find the element. In contrast, array, we can access the data index element randomly (ex: array[4], not in the linked list case).
• Uses more memory to store additional pointers for linked lists than in arrays.

Three types of linked list

• Singly Linked Lists: each node only pointing to the next node. The above example is all singly-linked lists.
• Doubly Linked Lists: each node has two pointers, a pointer to the next node and a pointer to the previous node.
• Circular Linked Lists: Similar to a singly linked list except the last node points to the first node of the list, forming a loop.

Implementing a list node in Javascript

So how do we create a linked list? First, we need to define a node class. As earlier stated, each node has value and pointer to the next node.

And now, we are implementing a linked list in javascript with a constructor. Start with the head and tail are null, and the length of the list is zero.

Lets create a linked list from the class LinkedList that was just created.

Linked Lists Methods

Unlike arrays, there are no built-in functions in the linked list; everything needs to be created from scratch. Lets build helper methods for the singly linked list.

• push(val): This method takes in value and adds it to the end (the tail) of the list.

• pop(): This method removes the last node (element) of the list and returns the last node that has been removed.

• shift(): This method removes the first node (element) of the list and returns the first node that has been removed.

• unshift(val):This method is the opposite of the push method. Instead of adding a node from the back, add it to the front of the list.

• get(index): This method gets the node from the list.

• set(index,val): This method changes the value of the node. We can utilize the get method from previous to reach our goal for this method.

• insert(index, val): This method inserts a new node to the list. Utilizing push(val) method if the index is at the end of the list, unshift(val) method if the index is from the beginning of the list, and get(index) method if the index is between the start and last.

• remove(index): This method returns the deleted node. Utilizing shift(), pop() and get (index) to reach the index that is about to delete.

Once we understand more about how a linked list works, we can start implementing stack and queue in the next article. Thanks for reading, and I hope you can learn something.

Resources: