Results 1 to 1 of 1
Thread: Linked Lists Queue
- 04-28-2010, 04:40 AM #1
Member
- Join Date
- Mar 2010
- Posts
- 46
- Rep Power
- 0
Linked Lists Queue
I need to complete the insertAfter and also change this to be a double list instead of single, i have it prity much as a single except if you could check on the insertAfter if it is correct... and help me get to do it as a double....
Java Code:package assignment13; import java.util.*; /** * 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. * * */ 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.setNext(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; // 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.getData(); // 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.getNext(); // 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.getNext(); } // 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.getNext(); else previous.setNext(current.getNext()); // 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 after * the specified placeholder element. If the placeholder 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) { 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(placeholder)) { previous = current; current = current.getNext(); } // If the element was not found, bail. if (current == null) return; if (previous == null) head = current.getNext(); else previous.setNext(current.getNext()); // 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; } /** * 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. This * does not cause problems. 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). The next 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 { // Statements not presented in class are commented out. // Please uncomment them to begin the process of // changing the queue to a doubly-linked list. // Instance variables. private E data; // The data stored in the node. private Node next; // 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; } /** * 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); } } }
Similar Threads
-
Concatenate Linked Lists
By tttestall in forum New To JavaReplies: 1Last Post: 04-20-2010, 07:03 PM -
Linked Lists
By vendetta in forum New To JavaReplies: 6Last Post: 01-26-2010, 08:23 AM -
Single linked lists - help
By Srcee in forum New To JavaReplies: 10Last Post: 10-29-2009, 05:35 PM -
Doubly Linked Lists
By stevenson15 in forum New To JavaReplies: 6Last Post: 04-21-2009, 12:35 PM -
question about linked lists
By jkurth in forum Advanced JavaReplies: 1Last Post: 11-11-2007, 08:33 AM


LinkBack URL
About LinkBacks
Reply With Quote
Bookmarks