Linked lists: Sets using Lists

Linked data structures

We now consider the idea of linked data structures. A linked data structure usually involves an object type which has a field of the same type within it, in other words a recursive type. Less usually it could involve the equivalent of indirect recursion, for example, an object which has a field of another type and that other type has a field of the first type.

The simplest linked data structure is the linked list. A linked list consists of an object with two fields, the first a piece of data, the second a linked list. As for simplicity we concentrated on sets of integers, so for simplicity we will concentrate on linked lists of integers, though the data could actually be of any type. So our linked list consists of an integer and a linked list, and the linked list which is part of it consists of an integer and a linked list, and the linked list which is part of that consists of an integer and a linked list ... and so on. While it seems this must go on for ever, we need to remember that an object field can be set to refer to an object or set to null meaning it is not set to refer to anything. This is the equivalent of the base case in recursion. We do not follow an endless chain of linked lists because eventually we will come to one set to null and thus come to a halt. Actually, we could have a linked list structure which is endless, but not infinite, since a list can point back to a cell which is already part of the list, creating a circular structure.

Here is the class for a linked list:

class Cell
{
 int first;
 Cell next;

 Cell(int f,Cell n)
 {
  first=f;
  next=n;
 }
}

Cell c1, c2, c3;

c1 = new Cell(5,c2);

The object that c1 refers to has two parts, and as they are not private to the object, they can be treated just like variables called c1.first and c1.next. The lack of a line around the boxes representing these fields shows they are not protected by being private to the object. Note that the arrows always point to the whole object even if it is shown to have separate parts; in Java (unlike C) there is no concept of a pointer to part of an object. The constructor sets c1.first to 5 and c1.next to refer to the same object that c2 refers to. But we can change either of them. If we first execute:

c1.first = 8;

If we then execute

c1.next = c3;

Of course, the objects that c2 and c3 refer to are themselves cells with two parts. Suppose we now execute:

c3 = new Cell(10,null);

Note that although c3 now refers to a new object, c1.next continues to refer to the object it was pointing to, which is the object c3 used to refer to. The diagonal line across the second part of the object c3 refers to is used to indicate an object value which is set to null.

Now if we execute

c1.next = c3;

The object that c1.next originally pointed to is not drawn because now none of the variables here point to it. If nothing at all points to it, the Java interpreter will remove the space allocated to it altogether, allowing it to be reused, a process known as garbage collection.

If after this we set c3.next to refer to a new Cell object, for example by executing:

c3.next = new Cell(4,null);

It can be seen that even though c1 wasn't mentioned in the last statement, what it refers to is changed by it, because c1 refers to an object that refers to the object that c3 refers to, and that object was changed.

Following the links here, we can think of c1 as referring to a list [8,10,4]. This is why this sort of data structure is called a "linked list".

Representing sets by linked lists

class IntSet11
{
// Destructive Set class, sets stored as unordered linked lists

 Cell list;

 public void delete(int n)
 {
  if(list!=null)
     if(list.first==n)
        list=list.next;
     else
        {
         Cell ptr;
         for(ptr=list; ptr.next!=null&&ptr.next.first!=n; ptr=ptr.next) {}
         if(ptr.next!=null)
            ptr.next=ptr.next.next;
        }
 }

 public void add(int n)
 {
  Cell ptr;
  for(ptr=list; ptr!=null&&ptr.first!=n; ptr=ptr.next) {}
  if(ptr==null)
     list = new Cell(n,list);
 }

 public boolean member(int n)
 {
  Cell ptr;
  for(ptr=list; ptr!=null&&ptr.first!=n; ptr=ptr.next) {}
  return (ptr!=null);
 }

 private static class Cell
 {
  int first;
  Cell next;

  Cell(int f,Cell n)
  {
   first=f;
   next=n;
  }
 }

 public String toString()
 {
  String str="{";
  if(list!=null)
     {
      str+=list.first;
      for(Cell ptr=list.next; ptr!=null; ptr=ptr.next)
          str+=","+ptr.first;
     }
  return str+"}";
 }

}

One new thing here is that the class Cell is actually inside the class IntSet11. To make this quite clear, it is put between the method member and the method toString, although this is just for demonstration and it would be more normal practice to put it either before or after all the methods. This is a simple example of a nested class (sometimes referred to as an "inner class" though that term is often used only for certain sorts of nested classes). The class is declared as private which means it cannot be used outside the class IntSet11 where it is declared. Nested classes can be declared as static or not, just like methods and fields in classes. If an inner class is declared as static, as Cell is, it cannot refer to non-static methods or non-static fields of the class. Making a class a nested class is a way of indicating it exists only in order to be used within its enclosing class.

There is no constructor given for the class IntSet11. If there is no constructor for a class it is given a default constructor. The default constructor for any class has no arguments and sets all numerical fields in the new object created to 0 and all object fields to null. So new IntSet11() will create a new IntSet11 object, with its field called list, which is of type Cell set to null. An IntSet11 object with its list field set to null represents the empty set (the set with no integers in it). It can be seen that the add method just adds the new number to the front of the list of numbers representing the set. So the list does not store the numbers in any particular order. It is, however, necessary to test first whether the number is already in the list, if it is it us not added again at the front (otherwise the delete method wouldn't work properly, because deleting one cell containing the number wouldn't delete the other).

