Doubly linked lists: the Editor example

Doubly linked lists

Another list-like data structure you may come across or need to use is the doubly linked list. This is a list structure in which each cell in the list has a pointer to the cell before it and also a pointer to the cell behind it. For example:

Normal linked lists have the links going one way, so if we want to run a pointer through the elements of a list we have to start at one end and move to the other one element at a time. We have seen the case of a list structure with an extra pointer to the last element in the list which makes it easier to add new items to the back of a list. A doubly-linked list structure is useful where we might want to run both ways in a list with equal convenience.

One abstract data type where we might want to use a doubly-linked list for implementation is a list with an insertion point (which is also known as a "sequence"). In the abstract, we can think of this as something like [a,b^,c,d] where the ^ symbol represents the insertion point. The operations on the structure are:

Return the current element which is the element at the insertion point, in the above case, b.

Insert a new element. If the element we are inserting is e then the state from the above after the operation would be [a,b,e^,c,d]. The element is inserted following the insertion point, and this point becomes the new insertion point.

Move the insertion point forward. If we follow from after the previous insert operation, the state becomes [a,b,e,c^,d].

Delete the current element. This deletes the element which is the current insertion point. Following on from the situation above after the forward operation, we get [a,b,e,d^]. Note the insertion point becomes the element which was after the deleted element.

Move the insertion point backwards. Applying this operation next gives us [a,b,e^,d].

We also have an operation which says whether the list is empty, one which says whether the insertion point is the first element and one which says whether the insertion point is the last element. If the list is empty, neither the forward, backward or delete operations can work. If the current position is the first element, the backward operation cannot work, if the current position is the last element, the forward operation won't work.

The data structure representing this has a double linked list, with a pointer pointing to the cell of the current position as the field of an object:

Inserting a new element involves creating a new cell, and rearranging the pointers so they correctly reflect a doubly linked list with the current position pointer pointing to the new cell:

Moving the insertion point forward or backwards simply involves following one link in the appropriate direction down the chain, for example, forward from the above gives:

Deleting involves more rearrangement of pointers:

When dealing with inserting or deleting, special account needs to be taken of inserting or deleting at the end of ths list, or inserting into an empty list. When the last element in the list is deleted, the insertion point becomes the new last element since it cannot move forward to the next element.

Here is code for the abstract data type of a list with an insertion point, implemented as suggested above by a doubly-linked list: 

class InsertList1
{
 private Cell ptr;

 public InsertList1()
 {
  ptr=null;
 }

 public boolean isEmpty()
 {
  return ptr==null;
 }

 public boolean atEnd()
 {
  return ptr.next==null;
 }

 public boolean atStart()
 {
  return ptr.prev==null;
 }

 public void insert(Object obj)
 {
  if(ptr==null)
     ptr = new Cell(null,obj,null);
  else if(ptr.next==null)
     {
      ptr.next = new Cell(ptr,obj,null);
      ptr = ptr.next;
     }
  else
     {
      ptr.next.prev = new Cell(ptr,obj,ptr.next);
      ptr.next = ptr.next.prev;
      ptr=ptr.next;
     }
 }

 public void delete()
 {
  if(ptr.next==null)
     {
      ptr = ptr.prev;
      if(ptr!=null)
         ptr.next=null;
     }
  else
     {
      ptr.next.prev = ptr.prev;
      if(ptr.prev!=null)
         ptr.prev.next = ptr.next;
      ptr=ptr.next;
     }
 }

 public void forward()
 {
  ptr = ptr.next;
 }

 public void backward()
 {
  ptr = ptr.prev;
 }

 public Object current()
 {
  return ptr.content;
 }
 
 public String toString()
 {
  Cell temp;
  String str="";
  if(ptr!=null)
     {
      for(temp=ptr; temp.prev!=null; temp=temp.prev);
      for(;temp!=null;temp=temp.next)
         {
          if(temp==ptr)
             str+="> ";
          else
             str+="  ";
          str+=temp.content+"\n";
         }
     }
  return str;
 }

 private static class Cell
 {
  Cell prev,next;
  Object content;

  Cell(Cell p,Object obj,Cell n)
  {
   prev=p;
   content=obj;
   next=n;
  }
 }
}
There is also a method toString for giving a string representation of the list. In this case, it puts the string representation of each object in the list on a separate line, with two blank spaces in front of each except the line for the object at the insertion point which is preceded by "> ".

A simple editor

The use of a list with an insertion point can be demonstrated in the program below which gives a simple text editor. In this case, the elements in the list are strings, representing lines of text. The editor works only by adding or deleting lines of text, there are no commands to alter a line.

The command i in the editor puts it in input mode. Following this, all text typed is added to the stored text in the editor following the insertion point until a line consisting of just the full stop character is entered. This causes the editor to go back to command mode, with the insertion point the end of the new text.

The commands + and - move the insertion position up and down the stored text. Each time it is moved, the line which becomes the new insertion point is printed. The command p prints the line which is the current insertion point without moving the insertion point.

The command d deletes the line which is the current insertion point and prints the next line which is the new insertion point.

The command l prints the entire stored text, indicating the insertion point with "> ", and the command q quits the editor.

Here is the code: 

import java.io.*;

