The List Abstract Data Structure

In the array implementation a list [a,b,c,d,e] is actually represented as an array, declared as a private field with name myArray on line 3, where myArray[0] stores a, myArray[1] stores b, myArray[2] stores c and so on. The length of the array is the same as the length of the list. As the code for tail on lines 25-31, and for cons on lines 33-40 show, this implementation is more time consuming and complex, since these methods require the creation of an entirely new array, and the copying of the information from the initial array into this new array.

Further list examples

 public String toString()
 {
  if(isempty())
     return "[]";
  else
     return "["+head()+restToString(tail());
 }

 private static String restToString(List L)
 {
  if(L.isempty())
     return "]";
  else
     return ","+L.head()+restToString(L.tail());
 }

     1  import java.io.*;
     2  import java.util.*;
     3
     4  class ListRead
     5  {
     6
     7   public static List readCharList(BufferedReader in) 
     8   throws CharListFormatException,IOException
     9   {
    10    StringTokenizer chars;
    11    String token,str=in.readLine().trim();
    12    List l1,l2;
    13    if(str.charAt(0)!='['||str.charAt(str.length()-1)!=']')
    14       throw new CharListFormatException();
    15    str=str.substring(1,str.length()-1);
    16    chars = new StringTokenizer(str,","); 
    17    l1=LinkedList.empty();
    18    while(chars.hasMoreTokens())
    19       {
    20        token=chars.nextToken();
    21        if(token.length()!=1)
    22           throw new CharListFormatException();
    23        l1=l1.cons(new Character(token.charAt(0)));
    24       }
    25    l2=LinkedList.empty();
    26    while(!l1.isempty())
    27       {
    28        l2=l2.cons(l1.head());
    29        l1=l1.tail();
    30       }
    31    return l2;
    32   }
    33
    34   public static List readIntList(BufferedReader in) 
    35   throws IntListFormatException,IOException
    36   {
    37    StringTokenizer ints;
    38    String token,str=in.readLine().trim();
    39    List l1,l2;
    40    int n;
    41    if(str.charAt(0)!='['||str.charAt(str.length()-1)!=']')
    42       throw new IntListFormatException();
    43    str=str.substring(1,str.length()-1);
    44    ints = new StringTokenizer(str,","); 
    45    l1=LinkedList.empty();
    46    while(ints.hasMoreTokens())
    47       {
    48        token=ints.nextToken();
    49        try {
    50             n=Integer.parseInt(token);
    51            }
    52        catch(NumberFormatException e)
    53            {
    54             throw new IntListFormatException();
    55            }
    56        l1=l1.cons(new Integer(n));
    57       }
    58    l2=LinkedList.empty();
    59    while(!l1.isempty())
    60       {
    61        l2=l2.cons(l1.head());
    62        l1=l1.tail();
    63       }
    64    return l2;
    65   }
    66   
    67 } 

class CharListFormatException extends Exception
{
}

class IntListFormatException extends Exception
{
}

Here is a program uses the method for reading lists of characters:

import java.io.*;

class UseLists1
{

 public static void main(String [] args) throws IOException
 {
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  List list1,list2;
  int n;
  for(;;) try
     {
      System.out.print("Enter list of characters 1 : ");
      list1=ListRead.readCharList(in);
      break;
     }
  catch(CharListFormatException e)
     {
      System.out.println("Not a valid list of characters");
     }
  for(;;) try
     {
      System.out.print("Enter list of characters 2: ");
      list2=ListRead.readCharList(in);
      break;
     }
  catch(CharListFormatException e)
     {
      System.out.println("Not a valid list of characters");
     }
  System.out.print("\nList 1 is: "+list1);
  System.out.print("\nList 2 is: "+list2);
  System.out.print("\n\nAppending list 1 to list 2 is: ");
  System.out.println(ListOps.append(list1,list2));
  System.out.print("\nMerging list 1 with list 2 is: ");
  System.out.println(ListOps.merge(list1,list2));
  System.out.println();

  for(;;) try
     {
      System.out.print("Enter an integer: ");
      n=Integer.parseInt(in.readLine());
      break;
     }
  catch(NumberFormatException e)
     {
      System.out.println("Not a valid number");
     }
  System.out.print("The first "+n+" elements of list 1 are: ");
  System.out.println(ListOps.take(n,list1));
  System.out.print("\nList 2 less its first "+n+" elements is: ");
  System.out.println(ListOps.drop(n,list2));
  System.out.println();
 }

}

class ListOps
{

 private static List empty()
 // Returns a new empty list
 {
  return LinkedList.empty();
 }

