Linked Lists in JavaScript

Adding a node to the end of a linked list

Let's suppose we want to add the name "Ian" to the end of the list. Firstly, we get an index of a slot where we can insert the name:

var newnode = get_node("Ian");

The variable newnode now points to the array index where the new name is stored. The next property of this new node is automatically set to -1, indicating that it is last in the list. Now we have to persuade the node that is currently last in the list to point to the new node. This is done by starting at the beginning of the list, and looking at the next property of each element we come across. This will tell us the index in the array of the next node that we need to check. Eventually, the next property of a node will be -1, which tells us that that node is the last one in the list.

var n = START;   // Starts at first node in list
var reached_end = false;
while (reached_end == false)
 { var next_index = nodes[n].next;
   if (next_index == -1)   // We've reached the end!
     reached_end = true;
   else
     n = next_index;       // Moves to next one in list
 }

When this loop terminates, n will contain the index in the array of the last node currently in the list. We know that the list starts off with only one node (the name Richard in nodes[0]), so the first time you run this function, the loop terminates immediately as the next property of nodes[0] is -1. As the list gets longer, the loop goes through more iterations before terminating.

The only other thing to do is to set the next property of this node to point to the new name (index newnode):

nodes[n].next = newnode;

Searching a linked list for an item

Well this is fairly simple, particularly given the while loop that you met in the last section. All we have to do is go through the list again, this time checking the information part of each node. Suppose we need to check the list for the string search_string:

var n = START;
var reached_end = false;
var found_it = false;         // true if/when we find the name
while (reached_end == false && found_it == false)
 { if (nodes[n].name == search_string)
     found_it = true;
   else
     { var next_index = nodes[n].next;
       if (next_index == -1)   // We've reached the end!
         reached_end = true;
       else
         n = next_index;       // Moves to next one in list
     }
 }
if (found_it == true)
  alert("Found the name!");

You'll recognise the basic structure of this loop, but this time there is an additional stopping clause. The first thing that happens in the loop is that the contents of the node is compared to the search string. If they match, the variable found_it is set to true and the loop terminates. You will notice that the while loop also checks found_it as well as reached_end. If the search string is not found, the loop only terminates when reached_end becomes true, as before.

We can tell that the search string was present after the loop simply by examining found_it. If true, then the variable n now holds the array index of the found node. That's why it was important to end the loop the moment that the search string was found. We can use n to display any more information about the node, or to do any editing.

Adding a node in the middle of a linked list

This is a little harder as we need to juggle links between nodes carefully. Firstly, let's assume that we have been asked to insert a name before the node with a given name e.g. insert a node with the name "Pippa" before name "Sarah" in the list. We'll assume that the name to be inserted is given by new_name, the name before which it is to be inserted is called before_name, and that these are passed as parameters to a function insert_middle_node(). The routine is slightly different, depending on whether the "insert before" name is the first node of the list or not:

function insert_middle_node (new_name, before_name)
{ if (nodes[START] == before_name)
    insert_node_at_start(new_name)
  else
    insert_node_in_middle(new_name, before_name)
}

if the starting node is the name before which to insert the new node, we call a special routine insert_node_at_start and pass it the parameter new_name. Otherwise, we call insert_node_in_middle, which handles insertions anywhere in the list apart from at the start or end.

Inserting a node at the start is done as follows. We'll use the example of inserting the name "Pippa" before "Richard" (at the start of the list)

1. Firstly, we create the node in the first free slot, and make sure we have a variable called new_node that points to its index:
   

2. Then we set the next link of the new node to the same value as the index of the starting node in the list, e.g. if the current starting node is at index 5, then we set the next link of the new node to 5. This is because the current starting node will become the second node in the list.
   

3. Finally, we reset the value of START to the index of the new node, as it is now the new starting node in the list. Now you can see why we store the index of the start of the list in a variable rather than always assuming it starts at 0.
   
   You can see by tracing the lines that the diagram above is equivalent to the following, i.e. Pippa has been inserted at the start of the list:
   

It is important that we do steps 2 and 3 above in the correct order. We must save the value pointed to by START before we overwrite it with the new value of the starting index. Here's the function that carries out the steps above. See if you can match the lines of the function with the steps above:

function insert_node_at_start (new_name)
{ var new_node = get_node(new_name);
  nodes[new_node].next = START;
  START = new_node;
}

Inserting a node somewhere else in the list is a little harder. This is because we need to find the correct place for the insertion in the first place and then maintain some more pieces of information. We need a pointer (call it n1) that looks for the correct place in terms of the name before which we want to insert the new name, but also a pointer (call it n2) that points to the node before that one. In the example below, we will consider the example where the name "Pippa" is inserted before the name "Henry".

1. Create the new node with the name "Pippa" in it.

2. Set n1 to the same value as START and n2 to the node that the starting node in the list points to (i.e. pointer n2 points to the second name in the list, pointer n1 to the first name in the list. n1 is and will always be one name behind n2).
   

   We know that pointer n2 won't have "missed" the name we are searching for (Henry in this example), as this procedure is only called if the first name is not the one we are searching for.

