Java Data Structures - Contents

Doubly Linked Lists (with Enumeration)...

    Doubly linked lists are not much different from singly linked lists; we just have an extra pointer to worry about. As usual, if you don't understand something, it help to draw it out on paper. Yeah, go ahead and draw a linked list, then go through the operations by drawing or erasing links.

    Anyway, lets get right to the point, and write it.

import java.lang.String;
import java.io.*;
import java.util.*;
import pTwoChildNode;

public class pDoublyLinkedList{

    private pTwoChildNode head,tail;
    protected long num;

    protected pTwoChildNode getHead(){
        return head;
    }

    protected pTwoChildNode getTail(){
        return tail;
    }

    protected void setHead(pTwoChildNode p){
        head = p;
    }

    protected void setTail(pTwoChildNode p){
        tail = p;
    }

    public pDoublyLinkedList(){
        setHead(new pTwoChildNode());
        setTail(new pTwoChildNode());
        getTail().setLeft(head);
        getHead().setRight(tail);
        num = 0;
    }

    public long size(){
        return num;
    }

    public boolean isEmpty(){
        return num == 0;
    }

    public void addHead(Object o){
        pTwoChildNode p = new pTwoChildNode(o);
        p.setLeft(getHead());
        p.setRight(getHead().getRight());
        getHead().setRight(p);
        p.getRight().setLeft(p);
        num++;
    }

    public Object removeHead(){
        Object o = null;
        if(!isEmpty()){
            pTwoChildNode p = getHead().getRight();
            getHead().setRight(p.getRight());
            p.getRight().setLeft(getHead());
            o = p.getData();
            num--;
        }
        return o;
    }

    public void addTail(Object o){
        pTwoChildNode p = new pTwoChildNode(o);
        p.setRight(getTail());
        p.setLeft(getTail().getLeft());
        getTail().setLeft(p);
        p.getLeft().setRight(p);
        num++;
    }

    public Object removeTail(){
        Object o = null;
        if(!isEmpty()){
            pTwoChildNode p = getTail().getLeft();
            getTail().setLeft(p.getLeft());
            p.getLeft().setRight(getTail());
            o = p.getData();
            num--;
        }
        return o;
    }

    public void add(Object o){
        addHead(o);
    }

    public Object remove(){
        return removeHead();
    }

    public Enumeration elementsHeadToTail(){
        return new Enumeration(){

            pTwoChildNode p = getHead();

            public boolean hasMoreElements(){
                return p.getRight() != getTail();
            }

            public Object nextElement(){
                synchronized(pDoublyLinkedList.this){
                    if(hasMoreElements()){
                        p = p.getRight();
                        return p.getData();
                    }
                }
                throw new NoSuchElementException(
                    "pDoublyLinkedList Enumeration");
            }
        };
    }

    public Enumeration elementsTailToHead(){
        return new Enumeration(){

            pTwoChildNode p = getTail();

            public boolean hasMoreElements(){
                return p.getLeft() != getHead();
            }

            public Object nextElement(){
                synchronized(pDoublyLinkedList.this){
                    if(hasMoreElements()){
                        p = p.getLeft();
                        return p.getData();
                    }
                }
                throw new NoSuchElementException(
                    "pDoublyLinkedList Enumeration");
            }
        };
    }

    public static void main(String[] args){
        pDoublyLinkedList list = new pDoublyLinkedList();
        int i;
        System.out.println("inserting head:");
        for(i=0;i<5;i++){
            Integer n = new Integer((int)(Math.random()*99));
            list.addHead(n);
            System.out.print(n+" ");
        }
        System.out.println("\ninserting tail:");
        for(i=0;i<5;i++){
            Integer n = new Integer((int)(Math.random()*99));
            list.addTail(n);
            System.out.print(n+" ");
        }
        System.out.println("\nhead to tail print...");
        Enumeration enum = list.elementsHeadToTail();
        while(enum.hasMoreElements())
            System.out.print(((Integer)enum.nextElement())+" ");
        System.out.println("\ntail to head print...");
        enum = list.elementsTailToHead();
        while(enum.hasMoreElements())
            System.out.print(((Integer)enum.nextElement())+" ");
        System.out.println("\nremoving head:");
        for(i=0;i<5;i++){
            Integer n = (Integer)list.removeHead();
            System.out.print(n+" ");
        }
        System.out.println("\nremoving tail:");
        while(!list.isEmpty()){
            Integer n = (Integer)list.removeTail();
            System.out.print(n+" ");
        }
        System.out.println("\ndone ;-)");
    }
}

    The above code both implements the doubly linked list, and tests it. The code also uses pTwoChildNode object we've developed earlier. (It is simply a node with two children ;-) Output from the above program follows:

inserting head:
0 39 33 14 51
inserting tail:
42 25 76 43 56
head to tail print...
51 14 33 39 0 42 25 76 43 56
tail to head print...
56 43 76 25 42 0 39 33 14 51
removing head:
51 14 33 39 0
removing tail:
56 43 76 25 42
done ;-)

    You can try tracing the output (it helps sometimes), or you can just look at the source and see what's happening. The testing procedure should seem like second nature by this time...

    The list is built around two dummy nodes, the head and tail. These are created at the time of the constructor call, and remain valid until the class gets swept away by garbage collection (when it goes out of scope). The addHead() method simply inserts the new node right after the head dummy node, and addTail() right before the tail node. The remove functions do their appropriate functions.

    There really isn't much to explain; just look at the source, and you'll figure it out (there is nothing here more complex than what you've already seen). What you should be curious about is the elementsHeadToTail() and elementsTailToHead() methods. These methods return an Enumeration object of the java.util package.

    The Enumeration object is created (and declared), inside the functions! (don't you just love Java?) All this object contains is a pointer to a node inside the list. The java.util.Enumeration interface has two functions, and we simply use these two functions to make it possible to step through the elements of the list. If you've ever used iterators in C++, or used java.util.Enumeration object with java.util.Vector, then this should be pretty easy to comprehend.

    This step-through-the-list method is fairly safe, since we're not giving away the safety of our list structure, and we're controlling everything (the user can't just access protected members of the list class, yet the user gets a fairly fast and efficient way to loop through every element of the list as if they were able to access the inside elements of the list.) This code is much more superior to the Object peek(int) method we used in previous lists.

    The main point of this section was not to show you one particular implementation, but to help you realize that linked lists are much more flexible than it is evident from their first appearance.

Back to Table of Contents

Free eBook - Interview Questions: Get over 1,000 Interview Questions in an eBook for free when you join JobsAssist. Just click on the button below to join JobsAssist and you will immediately receive the Free eBook with thousands of Interview Questions in an ebook when you join.

• Free Tutorials - HTML, Java, SQL, PHP, ASP, Perl, SQL Tutorials
• Discuss Programming Problems and Freshers Jobs related issues here.
• Discuss Final Year Project Ideas here.