| 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);
}
}
}
|
