Go4Expert

Go4Expert (http://www.go4expert.com/)
-   Java (http://www.go4expert.com/forums/java/)
-   -   Doubly Linked List, help (http://www.go4expert.com/forums/doubly-linked-list-help-t25596/)

Rose123456789 23Apr2011 02:56

Doubly Linked List, help
 
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);
        } 
    }
}


mumba004 28Apr2012 03:11

Re: Doubly Linked List, help
 
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


All times are GMT +5.5. The time now is 12:45.