Notes 6

More Abstract Data Types

Singly Linked Lists

The list implementations we have seen have a single link between each node. This is a very common kind of list structure. The overhead is low and the code is simple. However there are difficulties in insertions and deletions. In these operations, we need to have access to the node that comes before the node we want to delete. One way to handle this is to use a different structure.

Double Linked Lists

Adding a second link between nodes makes the insertion and deleting code simpler. In this design, each node has a link to the node after it and the node before it. Once I find a node, it is easy to insert nodes before or after it and to delete it.

Lists with header nodes

One remaining problem is how to handle insertion and deletion when the list is empty or there is just one element. One way to further simplify the problem. We can add a separate special node that is at the front of the list. This contains the pointer to the first actual node of the list and can have other information as well. We could store the length of the list in here to avoid the cost of the loop to count nodes. We could also store a second pointer to the end of the list. This would make operations like adding a node at the end much easier. This next sample code builds a list that includes all these ideas. The code is also here

The listdata class is only slightly changed to add a second pointer.


/**
 * This is an intermediate class that holds the data and pointer
 * 
 * @author Kent Archie 
 * @version 1/29/2002
 */
import data;

public class listdata
{
    private data d;   // the data element in this node
    private listdata next;   // the pointer to the next one
    private listdata prev;   // the pointer to the previous one     

    /** Constructor for objects of class ListData */
    public listdata() { d=null; next=null; prev=null; }
    public listdata(data other) { d=other; next=null; prev=null;}

    public listdata getNext() { return next; }
    public void setNext(listdata v) { next = v;}
    public listdata getPrev() { return prev; }
    public void setPrev(listdata v) { prev = v;}
    
    public data getData() { return d;}
    public void setData(data x) { d=x;}
} // class ListData

The llist class serves as the header record in some senses but not in others. This means that it holds pointers to both the head and tail and the length but the first element on the list doesn't point to it. This is mostly important in the delete method.

/**
 * This is an implementation of the list container using linked lists
 * 
 * @author Kent Archie
 * @version 1/27/2002
 */
import data;
import listdata;

public class llist
{
    private listdata Head;  // first entry in this list
    private listdata Tail;  // last entry in this list
    private int Length;     // the number of nodes in the list

    /** Constructor for objects of class llist */
    public llist()
    {
        Head=null; Tail=null; Length=0;
    }
     
     /* We make a listdata node first. If there is no memory, we return false.
        Later this will be changed to use exceptions.
        Adding to the front is easy since we just set the head pointer
        to the new element and set the new elements next field to point
        to whatever the list head pointed to.
        If the head is null, it still works the way we want.
    */
    public boolean addToFront(data d)
    {
        listdata my_l=new listdata(d);
        if( my_l == null) return false;  // no memory
        my_l.setNext(Head);  // leave the prev pointer null
        if(Head != null) Head.setPrev(my_l);
        if(Tail == null) Tail = my_l;  // first one
        Head = my_l;
        Length++;
        return true;
    } // addToFront
    
    /*  Like addToFront(), we first create a listdata node and
        add the data to it.
        Then we have to find the last element of the list.
        We do this in a loop where we check if the pointer is null
        and if it isn't, check if its next is null.
        We want to stop when the pointer is referring to the last element.
        If the pointer is null when we leave the loop, then the list was
        empty and we just point the Head pointer at it.
        Otherwise, we change the next pointer of the last one to point
        to the one we just added.
    */
    public boolean addToEnd(data d)
    {
        listdata my_l;
        if( (my_l = new listdata(d)) == null) return false;  // no memory
        Length++;
        // if the tail pointer is null, so must the head pointer
        if(Tail == null)
           Head = Tail = my_l; // first entry
        else {
            Tail.setNext(my_l);  // make the last one point to the new one
            my_l.setPrev(Tail);
            Tail = my_l;
        }
        return true;    
    }  // addToEnd
    
    public int getLength() { return Length; }

    /* we will provide 2 interfaces for searching.
       One will take two integers and make a data object.
       The other will take a data object.
       Both will simply call the search routine to do the actual work.
       These are provided as a convenience to the user.
    */
    public listdata find(int a, int b) { return search(new data(a,b)); }
    public listdata find(data target) { return search(target); }

    /*  We start at the front of the list and look at each element
        checking if the data item stored there is the same as
        one we passed in.
    */
    private listdata search(data target)
    {
        for(listdata lptr = Head; lptr != null; lptr = lptr.getNext())
            if(lptr.getData().equals(target))
                return lptr;
        return null; // if we get here, we didn't find it
    } // find
    
    // walk the list and print each data item
    public void printList()
    {
        for(listdata lptr = Head; lptr != null; lptr = lptr.getNext())
            System.out.println(lptr.getData());
    } // printList

    /*  addBefore() takes two data objects as parameters.
        The first (target) is used as the parameter to the search routine.
        If we find the node, we insert the second (newone) before the found one.
    */
    public boolean addBefore(data target,data newone)
    {
        listdata t;
        if( ( t = search(target)) == null)
            return false;  // didn't find it
        // t now points to the target node in the list
        listdata n = new listdata(newone);
        Length++;
        n.setPrev(t.getPrev());    // n to prev
        n.setNext(t);              // n to t
        (t.getPrev()).setNext(n);  // prev to n
        t.setPrev(n);              // t to n
        return true;
    } // addBefore

