Building a Singly Linked List
Data Structures in JavaScript
Most likely you arrived at this article because your preparation for an interview has lead you down a LeetCode rabbit hole. Linked lists are a favorite of many interviewers to test an interviewees understanding of basic data structures as well as your problem solving skills. Whether you're just a bit rusty from school or this is your first time encountering linked lists they can be a bit tricky to understand at first.
As with most problems it is helpful to start with a diagram. A linked list is a linear data structure which can be thought of as a chain, where each link in a chain is connected to the next link. In a linked list, each link in the chain will be represented as a node.
In a singly linked list, each node contains some data and then a pointer to the next node. For a doubly linked list there would also be a pointer to the previous node. The first node in the list is conventionally referred to as the head and the final node’s next pointer refers to nothing. With this diagram constructed it is now time to start coding up a singly linked list in JavaScript.
Coding a Node Class
Since a singly linked list consists of many notes it makes sense to create a class Node that way a new node can be easily and consistently instantiated. At the instantiation of a new node the data it will contain should be know but the next node might not be known.
A doubly linked list node class would look very similar to Figure 2 but with an additional property of previous that would also initialize to null as it may not be known or it could be the head node.
Building a Singly Linked List
With the node class written we can dive into building the singly linked list. Assume we have an array where each element represented the data that should be stored in a node and the subsequent element should be the next node. The element at index zero would be the head of this linked list.
The above function first checks two edge cases where either no or only a single node is created. The code then for loops through the remaining array creating a node for each elements data and then adds the next property to the previous node. Once that is completed, the head of the list is returned as it now points to the next node, which points to the next node, and so on until the last node’s next property points to null.
Additional Notes
Although this article does not cover how to insert or delete a node into an existing linked list, it is worth a quick discussion. Since a linked list is not indexed, any insertion or deletion of a node would need to start at the head node and then step through the subsequent nodes until the desired location is found. From here, the next property of the previous node would have to be updated to point to the appropriate node. For a more detailed discussion see the subsequent article in the “Data Structures in JavaScript” series: Editing a Singly Linked List.
I’m sure I am not the first to recommend Cracking the Coding Interview but if you are studying data structures and algorithms for an interview it is a great resource.