3. Is the name pointed to by n2 the insert-before name? If no, advance both n2 and n1 until either n2 is the insert-before name, or n2 is -1 (indicating that it has dropped off the end of the list). If it has reached the end of the list without success, the process finishes.
   

4. If we get to this point, n2 points to the insert-before name and n1 points to the name before. We need to insert the name between these two. Change the next pointer of the new node to the same value as n2.
   

5. Now change the next pointer of the node pointed to by n1 to point to the newly inserted node. This ties up the last link in the chain:
   

After the procedure we no longer need pointers n1 and n2. If you trace the arrows you will find that the node with the name "Pippa" lies in the list between Diane and Henry. However, you can see now why we needed n1. Suppose we had only used n2. When we had advanced it to the point where we had found the insert-before name, we couldn't have changed the next pointer of the node before that one in the list in order to maintain the chain structure.

And here we have all that in the form of JavaScript.

function insert_node_in_middle (new_name, before_name)
{ var new_node = get_node(new_name);
  var n1 = START;
  var n2 = nodes[START].next;
  while (nodes[n2].name != before_name && nodes[n2].next != -1)
   { n2 = nodes[n2].next;
     n1 = nodes[n1].next;
   }
  if (nodes[n2].name == before_name)
   { nodes[newnode].next = n2;
     nodes[n1].next = newnode;
   }
  else
   alert("Failed to find name: " + before_name);
}

Deleting a node from the list

We've done searching the list for an item, and adding a node to the list in various places. The only thing left is to delete a node from the list. Again the procedure will differ slightly depending on whereabouts in the list the node lies (start, middle or end).

To delete a node from the start of the list:

• Set the valid property of the node pointed to by START to false

• Set the value of START to the value of the next pointer of the current start node

Here's the computer code that does the same thing:

function delete_start_node ()
{ nodes[START].valid = false;
  START = nodes[START].next;   // New start of list
}

This is the reason that we store the start of the list in variable START rather than assuming it is index 0 in the array. The following procedure is used to delete a node from the end of the list:

• If the node that START points to has a next pointer which is -1, then the list only has one item in it. We can still delete this node, by setting its valid flag to false and perhaps setting START to some value like -1 to indicate "empty list".

• Assuming the list has more than one node, set variable n1 to START and variable n2 to the next property of that starting node. You may recognise this procedure as similar to the way we tackled inserting a node in the middle of the list.
  

• Move both pointers along one node at a time until n2 points to a node whose next property is -1. This will indicate that n2 is the last node in the list and n1 points to the previous node, since it's always one node behind.
  

• The rest is fairly easy. We simply mark the end node (indicated by n2) as invalid, and mark the next property of the previous node (indicated by n1) as -1 to show that it is the new end node.
  

Here's the JavaScript that does the same thing:

function delete_end_node ()
{ if (START == -1)   // If list already empty, abort!
    return;
  if (nodes[START].next == -1)  // List contains one name only
    { START = -1;               // List now empty
      return;
    }
  var n1 = START;
  var n2 = nodes[START].next;
  while (nodes[n2].next != -1)  // As long as n2 isn't last node
   { n2 = nodes[n2].next;
     n1 = nodes[n1].next;
   }
  nodes[n2].valid = false;      // Remove name from list
  nodes[n1].next = -1;          // Indicates new end of list
}

The only other thing to consider is deleting a node from the middle of the list, defined as deleting the node before a given name. This is done in a similar manner to deleting the node at the end, except that instead of looking for the end of the list (nodes[n2].next == -1), we look for the "delete-before" name. However, in this case, we need to maintain three pointers: one for the node to be deleted (we'll call that n2), one for the node before that in the list (call it n1) to tie up the pointers correctly, and one for the next node in the list (call it n3) to detect the presence of the delete-before name.

• Is the list empty? If not, does the first node contain the delete-before name? Does the list only contain one item? If the answer is yes to any of these questions, the procedure ends!

• Is the second name the delete-before name? If so, delete the first name in the list (we already have a procedure to do this!)

• If we get to this point, we need to check through the list to find the delete-before name. We already know that the delete-before name isn't the first item in the list, or the second, so we can set the following values: Set n1 to the first item in the list, n2 to the second item, and n3 to the third item

And in JavaScript:

function delete_middle_node (delete_before_name)
{ if (START == -1)
    return;
  if (nodes[START].name == delete_before_name || nodes[START].next == -1)
    return;
  var n1 = START;               // Starting node
  var n2 = nodes[START].next;   // 2nd node in list
  if (nodes[n2].name == delete_before_name)  // 2nd name is delete-before name
   { delete_start_node();       // so delete first name (we already know how
     return;                    // to do this!)
   }

  var n3, finished = false;
  while (finished == false)
   { if (nodes[n2].next == -1)
       finished = true;
     else
       { n3 = nodes[n2].next;      // 3rd node in list
         if (nodes[n3],name = delete_before_name)
          {  // Found the name, so do the delete!

             finished = true;
          }
       }
   }

}