 public static List append(List l1,List l2)
 // Joins its two input lists together
 {
  if(l1.isempty())
     return l2;
  else
     {
      List a=append(l1.tail(),l2);
      return a.cons(l1.head());
     }
 }

 public static List merge(List l1,List l2)
 // Merges its two input lists, taking an object from each
 // one alternatively
 {
  if(l1.isempty())
     return l2;
  else if(l2.isempty())
     return l1;
  else
     {
      List m=merge(l1.tail(),l2.tail());
      return m.cons(l2.head()).cons(l1.head());
     }
 }

 public static List take(int n,List L)
 // Gives the list consisting of the first n elements of L
 {
  if(n==0||L.isempty())
     return empty();
  else
     return take(n-1,L.tail()).cons(L.head());
 }

 public static List drop(int n,List L)
 // Gives the list consisting of the elements of L less its
 // first n elements
 {
  if(n==0||L.isempty())
     return L;
  else    
     return drop(n-1,L.tail());
 }

}

import java.io.*;

class UseLists2
{

 public static void main(String [] args) throws IOException
 {
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  List list1=null,list2=null;
  for(;;) try 
     {
      System.out.print("Enter list of characters: ");
      list1=ListRead.readCharList(in);
      break;
     }
  catch(CharListFormatException e)
     {
      System.out.println("Not a valid list of characters");
     }
  for(;;) try 
     {
      System.out.print("Enter list of integers: ");
      list2=ListRead.readIntList(in);
      break;
     }
  catch(IntListFormatException e)
     {
      System.out.println("Not a valid list of integers");
     }
  System.out.print("\nList 1 is: "+list1);
  System.out.println("\nList 2 is: "+list2);
  System.out.print("\nAppending list 1 to list 2 is: ");
  System.out.println(ListOps.append(list1,list2));
  System.out.print("Merging list 1 with list 2 is: ");
  System.out.println(ListOps.merge(list1,list2));
 }

}

Writing recursive methods to build lists

Writing such a recursive method generally involves thinking about the problem by considering what happens when you apply the recursive method to the tail of the input list. If a logical relation can be given which links the desired output with the output of the recursive operation, a method can be built up. It often helps to start with an example and then generalise. For example, suppose we want to append [a,b,c] to [x,y,z]. The result should be [a,b,c,x,y,z]. Thinking about it recursively, if we append [b,c] (the tail of the first input) to [x,y,z] (the second input), we get [b,c,x,y,z]. This is almost the output we want, in fact all we need do is append the head of the first input to it to get it. This gives us the recursive part of the append method, which just generalises from this example:

      List a=append(l1.tail(),l2);
      return a.cons(l1.head());

      return append(l1.tail(),l2).cons(l1.head());

Having got the recursive part right, we need to consider the base case - what happens when we can't take the tail of the first input because it is empty. Obviously appending an empty list to a list L gives the list L as output. With this we can write our complete append method, as given above.

Now let us consider in a similar way, how to write the method for take. Suppose the arguments to take are 3 and [k,l,m,n,o,p,q]. Then the result should be [k,l,m]. If we try the recursive call with the same integer argument but the tail of the list argument i.e. 3 and [l,m,n,o,p,q] we get [l,m,n] which doesn't quite help us. Let us consider again, this time the recursive call with arguments the integer argument less one and the tail of the list argument, i.e. 2 and [k,l,m,n,o,p,q]. This time the result of the recursive call is [l,m], which is close to the [k,l,m] we want, so this looks like the recursive call we should use. Again the final result comes from appending the head of the input list to the result of the recursive call. We could do this in two steps (as before, generalising from the specific example to the general case):

List t=take(n-1,L.tail());
return t.cons(L.head());

return take(n-1,L.tail()).cons(L.head());

Because recursive methods on lists are based on thinking about logical relations between method calls, they are often the best way to write list methods - it's easy to do once you've got the hang of it, and what the code does is very clear (again, once you've got the hang of using recursion). It is often possible to use iteration however. Beware that a loop which takes elements of a list and conses them to something else causes them to be reversed. So the following does not append two lists:

public static list append1(List l1,List l2)
{
 while(!l1.isempty())
    {
     l2=l2.cons(l1.head());
     l1=l1.tail();
    }
 return l2;
}

public static list append2(List l1,List l2)
{
 List l3=empty();
 while(!l1.isempty()
    {
     l3=l3.cons(l1.head());
     l1=l1.tail();
    }
 while(!l3.isempty())
    {
     l2=l2.cons(l3.head());
     l3=l3.tail();
    }
 return l2;
}

l1=l1.tail();

These notes were produced as part of the course Introduction to Programming as it was given in the Department of Computer Science at Queen Mary, University of London during the academic years 1998-2001.

Last modified: 25 Jan 1999