class Editor1
{
 public static void main(String[] args)
 throws IOException
 {
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  InsertList1 lines = new InsertList1();
  char ch;
  String command,line;
  do {
      System.out.print(": ");
      command = in.readLine();
      ch = command.charAt(0);
      switch(ch)
        {
         case 'i' :
            do {
                line = in.readLine();
                if(line.length()==1&&line.charAt(0)=='.')
                   break;
                lines.insert(line);
               }
            while(true);
            break;
         case 'd' :
	    if(lines.isEmpty())
	       System.out.println("?");
	    else
	       {
	        lines.delete();
	        if(!lines.isEmpty())
	           System.out.println(lines.current());
	       }
	    break;
         case '+' :
            if(lines.isEmpty()||lines.atEnd())
               System.out.println("?");
            else
               {
                lines.forward();
                System.out.println(lines.current());
               }
            break;
         case '-' :
            if(lines.isEmpty()||lines.atStart())
               System.out.println("?");
            else
               {
                lines.backward();
                System.out.println(lines.current());
               }
            break;
         case 'p':
            if(lines.isEmpty())
               System.out.println("?");
            else
               System.out.println(lines.current());
            break;         
         case 'l':
            System.out.print(lines);
            break;
         case 'q': break;
         default: 
             System.out.println("?");
        }    
     }
  while(ch!='q'); 
 }
}

A double stack implementation

Another way of representing a list with an insertion point is to use two stacks. The stacks need only be single linked lists. In the representation, one stack holds all the items before and up to the insertion point, the other stack holds the items after the insertion point. If we call these stacks before and after, then moving the insertion point forward can be implemented by taking the top item off the after stack and putting it on the before stack, while moving the insertion point backwards can be implemented by taking the top item off the before stack and putting it on the after stack. The before stack is a linked list of items in the reverse order in which they occur in the list considered as a whole list, while the after stack holds the items in the same order as they are considered in the list. Deleting an item involves just taking the item off the top of the before stack, while adding an item involves adding it to the top of the before stack.

Here is some Java code that uses this implementation: 

class InsertList2
{
// A sequence type implemented using two singly-linked lists.

 private Cell before,after;

 public InsertList2()
 {
  before=null;
  after=null;
 }

 public boolean isEmpty()
 {
  return before==null&&after==null;
 }

 public boolean atEnd()
 {
  return after==null;
 }

 public boolean atStart()
 {
  return before.next==null;
 }

 public void insert(Object obj)
 {
  before = new Cell(obj,before);
 }

 public void delete()
 {
  before = before.next;
 }

 public void forward()
 {
  Cell ptr=after;
  after=after.next;
  ptr.next=before;
  before=ptr;
 }

 public void backward()
 {
  Cell ptr=before;
  before=before.next;
  ptr.next=after;
  after=ptr;
 }

 public Object current()
 {
  return before.content;
 }
 
 public String toString()
 {
  Cell ptr;
  String str="";
  if(before==null)
     return "";
  for(ptr=before.next; ptr!=null; ptr=ptr.next)
     str="  "+ptr.content+"\n"+str;
  str=str+"> "+before.content+"\n";
  for(ptr=after; ptr!=null; ptr=ptr.next)
     str=str+"  "+ptr.content+"\n";
  return str;
 }

 private static class Cell
 {
  Cell next;
  Object content;

  Cell(Object obj,Cell n)
  {
   content=obj;
   next=n;
  }
 }
}

An array implementation

Destructive lists with an insertion point can easily be implemented using an array and count technique as discussed previously. In this case, as well as the count field of the object giving the total amount of array used, there is a requirement for an additional field giving the current insertion point. Below is a simple implementation of this idea, giving a data structure in which the only operations are to insert at the current insertion point, to delete at the current insertion point, and to the move the insertion point forwards and backwards. We call the type IntSequence, for demonstration purposes reverting to collections of integers: 
class IntSequence
{
// Sequence class

 private int[] array;
 private int count,current;
 final static int MAX=100;

 public IntSequence()
 {
  array = new int[MAX];
 }

 public void delete()
 {
  if(current<count)
     {
      for(int i=current+1;i<count;i++)
         array[i-1]=array[i];
      count--;
     }
 }

 public void add(int n)
 {
  for(int i=count;i>current;i--)
     array[i]=array[i-1];
  array[current]=n;
  current++;
  count++;
 }

 public void forward()
 {
  if(current<count)
     current++;
 }

 public void backward()
 {
  if(current>0)
     current--;
 }

 public String toString()
 {
  int i;
  String str="[";
  if(current==0)
     str+="^";
  if(count>0)
     {
      str+=array[0];
      for(i=1;i<count;i++)
         if(current==i)
            str+=",^"+array[i];
         else
            str+=","+array[i];
      if(current==count)
         str+=",^";
     }
  return str+"]";
 }
}
When an integer is added to or deleted from a sequence in this representation, the entire contents of the array following the insertion point have to be copied to or from their next cell in the array. This means that insertion and deletion are O(N) in this representation. In the doubly-linked list representation, insertion and deletion are O(1) since the amount of pointer manipulation required is fixed, not dependent on the size of the list.

Here is a front-end which uses this class to give a simple sequence maintenance program: 

import java.io.*;

class UseIntSequences
{
// Sequence maintenance program

 public static void main(String[] args)
 throws IOException
 {
  int n=0;
  char ch;
  String line;
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  IntSequence mySequence = new IntSequence();
  do {
      System.out.print(": ");
      line = in.readLine();
      ch = line.charAt(0);
      if(line.length()>1)
         n = Integer.parseInt(line.substring(1).trim());
      switch(ch)
         {
          case 'q' : 
            break;
          case 'd' :
            mySequence.delete();
            break;
          case 'a' :
            mySequence.add(n);
            break;
          case 'f' :
            mySequence.forward();
            break;
          case 'b' :
            mySequence.backward();
            break;
          case 'p':
            System.out.println(mySequence);
            break;
          default:
            System.out.print("d - delete, a - add, f - forward,");
            System.out.println(" b - backward, p - print, q - quit");
            break;
         }
     }
  while(ch!='q');
 }

}
Matthew Huntbach

Last modified: 12 March 2004