Insert After

Another very common list operation is to insert a new element or indeed a complete list into an existing list. For data structures such as an array inserting data involves moving a block of data to free up some space for the items being inserted. In a linked list you don't have to do this because all you have to do is change some links.

For example to insert x into the list

A->B->C

after B all you have to do is create x and point it at what B was pointing at and set B to point at x:


A->B->x->C

This is fairly easy to program as long as you remember to keep the end pointer correct.

For example a method that inserts a new item of data following a node which stores a specified item of data is just:

this.insertAfter = function(t, d) {
 var current = this.start;
 while (current !== null) {
  if (current.data === t) {
   var temp = List.makeNode();
   temp.data = d;
   temp.next = current.next;
   if (current == this.end) this.end = temp;
   current.next = temp;
   return; 
  }
  current = current.next;
 }
};

Notice that you only have to fix up the end pointer when the item is inserted at the end and you don't have to fix the start pointer because this method can't insert something before the first node.

Indexing

Where the linked list suffers is when you need to refer to nodes by an index value. That is when you want to pretend that a linked list is an array. The only way of retrieving say the fifth element in the list is to traverse the list and stop at the fifth element.

There are many ways to keep a count of how many elements you have retrieved, here is just one:

this.item=function(i){
 var current = this.start;
 while (current !== null) {
  i--;
  if(i===0) return current;
  current = current.next;
 }
 return null;
};

You could also use a for loop but if so you would need to check that the index was in the range of the list or include a test for the end of the list.

Notice that this indexing routing returns the entire node and not just the data. In most cases it would probably be better to return the data but then you would need an item get and an item set method.

Each

As a final example a useful method and one that is in line with functional thinking is the each method which applies a function to each element of the list.

this.each = function(f) {
 var current = this.start;
 while (current !== null) {
  f(current);
  current = current.next;
  }
};

For example you could use this to display the entire list using an alert function:

The Head and the Tail of it - Lisp Lists

There is another way to build a list structure as a two part data type that stores the head of the list i.e. the first element and the tail of the list i.e. the rest of the list. This is the approach used by Lisp and by many functional languages. It is entirely equivalent to the approach using pointers but it often looks very different. The difference is that instead of considering the node the basic element of the list we work in terms of a list composed ot a head element and a pointer to the rest of the list. Of course the rest of the list has a head element and a pointer to the rest of the list.

You can see that this sort of definition of a list is idea if you want to implement recursive functions. However it is very easy to write methods that give you the head and tail of a list from the sort of data structure described here.

For more information see:  JavaScript data structures - a Lisp-like list