Editing a Singly Linked List
Data Structures in JavaScript
In the previous “Data Structures in JavaScript” discussion, we walked through the methodology used to construct a node class which represent each “link” in the “chain” that is a linked list. From there we discussed how to construct a singly linked list from a an array. Building on the previous discussion, we will now dive into editing that singly linked list. If you are not familiar with the code and terminology covered in the previous article it is recommended you review Building a Singly Linked List.
With a linked list there are three ways to edit the list: update a nodes data property, add a node to the list or delete a node from the list. In all these cases, we will want to access a specific place in the singly linked list. Depending on the situation, you might want to edit the nth node from the head of the list, the nth node from the end of the list, or a node of a particular data value. For this discussion, we will assume that we are interested in editing the nth Node from the head of the list. With this in mind, we can step through a singly linked list from the head to the nth a node using a simple for loop as shown in Figure 1.
Editing a Node
When editing a node we simply have to update the data property of that node which is relatively straight forward with the code from Figure 1. As seen in Figure 2, the nthNode function is used to find the correct node and then the nodes data property is updated.
Adding a Node
When inserting a new node to a singly linked list we need to first create the new node, then connect its next property as well as the next property of the previous node appropriately. This can sound a little confusing, so let’s draw a diagram.
In Figure 3 a node is being added at n = 2 by first creating that node, having its next property point to the node after it (n = 3), and then updating the node before (n=1) to point to the new node. Generalizing this process results in the addNode function seen in Figure 4.
In addition to adding a node to the middle of the singly linked list there exist two edge cases: adding a node to the beginning of the list or at a location outside of the existing scope of the list. To add a node at the beginning of the list (n = 0) only requires the new node’s next property to point to the old head. Now when adding a node at a location beyond the scope of the list can’t be done since a previous node doesn't exist so the code simply returns null instead.
Deleting a Node
When deleting a node from a linked list there is no actual deleting that occurs; instead the next pointer of the previous node is updated to skip the selected node. This is another instance where a quick diagram can add a lot of value.
In the above diagram you can see that when deleting the node at n = 2 the next pointer of the previous node, in this case at n = 1 is updated to point the the next node which is n = 3 in this example. The node being deleted doesn't have to be updated even though its next property points to a node on the linked list. This is because it will never be referenced by the singly linked list. Like in the case of adding a node, the code needs to consider the edge cases of deleting the head of the singly linked list or a node beyond list scope.
Additional Notes
Although this article does not discuss a doubly linked list, the process for adding and deleting a node would require the previous property to be updated appropriately. It is of note that the editNode function would not have to change at all.
