Doubly Linked List, help

Rose123456789's Avatar, Join Date: Apr 2011
Newbie Member
This is incomplete, its suppose to be a doubly linked list, though im having a hard time turning it into one, if you could then I could go through and better understand, many thanks.

Code:
import java.util.*;
/**
 * This is an example for CS 1410 - It is a simple
 * Queue data structure implemented using a
 * singly-linked list. <p>
 *
 * This example demonstrates linked lists and generics.
 * It has been fully commented and reorganized for clarity. <p>
 * 
 * Note - any data of any single type can be stored in this list,
 * including null.  Care must be taken because data values
 * may be null.  (I have added code to handle this in the
 * Node inner class.)
 *
 * @author Peter A Jensen 
 */
public class Queue<E> 
{
    // Instance variables
    
    private Node head;  // Points to (refers to) the first node in the list, or null if none.
    private Node tail;  // Points to (refers to) the last node in the list, or null if none.
    
    private int size;   // The number of elements (nodes) in the list.
    
    /**
     * This constructor initializes the queue to an empty
     * state.  (The head and tail reference 'null', and the
     * size is set to 0.)
     */
    public Queue ()
    {
    	
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    /**
     * Returns the number of elements in this queue.
     * 
     * @return
     *        the number of elements in this queue
     */
    public int size ()
    {
        return size;
    }
    
    /**
     * Adds an element to the end (the back) of the queue.
     * 
     * @param data
     *            the data to be enqueued
     */
    public void enqueue (E data)
    {
        // Create a new node with the data.  This node
        //   will be linked in to the list at the end of the list.
        
        Node n = new Node (data);
        
        // If the list is not empty, just link the new node
        //   in after the tail.
        
        if (tail != null)
            tail.next = n;
            
        // The end of the list is changed to reference the new node.
        
        tail = n;
        
        // If the list was empty, the head should also reference this new node.
        
        if (head == null)
            head = n;
        else
        	head.next =n;//added by me---
            
        // The list has had a node added - increase its size.    
            
        size++;
    }
    
    
    /**
     * Removes an element from the start (the front) of the queue.
     * 
     * @return
     *        the data stored at the start of the queue
     * 
     * @throws NoSuchElementException
     *                               if the queue is empty
     */
    public E dequeue ()
    {
        // If the queue is empty, throw an exception.
        
        if (size == 0)
            throw new NoSuchElementException("Cannot remove an element from an empty queue.");
        
        // Get the data from the node at the front of the list.  Note that we know
        //   the head will be non-null, the queue is not empty if we get here.
            
        E temp = head.data;
        
        // Point the head to the next node in the list.  This causes the first node
        //   to become unreferenced, and it will be discarded by the garbage collector.
        
        head = head.next;
        
        // The list has shrunk, change the size.
        
        size--;
        
        // If the list is now empty, both the head and tail should point to null.
        //   (Note that the head already would contain null, we don't need to change it again.)
        
        if (size == 0)
            tail = null;
            
        // Return the data that was stored at the front of the queue.    
            
        return temp;
    }
    
    /**
     * Removes the specified element from the list.  If the
     * data does not exist in the list, the queue is not changed.
     * If the data occurs multiple times in the list, only
     * the first occurrence is removed.
     * 
     * @param data
     *            the data element to be removed
     */
    public void remove (E data)
    {
        // Keep track of a 'current' node (or position) in the list, as
        //   well as the node that links to this node.
        
        Node current = head;
        Node previous = null;
        
        // As long as 'current' has not reached the end of the list, and
        //   as long as it is not referencing a node that contains the
        //   data we want to remove, loop and advance through the list.
        
        while (current != null && !current.containsData(data))
        {
            previous = current;
            current = current.next;
        }
        
        // If the element was not found, bail.
        
        if (current == null)
            return;
        
        // If the element was at the start of the list, just advance
        //   the head.  Otherwise, unlink it from the list.
            
        if (previous == null)
            head = current.next;
        else
            previous.next = current.next;
            
        // An element has been removed, adjust the size appropriately.    
            
        size--;
        
        // If the last element was removed, adjust the tail appropriately.
        
        if (current == tail)
            tail = previous;
    }
    
    /**
     * Inserts the specified element into the list immediately before 
     * the specified placeholder data.  If the placeholder data is not 
     * in the list, no action is taken.  The inserted data element will be 
     * nearer to the start of the list than the placeholder.  If the
     * placeholder element occurs multiple times in the list, the
     * data element will be inserted before the first occurrence of the
     * placeholder.
     * 
     * @param placeholder
     *                   the data element to search for
     * 
     * @param data
     *            the data element to insert
     */
    public void insertBefore (E placeholder, E data)
    {
        // We did not write this method during class - you
        //   will need to write it as part of the assignment.
    	if(head==null)
    	{
    		head= new Node(data);
    		tail= head;
    	}
    	else
    	{
    		
    	}
    	size++;
    }
    
    
    /**
     * Inserts the specified element into the list immediately after 
     * the specified placeholder data.  If the placeholder data is not 
     * in the list, no action is taken.  The data element will be 
     * nearer to the end of the list than the placeholder.  If the
     * placeholder element occurs multiple times in the list, the
     * data element will be inserted after the first occurrence of the
     * placeholder.
     * 
     * @param placeholder
     *                   the data element to search for
     * 
     * @param data
     *            the data element to insert
     */
    public void insertAfter (E placeholder, E data)
    {
        // We did not write this method during class - you
        //   will need to write it as part of the assignment.
    }
    
    
    /**
     * This class defines 'node' objects, which are the
     * parts of the linked list used in the queue class above.
     * A single Queue object may create and link together
     * many Node objects.  <p>
     * 
     * Note that this class is inside of the Queue class.
     * The class is private because we only want to use it
     * within the Queue class. <p>
     * 
     * In the in-class demo, nodes were designed to be singly-linked
     * (forward only).  This assignment requires you to convert
     * the Queue and the Node classes to use / represent a
     * doubly-linked list.  Nodes will have two references, one that
     * points forwards, and one that points backwards. <p>
     * 
     * @author Peter Jensen
     */
    private class Node
    {
        // Instance variables.
        
        private E data;         // The data stored in the node.
        private Node next;
        private Node previous;// A reference to the next node in the list, or null if none.
        
        /**
         * Creates a node containing the specified data,
         * and linking to nothing.
         * 
         * @param data
         *            the data to store in this node
         */
        public Node (E data)
        {
            this.data = data;
            this.next = null;
        }
    
        /**
         * Returns the data stored in this node.
         * 
         * @return
         *        the data stored in this node
         */
        public E getData ()
        {
            return data;
        }
    
        /**
         * Returns the Node object that follows this
         * Node object.  This method is used to traverse
         * the linked list.
         * 
         * @return
         *        the node that follows this node
         */
        public Node getNext()
        {
            return next;
        }
        /**
         * made by me, accessor method to get previous
         */
        public Node getPrevious()
        {
        	return previous;
        }
        /**
         * made by me, mutator method to set previous
         */
        public void setPrevious(Node n)
        {
        	previous=n;
        }
        
        /**
         * Causes this Node object to be linked to
         * the specified node.  The specified node will
         * follow, or come after, this node.
         * 
         * @param n
         *          the node to be placed after this node
         */
        public void setNext(Node n)
        {
            next = n;
        }
        
        /**
         * Returns true if this node contains the specified
         * data.  This is just a helper method to make it easier
         * to allow null values to be stored in the queue.  Nulls
         * can be safely compared with this method.
         * 
         * @param data
         *            a data element to compare to the data in this node
         *            
         * @return 
         *        true if the data elements are equal, false otherwise
         */
        public boolean containsData (E data)
        {
            if (this.data == null || data == null)
                return this.data == data;
            else
                return this.data.equals(data);
        }   
    }
}

Last edited by shabbir; 23Apr2011 at 09:07.. Reason: Code blocks
mumba004's Avatar, Join Date: Apr 2012
Newbie Member
I want to bump this since I also need help with this, and if you have the answer rose1234 could you pm me it ? thanks