The other methods use the technique of setting a variable to refer to each of the items in the list in turn, moving down the list until either it reached the end of the list or it reaches some point where it needs to halt. Consider the loop in the method member:

for(ptr=list; ptr!=null&&ptr.first!=n; ptr=ptr.next) {}

The code for delete simply sets the list field of the IntSet11 object to the next field of the Cell object it is pointing to if it happens that the number to be deleted is at the front of the list. Otherwise, it moves ptr until it references the Cell before the one to be deleted. For example, if we want to delete 4 from the list representing [5,8,3,4,7], the variable ptr is made to move down the list until it points to the Cell object storing 3:

Now executing ptr.next=ptr.next.next will set the next field of the cell ptr is referencing, that is the cell holding 3, to be equal to the next field of the cell that ptr.next was originally referring to, that is to refer to the cell holding 7. Since the cell holding 3 is part of the list which starts at the field list of the IntSet11 object, the effect of this is to cut the cell holding 4 out of the list:

In fact, since nothing points to the cell holding 4, we can think of it as disappearing and being recycled in garbage collection:

Note that in these "cells and pointers" diagrams, the actual placing of the cells and shape of the lines does not mean anything. All that matters is where the lines representing pointers come from (individual variables or fields within cells) and where they point to (whole cells).

When we are deleting, an additional check needs to be made that ptr is not pointing to the last cell of the list. If it is, then ptr has been moved right through the list and the number to be deleted has been found not to be present in the list.

Representing sets by ordered linked lists

For illustration, here is come code that represents sets by ordered linked lists:

class IntSet12
{
// Destructive Set class, sets stored as ordered linked lists

 Cell list;

 public void delete(int n)
 {
  if(list!=null)
     if(list.first==n)
        list=list.next;
     else
        {
         Cell ptr;
         for(ptr=list; ptr.next!=null&&ptr.next.first<n; ptr=ptr.next) {}
         if(ptr.next!=null&&ptr.next.first==n)
            ptr.next=ptr.next.next;
        }
 }

 public void add(int n)
 {
  if(list==null)
     list = new Cell(n,null);
  else if(n<list.first)
     list = new Cell(n,list);
  else
     {
      Cell ptr;
      for(ptr=list; ptr.next!=null&&ptr.next.first<n; ptr=ptr.next) {}
      if(ptr.next==null||ptr.next.first>n)
         ptr.next = new Cell(n,ptr.next);
     }
 }

 public boolean member(int n)
 {
  Cell ptr;
  for(ptr=list; ptr!=null&&ptr.first<n; ptr=ptr.next) {}
  return (ptr!=null&&ptr.first==n);
 }

 public String toString()
 {
  String str="{";
  if(list!=null)
     {
      str+=list.first;
      for(Cell ptr=list.next; ptr!=null; ptr=ptr.next)
          str+=","+ptr.first;
     }
  return str+"}";
 }

 private static class Cell
 {
  int first;
  Cell next;
  
  Cell(int f,Cell n)
  {
   first=f;
   next=n;
  }
 }
}

for(ptr=list; ptr.next!=null&&ptr.next.first<n; ptr=ptr.next) {}

Then executing ptr.next = new Cell(n,ptr.next) where n holds 5 gives:

Deletion is similar to deletion from a non-ordered list, except if the pointer is moved to a position where the cell referenced by the next field of the cell referenced by the pointer holds a number greater than the number being deleted, we know that number cannot be in the list. So in the simple form of sets we have been considering, we leave the situation unchanged and do not report any error or exceptional condition.

Copying linked lists

class IntSet11a extends IntSet11
{
 public IntSet11a()
 {
  super();
 }

 private IntSet11a(Cell l)
 {
  list=l;
 }

 public IntSet11a copy()
 {
 Left blank for now
 }
}

As in our previous example, we have a private constructor which takes the data structure used to represent the new set as its argument, and creates a new object around that data structure. If the following code were used for the copy method:

 public IntSet11a copy()
 {
  Cell list1=list;
  return new IntSet11a(list1);
 }

s2=s1.copy();

So we have two separate objects, referred to by s1 and s2, each with their own list field. But the list fields refer to the same Cell object. Since the delete method alters the linked list of a set object, calling, for example

s1.delete(4);

What we need is to copy the list completely, so that calling s2=s1.copy() will result in the list field of s2 referring to a list of cells with the same contents as that of s1 but not actually the same cells, that is, using our previous example:

The following code for copy will achieve this:

 public IntSet11a copy()
 {
  if(list==null)
     return new IntSet11a(null);
  else
     {
      Cell list1 = new Cell(list.first,null);
      Cell ptr,ptr1;
      for(ptr1=list1,ptr=list; ptr.next!=null; ptr=ptr.next, ptr1=ptr1.next)
         ptr1.next = new Cell(ptr.next.first,null);
      return new IntSet11a(list1);
     }
 }

Then both pointers are advanced down the list, and the process repeated until ptr points to the last cell in its list. The effect is that the copy is built up in the order the cells come. This copy is then used to create a new object using the private constructor.

We shall use the techniques used here to copy a linked list again when we consider implementing a constructive set class using recursion.

Last modified: 4 March 2005