    /*  addAfter() takes two data objects as parameters.
        The first (target) is used as the parameter to the search routine.
        If we find the node, we insert the second (newone) after the found one.
    */
    public boolean addAfter(data target,data newone)
    {
        listdata t;
        if( ( t = search(target)) == null)
            return false;  // didn't find it
        // t now points to the target node in the list
        listdata n = new listdata(newone);  // make a new node
        Length++;
        n.setNext(t.getNext());    // n to target next
        n.setPrev(t);              // n to t
        (t.getNext()).setPrev(n);  // target next to n
        t.setNext(n);              // t to n
        if( t == Tail) Tail = n;
        return true;
    } // addAfter

    public boolean delete(data target)
    {
        listdata t;
        if( ( t = search(target)) == null)
            return false;  // didn't find it
        // t now points to the target node in the list
        // some special cases are handled first
        // first (or only) one
        Length--;
        if(Head == t) {
            System.out.println("Deleting first node");
            if(t.getNext() != null) {
                (t.getNext()).setPrev(null); // new first one
            }
            Head = t.getNext();
            return true;
        } // head == t

        // last one
        if(Tail == t) {
            System.out.println("Deleting last node");
            Tail = Tail.getPrev();
            Tail.setNext(null);
            return true;
        }  // Tail == t

        // now the general case where it is between to other nodes
        System.out.println("Deleting middle node");
        (t.getPrev()).setNext(t.getNext());  // prev to next
        (t.getNext()).setPrev(t.getPrev()); // next to prev
        return true;
    } // delete
    
    // return the first object from the list
    public listdata getFirst() { return Head;}
    
    /*  first set the second (if there is one) to be the new first.
        Then point the head to this one.
        If  the list is now empty, fix the tail pointer.
    */
    public void chop()
    {
        System.out.println("starting chop");
        if(Head == null) return;
        if(Head.getNext() == null) {
            Head = Tail = null;
            Length=0;
            return;
        }
        (Head.getNext()).setPrev(null);
        Head = Head.getNext();
        Length--;
    } // chop
} // class llist
Here is the driver class and the results from running it.

/**
 * Driver for the array implementation of a list
 * 
 * @author Kent Archie 
 * @version 1/27/2002
 */
import llist;

public class main
{
    public static void main(String[] args)
    {
        llist joe = new llist();
        joe.addToFront(new data(1,42));
        joe.addToFront(new data(2,43));
        joe.addToEnd(new data(3,44));
        joe.printList();
        System.out.println("There are " + joe.getLength() + " items in the list");
        look(joe,1,42);
        look(joe,2,43);
        look(joe,2,454);

        System.out.println("\nAdding before (3,44)");
        if(joe.addBefore(new data(3,44), new data(4,44)))
            System.out.println("target found");
        else
            System.out.println("target not found");
    
        System.out.println("after addBefore");
        joe.printList();
        System.out.println("There are " + joe.getLength() + " items in the list");

        System.out.println("\nAdding after (2,43)");
        if(joe.addAfter(new data(2,43), new data(5,45)))
            System.out.println("target found");
        else
            System.out.println("target not found");
    
        System.out.println("after addAfter");
        joe.printList();
        System.out.println("There are " + joe.getLength() + " items in the list");
        
       System.out.println("\nDeleting (5,45)");
       if(joe.delete(new data(5,45)))
            System.out.println("target found");
        else
            System.out.println("target not found");
    
        System.out.println("after delete");
        joe.printList();
        System.out.println("There are " + joe.getLength() + " items in the list");

        System.out.println("\nDeleting first (2,43)");
        if(joe.delete(new data(2,43)))
            System.out.println("target found");
        else
            System.out.println("target not found");
    
        System.out.println("after delete");
        joe.printList();
        System.out.println("There are " + joe.getLength() + " items in the list");

        System.out.println("\nDeleting last (3,44)");
        if(joe.delete(new data(3,44)))
            System.out.println("target found");
        else
            System.out.println("target not found");
    
        System.out.println("after delete");
        joe.printList();
        System.out.println("There are " + joe.getLength() + " items in the list");
        
        System.out.println("\nGetting the first one");
        listdata l = joe.getFirst();
        if(l == null)
            System.out.println("There is no first one");
        else {
            System.out.println("The first one is " + l.getData());
        }

        System.out.println("There are " + joe.getLength() + " items in the list");
        System.out.println("\nDeleting the first one");
        joe.chop();
        joe.printList();
        System.out.println("There are " + joe.getLength() + " items in the list");
    } // main

    // look for the item indicated in the list passed. print results
    private static void look(llist l, int a, int b)
    {
        listdata results = l.find(new data(a,b));
        if(results != null)
            System.out.println("Item(" + a + "," + b  + ") found");
        else
            System.out.println("Item(" + a + "," + b  + ") not found");
    } // look
}  // class main


target found
after addAfter
x= 2 y= 43
x= 5 y= 45
x= 1 y= 42
x= 4 y= 44
x= 3 y= 44
There are 5 items in the list

Deleting (5,45)
Deleting middle node
target found
after delete
x= 2 y= 43
x= 1 y= 42
x= 4 y= 44
x= 3 y= 44
There are 4 items in the list

Deleting first (2,43)
Deleting first node
target found
after delete
x= 1 y= 42
x= 4 y= 44
x= 3 y= 44
There are 3 items in the list

Deleting last (3,44)
Deleting last node
target found
after delete
x= 1 y= 42
x= 4 y= 44
There are 2 items in the list

Getting the first one
The first one is x= 1 y= 42
There are 2 items in the list

Deleting the first one
starting chop
x= 4 y= 44
There are 1 items in the list