Introduction To Linked Lists

A list is a ordered sequence of objects or data values. Lists represent a very powerful and flexible means of organizing data. Lists are so flexible that it can be a problem. You will see many different uses of lists in programs all just slightly different. Lists are used in all programming languages - not just object-oriented ones. It helps to begin with an example of simple lists of animal names and then later see how these ideas can be encapsulated using classes.

Consider the following class which is part of a larger program which is presented below.

    class Node<T> { // a Node holding a value of type T and a next reference
     T valu;   Node<T> next; 
     public Node( T s, Node<T> n) { valu = s; next = n; }
    }

Note that a Node object consists of a valu and a reference to another (next) Node. The next Node will contain a reference to another one and so on. The last Node in a list will have a null next reference which has the effect of terminating the list.

Now consider the following code which creates three Node objects each containing a reference to the previous one.

      Node tail = new Node( "fox", null);
      Node mid  = new Node( "dog", tail );
      Node head = new Node( "bat", mid);

This is a simple list of three valus(bat, dog, fox). The tail Node has null for a next reference terminating the sequence.

Now consider the following loop which prints out all the valus in the list in order from head to tail:

      for( Node p = head; p != null; p = p.next )
        System.out.print( p.valu + " " );
      System.out.println();

In this loop the variable p is assigned the reference values (head, mid, tail, null). When p == null the loop terminates. The effect is to print out the valus:( bat, dog, fox ) each followed by a space. In the complete program which appears below this loop is written as a method called output.

Lists are extremely flexible. It is a simple matter to insert a new Node at the end or in the middle or at the front of a list:

 

      tail.next = new Node( "gnu", null);
      mid .next = new Node( "emu", mid.next);
      head.next = new Node( "cat", head.next);
      head      = new Node( "ape", head);

If we now output the list using the same loop as before we will get seven animals valus ( ape bat cat dog emu fox gnu ).

It is also a simple matter to delete nodes from a list:

      mid.next = mid.next.next;  // delete valu after dog

Now the output would be: ( ape bat cat dog fox gnu ). Note that the emu Node has been deleted. In most languages such as C++ we would have to be very careful to recycle the memory containing Nodes which are removed from a list. Java has a "garbage collection" process which will find such deleted objects and make the memory available for new objects. This simplifies the programmer's job considerably.

One of the peculiar features of lists is that it is most convenient to construct them "right to left" with the last valu to be inserted appearing first in the list. It is not hard to make a copy of a list in reverse order:

      Node rev = null;
      for( Node p = head; p != null; p = p.next )
        rev = new Node( p.valu, rev );

If we output the list beginning with rev we get: gnu fox dog cat bat ape.

It is also possible to construct a list from "left to right" if you are careful to keep track of the Node which is currently last in the list. The following code shows how to read valus from standard input and store them in the same order in a list whose first Node is stored in the reference variable inList:

      
    Scanner sc = new Scanner( System.in );
    String line;
    Node inList = null;
    if ( sc.hasNextLine() ) {
      inList = new Node( sc.nextLine(), null), last = inList;
      while ( sc.hasNextLine() )
        last = last.next = new Node( sc.nextLine(), null );

The last line contains two assignment statements. In this case the order of the assignments matters(right to left)!

All these code fragments are gathered together into a file Animals.java which you may wish to compile and run.

Exercises

Write a method to calculate the current length of a list.
Write a method to test if a particular valu occurs in a given list.
Write a method to test if a list of valus is in alphabetical order. (If you are "into recursion" it is possible to write this method as just one long statement!)
Write a method to insert a valu into an ordered list so that it remains ordered.
Write a method to traverse a given list inserting each valu into a second list (initially empty) ending up with a sorted copy of the list. This is called insertion sort. Show that it is O(n*n) where n is the length of the given list.
Modify the given program to read in lines of text containing a valu followed by a semicolon and then an address and store the information in a list where the valus and addresses are stored as separate strings. There are two ways to do this. Class Node could have an address field added to it. This is proably the simplest. An alternative approach would be to package valus and addresses as some new kind of object and replace the valu field in class Node by this new kind of object. This is more work but may lead to a better program. Try it both ways. In either case you must be able to print out the list.
Add a method to the previous exercise to check if more than one person in the list has the same address.
Write a method to merge two alphabetically sorted lists of valus into one combined list.
Write a method to create a list containing the 1st, 3rd, 5th, ... elements of another list.
Write a method to create a list containing the 2nd, 4th, 6th, ... elements of another list.
Write a method which uses the last three methods and performs a merge sort of a given list by splitting it into odd and even sublists and sorting each of them and merging the results into one combined list. This is known as merge sort. It is O(n log n) which is dramatically faster than insertion sort for long lists. Be careful not to use recursion in the case that that there is only one valu in the list.
It is possible that there not be any lines of input. How should the Scanner example be modified to cope with this situation?
Suppose you have file and each line of the file has the valus of two people who are friends(separated by a comma). For example,
```
    Kevin, Mike
    Denis, Kevin
    Carolyn, Kevin
    ...
```
Write a program to read such data and print out in alphabetical order the names of all the people one per line each followed by the names of the people they are friends with (also ordered). E.g.:
```
    Carolyn: Kevin
    Denis: Kevin
    Kevin: Carolyn, Denis, Mike
    Mike: Kevin
```
To do this you will need a list of person objects each of which has a list of friend objects.