We will first introduce a list in its purest form, implementing the basic methods over a list of integers. This will then be generalised to a list of objects, and applied to a small problem (managing a "To Do" list). We then re-implement this abstract data type using vectors and then with a two dimensional array with internal memory management. 
We should not lose site of just what we mean by an abstract data type (adt). An adt is a data structure with assocated methods. Therefore, when we have a List adt we expect certain functionality, but generally don't care how it is implemented. What we will be doing here is to develop an number of different implementations of the List adt. We do this to get a better idea of just what is involved in implementing this adt, and the costs and benefits of one implementation over another. Therefore, when we talk about adt's we are more concerned about functionality, whereas when we talk of data structures we are concerned with how we implement those adt's. 

Generally, lists are flexible, grow and shrink on demand, elements can be accessed, inserted, deleted. Lists can be joined together (concatenated), split into sub-lists, etc 

Mathematically: a list is empty or is has a head with data in it, followed by a tail that is a list. Note:That is a recursive definition of a list; we have defined a list in terms of a list! 

A list is often shown as follows: 

               a1, a2, ..., an     or as
               [a1,a2,...,an]      or as
               (a1, a2,...,an)  

• List: create a new list. This might be used to create an empty list, or a list with a single element, or a list that contains an element followed by an existing list.
• add: add a new element to an existing list
• insert: insert the element e into the list in order
• delete: delete the element e from the list
• length: the length of the list (zero for an empty list)
• print: print out the list
• reverse: turn the list round
• append: given lists L₁ and L₂, deliver a new list composed of the elements of L₁ followed by the elements of L₂.

       boolean eol;
       int data;
       List next;

• The (boolean) attribute eol is true if the list element corresponds to an empty list, and is false otherwise. Given the List L we can determine if it is empty as follows: L.isEmpty();
• Attribute data contains the data within the list element (and is private, and can be accessed only via method head), and is an integer (so we can at present only have lists of integers). Given a List L we get the data within the first element of L as follows: L.head();
• Attribute next is another list element, or null. Given List L, to get the rest of the list after the first element: L.tail();

Below we have a diagram of a list containing the elements [21, 14, 7]. There are 4 elements in the list. Note that the first 3 all have their eol attribute set to False signifying that the element is not an end of list element. The data attribute has an integer value (21, 14, or 7). The next attribute points to another list element. Note that the last element of the list has an eol set to True and a next attribute pointing to the ground (this is generally accepted as a pointer to null). This fourth and last element, is our representation of the end of list. 

List()

Construct an empty list.

List(e)

Construct a list of a single element with e as the data and an empty list as the next of the list

List(e,l)

Construct a list of a single element with e as the data and l as the next of the list

L.head()

delivers the value of the data within the 1^st element of L.

L.isEmpty()

delivers the value of the eol attribute of the first element of L.

L.tail()

delivers the value of the next attribute, the list that follows the first element of L.

A recursive function is generally of this form: 

     define f(x)
        if x=some.terminating.value
        then do-something-and-then-stop
        else {compute y using the value of x;
              f(y);}

1. The list is empty (i.e. isEmpty()), so print the null string ""
2. The list is not empty, so print the head of the list and then go on and print the tail of the list.

  public void print()
  {
    if (isEmpty())
      System.out.println("");
    else 
      {
        System.out.print(head() + " ");
        tail().print();
      }
  }

  public int length()
  {
    if (isEmpty())
      return 0;
    else return 1 + tail().length();
  }

Given a List L, L.length() might be thought of as expanding to a sequence of additions 1 + 1 + 1 + 1 + ... + 1 + 0 

  public List add(int e)
  {
    return new List(e,this);
  }

Note the use of this. this refers to the current object. The current object is generally implict, for example when we use the method head() in append below. But when we want to do something explicitly with the current object we refer to it as this. 

  public List append(List l2)
  {
    if (isEmpty())
      return l2;                                    // (1)
    else return new List(head(),tail().append(l2)); // (2)
  }

 List(1,[3,5].append(L2))
 List(1,List(3,[5].append[L2]))
 List(1,List(3,List(5,null.append[L2])))
 List(1,List(3,List(5,L2)))

  public List insert(int e)
  {
    if (isEmpty())
      return new List(e);
    else if (e < head())      
      return new List(e,this);
    else return new List(head(),tail().insert(e));
  }

  public List delete(int e)
  {
    if (isEmpty())
      return this;
    else if (e == head())
      return tail();
    else return new List(head(),tail().delete(e));
  }

Given a two Lists L1 and L2, L1.rev(L2) takes the elements in L1 and adds them one by one onto the front of L2, terminating when L1 is empty, delivering L2 as a result. So, to get the reverse of L1 we start with L2 = List(), the empty List. And that is what reverse does, it makes a call to L1.rev(new List()) (but of course L1 is there implicitly). 

  private List rev(List temp)
  {
    if (isEmpty())
      return temp;
    else return tail().rev(new List(head(),temp));
  }

  public List reverse()
  {
    return rev(new List());
  }
}

The Test class uses BasicIo. You used this in 1st year, and we need to import this from java.lancs. The Test program runs on a DOS or UNIX window, putting out a prompt. The program starts by prompting us for a command: end (quits the program), sho (prints the current list), len (prints the length of the list), add (adds a new element to the list, and you are prompted for data), del (delete an element from the current list, and you are prompted for data), rev (reverse the current list). 

On successful completion of each command the current list is printed out. 

import java.lancs.*;

public class Test
{      
       
 public static void main(String[] args) throws Exception
  {
    List l1 = new List();
    int i;
    BasicIo.prompt("Type in command: (end, sho, len, add, ins, del, rev) ");
    String command = BasicIo.readString();
    
    while (!command.equals("end"))
      {
        if (command.equals("sho"))
          l1.print();
        if (command.equals("len"))
          System.out.println(l1.length());
        if (command.equals("add"))
          {
            BasicIo.prompt("data: ");
            i = BasicIo.readInteger();
            l1 = l1.add(i);
            l1.print();
          }
        if (command.equals("ins"))
          {
            BasicIo.prompt("data: ");
            i = BasicIo.readInteger();
            l1 = l1.insert(i);
            l1.print();
          }
        if (command.equals("del"))
          {
            BasicIo.prompt("data: ");
            i = BasicIo.readInteger();
            l1 = l1.delete(i);
            l1.print();
          }
        if (command.equals("rev"))
          {
            l1 = l1.reverse();
            l1.print();
          }
        BasicIo.prompt("Type in command: ");
        command = BasicIo.readString();
      }
  }
}

1. A statement such as l1 = l1.revese() constructs a brand new list, and then assigns it to l1.
2. A statement such as l1 = l1.add(i) creates a new list element and reuses the old l1 as the tail of that element. The list is then assigned to l1.
3. l1 = l1.insert(i) will build a new list, but that list might reuse some of the old list l1.

• Costs: space overhead per element due to pointers, computational effort in maintaining pointers, garbage when we use a constructive technique for insert and delete, garbage on delete!
• Benefits: elegance, simpliciy, elegance, do not need contiguous storage (don't need to pack/shift elements), elegance, can allow lists to grow/shrink dynamically, simplicity.

• l.find(e) finds the first element of the list that has l.head()==e
• l.position(e) delivers the position of e in the list. If e is first element deliver 0, and if e is not in the list deliver -1.
• l.nth(i) delivers the list element at position i. If i=0 deliver the first item in the list. If i is greater than or equal to l.length() throw an exception.