Algorithms and Data Structures
 Quick Links What's New  Home  Contacts Course Book  Java Book  JDK & JDSL  Slides  Notes  Demos  Exercises  Marks

Abstract: A look at lists, how we can implement them, and the operations (methods) that act upon them.

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.

What is a list?
A list is a sequence of elements. You can think of many applications of lists, in the real world and abstractly. Real world, we have shopping lists, lists of things to do, list of students, etc. Abstractly, in the computer, we can manage the memory of the machine as a list, a file of characters as a list, a list of activities to process, etc.

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)  ```
The basic methods we would expect to have over a list are as follows
• 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.
• 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 L1 and L2, deliver a new list composed of the elements of L1 followed by the elements of L2.

A first stab at the List Class, and its methods (java code)
Our first definition of the List Class, and its methods is defined textually below. A List is defined as a triple:
```       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();
Therefore we have the basic methods isEmpty, head, and tail. In lisp-like languages (such as Lisp, and Scheme) the method head is known as car, tail as cdr, and isEmpty is generally null.

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

Why can't I have a null List in Java?
A good question! The methods that we use on a List are defined for the class List (obviously). It would have been nice to be able to apply the relevant methods to an empty list null. Unfortunately null is classless! So, Java would not know what method to apply. This is a nuisance. Consequently I have to tag each List element to say if it is actual data or the end of list marker. And the end of list marker looks like every other List element with the exception that its eol attribute is True
The constructors
We have three constructors:
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

The accessors
We have 3 methods to access elements of the list. Assume we have the List L.
delivers the value of the data within the 1st 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.
Therefore we have the basic methods isEmpty, head, and tail. In lisp-like languages (such as Lisp, and Scheme) the method head is known as car, tail as cdr, and isEmpty is generally null.
To print a list
This is our first recursive function. A recursive function/method is defined in terms of itself. We have already seen a recursive definition of a class, the List. So it would appear natural that methods that operate over this class will be recursive as well.

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);}```
This is an example of tail recursion. The print method is also tail recursive. We must address the following situations when printing a List L:
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
{
tail().print();
}
}```
The method terminates when it encounters the empty list element. You might like to think of the method as operating with some kind of pointer that chases along the list, and each recursive call uses this pointer and then moves it along one place/element on the recursive call.
Length of a list
The length of a list is a count of the number of List elements in the List. Given a List L, the length of L is 0 if L is empty, otherwise it is one plus the length of the rest of the list
```  public int length()
{
if (isEmpty())
return 0;
else return 1 + tail().length();
}```
The above italicised text is a recursive definition of the length of a list, defined in terms of the method length. Again, it has a stopping condition (when the List is empty), and an action to perform immediatley before it makes is recursive call.

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

Add an element e to the list
```  public List add(int e)
{
return new List(e,this);
}```
Add an element to the list, for example with List L, L=L.add(3), will add a new List element to the front of L. In a lisp-like language (lisp or scheme) this method is implemented in the function cons

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

Append two lists together
Given two Lists L1 and L2, L1.append(L2) delivers a new List with the elements of L1 followed by the List L2. Again, the method is tail recursive.
```  public List append(List l2)
{
if (isEmpty())
return l2;                                    // (1)
else return new List(head(),tail().append(l2)); // (2)
}```
The line commented (1) we are appending L2 to an empty List, so we just deliver L2. Line commented (2) we make our recursive call: we deliver a new List with L1.head() as the data and a next of the list composed of L2.tail() with L2 appended. So, you might think of this expanding into a sequence of calls to the constructor List(e,l). For example assume we have List L1 [1 3 5] and List L2 [2 4 6], a call L1.append(L2) expands as follows
``` 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)))```

Insert an element e into a List
Given a List L1, insert an element in order into the list. Deliver a new list. A call might be L1.insert(3), inserting the integer 3 into the List L1.
```  public List insert(int e)
{
if (isEmpty())
return new List(e);
return new List(e,this);
}```
Again, tail recursive. We see a pattern similar to append, with recursive calls building up a sequence of calls to the constructor List(e,l).
Delete an element e from a List
Delete an element from the List, delivering a new List. Given L1 and element e=3, we might have L1.delete(3), deleting the list element with L1.head()==3.
```  public List delete(int e)
{
if (isEmpty())
return this;
return tail();
}```
Similar to insert and append, being tail recursive, building up a sequence of calls to the constructor List(e,l).
Reverse a List
Given a List L1 = [1 2 3], L1.reverse() delivers a new List [3 2 1]. The method is a bit more complicated than previous methods. Ideally, we'd like to define a method reverse that acts on a list. To do that we need a helper function, which I've called rev. Consequently reverse calls rev, and all the work is done in rev.

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;
}

public List reverse()
{
return rev(new List());
}
}```
rev again is tail recursive, resulting in a sequence of calls to the constructor List(e,l), building the resultant list as it goes.
The Test class (java code
The class definition of the List doesn't actually do anything, but it is there to be used. The little program below is a driver program, allowing us to demonstrate most of the features of the List class.

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) ");

while (!command.equals("end"))
{
if (command.equals("sho"))
l1.print();
if (command.equals("len"))
System.out.println(l1.length());
{
BasicIo.prompt("data: ");
l1.print();
}
if (command.equals("ins"))
{
BasicIo.prompt("data: ");
l1 = l1.insert(i);
l1.print();
}
if (command.equals("del"))
{
BasicIo.prompt("data: ");
l1 = l1.delete(i);
l1.print();
}
if (command.equals("rev"))
{
l1 = l1.reverse();
l1.print();
}
BasicIo.prompt("Type in command: ");
}
}
}```
Note
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.

Benefits and Costs of the linked List
• 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.

Missing Methods?
I guess the following methods are missing, and might be implemented.
• 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.

Confessions
I write this on July the 2nd 1998. I wrote my first "Hello World" program in java less than 7 days ago. So, although I've been educated until I am daft, I am still on a steep learning curve (java on the y-axis, time on the x-axis). I make claim that I cannot use null as the empty list. This might be wrong. If you can correct this, then please do, and let me know how to do it.