Verkettete Liste Stack/Queue Implementierung leert sich ohne ersichtlichen Grund?

Question

Ich habe versucht, eine LinkedList-Implementierung eines Stacks und einer Warteschlange zu programmieren. Jedes Mal, wenn ich sie ausführe, erhalte ich einen Fehler, der mich darauf hinweist, dass die Liste leer ist, wenn ich versuche, irgendetwas zu entfernen. Die Sache ist, wenn ich .toString() auf der Liste anrufe, sogar RECHTS vor dem pop/dequeue Befehl, kann ich sehen, dass sie nicht sind. Ich kann selbst nichts falsches mit meiner Pop/Dequeue Implementierung sehen, aber vielleicht können Sie mir gut helfen.

LinkedList.java

package jsjf; 

import jsjf.exceptions.*; 
import java.util.*; 

/** 
* LinkedList represents a linked implementation of a list. 
* 
* @author Java Foundations 
* @version 4.0 
*/ 
public class LinkedList<T> implements ListADT<T>, Iterable<T> 
{ 
    protected int count; 
    protected LinearNode<T> head, tail; 
    protected int modCount; 

    /** 
    * Creates an empty list. 
    */ 
    public LinkedList() 
    { 
     count = 0; 
     head = tail = null; 
     modCount = 0; 
    } 

    /** 
    * Adds a new element to the end of the list. 
    * 
    * @param element the element to add. 
    */ 
    public void add(T element) { 
     // If the list is empty... 
     if(this.tail == null){ 
      // Creates a new node for the new element. 
      LinearNode<T> newElement = new LinearNode(element); 
      // Assigns the new node to be the head and the tail. 
      this.tail = this.head = newElement; 
     } 
     // Otherwise... 
     else { 
      // Temporary caches the old tail. 
      LinearNode<T> temp = this.tail; 
      // Creates a new node for the new element. 
      LinearNode<T> newElement = new LinearNode(element); 
      // Assigns the new node to follow the old tail. 
      temp.setNext(newElement); 
      // Assigns the old tail to precede the new node. 
      newElement.setPrevious(temp); 
      // Assigns the new node to be the tail. 
      this.tail = newElement; 
     } 
    } 


    /** 
    * Adds a new element at a specific index, bumping the current element at 
    * that index to the next index. 
    * 
    * @param index the index to add to. 
    * @param element the element to add. 
    */ 
    public void add(int index, T element) { 
     // Find the node at the index requested. 
     LinearNode<T> desiredIndex = this.head; 
     for(int i = 1; i <= index; i++){ 
      desiredIndex = desiredIndex.getNext(); 
     } 
     // Hold the previous element of the old element. 
     LinearNode<T> prev = desiredIndex.getPrevious(); 
     // Create a new node for the new element. 
     LinearNode<T> newElement = new LinearNode(element); 
     // Assign prev to precede the new element. 
     newElement.setPrevious(prev); 
     // Assign the old element to follow the new element. 
     newElement.setNext(desiredIndex); 
     // Assign the new element to precede the old element. 
     desiredIndex.setPrevious(newElement); 
    } 


    /** 
    * Returns an element from a specific index, without removing it. 
    * 
    * @param index the index to check. 
    * @return the element at that index. 
    */ 
    public T get(int index) { 
     // Find the node at the index requested. 
     LinearNode<T> desiredIndex = this.head; 
     for(int i = 1; i <= index; i++){ 
      desiredIndex = desiredIndex.getNext(); 
     } 
     // Return that element. 
     return desiredIndex.getElement(); 
    } 


    /** Removes the first element in this list and returns a reference 
    * to it. Throws an EmptyCollectionException if the list is empty. 
    * 
    * @return a reference to the first element of this list 
    * @throws EmptyCollectionException if the list is empty 
    */ 
    public T removeFirst() throws EmptyCollectionException 
    { 
     if (isEmpty()) 
      throw new EmptyCollectionException("list"); 

     T result = head.getElement(); 
     head = head.getNext(); 
     count--; 

     if(isEmpty()) 
      tail = null; 

     modCount++; 

     return result; 
    } 


    /** 
    * Removes the last element in this list and returns a reference 
    * to it. Throws an EmptyCollectionException if the list is empty. 
    * 
    * @return the last element in this list 
    * @throws EmptyCollectionException if the list is empty  
    */ 
    public T removeLast() throws EmptyCollectionException 
    { 
     if (isEmpty()) 
      throw new EmptyCollectionException("list"); 

     T result = tail.getElement(); 
     tail = tail.getPrevious(); 
     count--; 

     if(isEmpty()) 
      tail = null; 

     modCount++; 

     return result; 
    } 


    /** 
    * Removes the first instance of the specified element from this 
    * list and returns a reference to it. Throws an EmptyCollectionException 
    * if the list is empty. Throws a ElementNotFoundException if the 
    * specified element is not found in the list. 
    * 
    * @param targetElement the element to be removed from the list 
    * @return a reference to the removed element 
    * @throws EmptyCollectionException if the list is empty 
    * @throws ElementNotFoundException if the target element is not found 
    */ 
    public T remove(T targetElement) throws EmptyCollectionException, 
    ElementNotFoundException 
    { 
     if (isEmpty()) 
      throw new EmptyCollectionException("LinkedList"); 

     boolean found = false; 
     LinearNode<T> previous = null; 
     LinearNode<T> current = head; 

     while (current != null && !found) 
      if (targetElement.equals(current.getElement())) 
       found = true; 
      else 
      { 
       previous = current; 
       current = current.getNext(); 
      } 

     if (!found) 
      throw new ElementNotFoundException("LinkedList"); 

     if (size() == 1) // only one element in the list 
      head = tail = null; 
     else if (current.equals(head)) // target is at the head 
      head = current.getNext(); 
     else if (current.equals(tail)) // target is at the tail 
     { 
      tail = previous; 
      tail.setNext(null); 
     } 
     else // target is in the middle 
      previous.setNext(current.getNext()); 

     count--; 
     modCount++; 

     return current.getElement(); 
    } 


    /** 
    * Changes the element at a specific index. 
    * 
    * @param index the index to change. 
    * @param element the element to change to. 
    */ 
    public void set(int index, T element) { 
     // Find the node at the index requested. 
     LinearNode<T> desiredIndex = this.head; 
     for(int i = 1; i <= index; i++){ 
      desiredIndex = desiredIndex.getNext(); 
     } 
     // Change the element at that index. 
     desiredIndex.setElement(element); 
    } 


    /** 
    * Returns the first element in this list without removing it. 
    * 
    * @return the first element in this list 
    * @throws EmptyCollectionException if the list is empty 
    */ 
    public T first() throws EmptyCollectionException 
    { 
     if (isEmpty()) 
      throw new EmptyCollectionException("list"); 

     T result = head.getElement(); 
     return result; 
    } 


    /** 
    * Returns the last element in this list without removing it. 
    * 
    * @return the last element in this list 
    * @throws EmptyCollectionException if the list is empty 
    */ 
    public T last() throws EmptyCollectionException 
    { 
     if (isEmpty()) 
      throw new EmptyCollectionException("list"); 

     T result = tail.getElement(); 
     return result; 
    } 


    /** 
    * Returns true if the specified element is found in this list and 
    * false otherwise. Throws an EmptyCollectionException if the list 
    * is empty. 
    * 
    * @param targetElement the element that is sought in the list 
    * @return true if the element is found in this list 
    * @throws EmptyCollectionException if the list is empty 
    */ 
    public boolean contains(T targetElement) throws 
     EmptyCollectionException 
    { 
     if(isEmpty()) 
      throw new EmptyCollectionException("list"); 

     boolean found = false; 
     LinearNode<T> previous = null; 
     LinearNode<T> current = head; 

     while (current != null && !found) 
      if (targetElement.equals(current.getElement())) 
       found = true; 
      else 
      { 
       previous = current; 
       current = current.getNext(); 
      } 

     if (!found) 
      throw new ElementNotFoundException("LinkedList"); 

     return found; 
    } 


    /** 
    * Returns true if this list is empty and false otherwise. 
    * 
    * @return true if the list is empty, false otherwise 
    */ 
    public boolean isEmpty() 
    { 
     return (count == 0); 
    } 


    /** 
    * Returns the number of elements in this list. 
    * 
    * @return the number of elements in the list 
    */ 
    public int size() 
    { 
     return count; 
    } 


    /** 
    * Returns a string representation of this list. 
    * 
    * @return a string representation of the list  
    */ 
    public String toString() 
    { 
     String result = ""; 
     LinearNode current = head; 

     while (current != null) 
     { 
      result = result + current.getElement() + "\n"; 
      current = current.getNext(); 
     } 

     return result; 
    } 


    /** 
    * Returns an iterator for the elements in this list. 
    * 
    * @return an iterator over the elements of the list 
    */ 
    public Iterator<T> iterator() 
    { 
     return new LinkedListIterator(); 
    } 


    /** 
    * LinkedIterator represents an iterator for a linked list of linear nodes. 
    */ 
    private class LinkedListIterator implements Iterator<T> 
    { 
     private int iteratorModCount; // the number of elements in the collection 
     private LinearNode<T> current; // the current position 

     /** 
     * Sets up this iterator using the specified items. 
     * 
     * @param collection the collection the iterator will move over 
     * @param size  the integer size of the collection 
     */ 
     public LinkedListIterator() 
     { 
      current = head; 
      iteratorModCount = modCount; 
     } 

     /** 
     * Returns true if this iterator has at least one more element 
     * to deliver in the iteration. 
     * 
     * @return true if this iterator has at least one more element to deliver 
     *   in the iteration 
     * @throws ConcurrentModificationException if the collection has changed 
     *   while the iterator is in use 
     */ 
     public boolean hasNext() throws ConcurrentModificationException 
     { 
      if (iteratorModCount != modCount) 
       throw new ConcurrentModificationException(); 

      return (current != null); 
     } 

     /** 
     * Returns the next element in the iteration. If there are no 
     * more elements in this iteration, a NoSuchElementException is 
     * thrown. 
     * 
     * @return the next element in the iteration 
     * @throws NoSuchElementException if the iterator is empty 
     */ 
     public T next() throws ConcurrentModificationException 
     { 
      if (!hasNext()) 
       throw new NoSuchElementException(); 

      T result = current.getElement(); 
      current = current.getNext(); 
      return result; 
     } 

     /** 
     * The remove operation is not supported. 
     * 
     * @throws UnsupportedOperationException if the remove operation is called 
     */ 
     public void remove() throws UnsupportedOperationException 
     { 
      throw new UnsupportedOperationException(); 
     } 
    } 

} 

LinkedListQueue.java

package jsjf; 

public class LinkedListQueue<T> implements QueueADT<T> { 

    LinkedList queue = new LinkedList(); 


    /** 
    * Adds the specified element to the back of this queue. 
    * 
    * @param element generic element to be pushed onto queue. 
    */ 
    public void enqueue(T element) { 
     queue.add(element); 
    } 


    /** 
    * Removes the element from the front of the queue and returns it. 
    * 
    * @return the element from the front of the queue. 
    */ 
    public T dequeue() { 
     return (T) queue.removeFirst(); 
    } 


    /** 
    * Returns the front element, without removing it. 
    * 
    * @return the element at the front of the queue. 
    */ 
    public T first() { 
     return (T) queue.first(); 
    } 


    /** 
    * Returns true if the queue is empty. 
    * 
    * @return the boolean value of this queue being empty. 
    */ 
    public boolean isEmpty() { 
     if(queue.isEmpty()) 
      return true; 
     return false; 
    } 


    /** 
    * Returns the number of elements contained in the queue. 
    * 
    * @return the number of elements contained in the queue. 
    */ 
    public int size() { 
     return queue.size(); 
    } 


    /** 
    * Returns the queue as a string. 
    * 
    * @return the queue as a string. 
    */ 
    public String toString() { 
     return queue.toString(); 
    } 
} 

LinkedListStack.java

package jsjf; 

public class LinkedListStack<T> implements StackADT<T> { 

    LinkedList stack = new LinkedList(); 


    /** 
    * Adds the specified element to the top of this stack. 
    * 
    * @param element generic element to be pushed onto stack. 
    */ 
    public void push(T element) { 
     stack.add(element); 
    } 


    /** 
    * Removes the element from the top of the stack and returns it. 
    * 
    * @return the element from the top of the stack. 
    */ 
    public T pop() { 
     return (T) stack.removeLast(); 
    } 


    /** 
    * Returns the top element, without removing it. 
    * 
    * @return the element at the top of the stack. 
    */ 
    public T peek() { 
     return (T) stack.last(); 
    } 


    /** 
    * Returns true if the stack is empty. 
    * 
    * @return the boolean value of this stack being empty. 
    */ 
    public boolean isEmpty() { 
     if(stack.isEmpty()) 
      return true; 
     return false; 
    } 


    /** 
    * Returns the number of elements contained in the stack. 
    * 
    * @return the number of elements contained in the stack. 
    */ 
    public int size() { 
     return stack.size(); 
    } 


    /** 
    * Returns the stack as a string. 
    * 
    * @return the stack as a string. 
    */ 
    public String toString() { 
     return stack.toString(); 
    } 

} 

Driver.java

package jsjf; 

public class Driver { 

    public static void main(String[] args) { 

     // Instantiate the array based structures. 
     ArrayListQueue arrayQueue = new ArrayListQueue(); 
     ArrayListStack arrayStack = new ArrayListStack(); 

     // Instantiate the link based structures. 
     LinkedListQueue linkedQueue = new LinkedListQueue(); 
     LinkedListStack linkedStack = new LinkedListStack(); 

     // An integer to hold reference to a data piece to be pushed to the structures. 
     int data; 

     // Randomly generate a piece of data, and pass it to the structures. 
     for(int i = 0; i < 25; i++){ 
      data = (int)(Math.random() * 50); 
      arrayQueue.enqueue(data); 
      arrayStack.push(data); 
      linkedQueue.enqueue(data); 
      linkedStack.push(data); 
     } 


     System.out.print("Array Queue: "); 
     for(int i = 0; i < 25; i++){ 
      System.out.print(arrayQueue.dequeue() + " "); 
     } 
     System.out.println(); 


     System.out.print("Array Stack: "); 
     for(int i = 0; i < 25; i++){ 
      System.out.print(arrayStack.pop() + " "); 
     } 
     System.out.println(); 

     System.out.print("\n\nLinked Stack as string: " + linkedStack.toString() + "\n\n"); 


     System.out.print("Linked Stack: "); 
     for(int i = 0; i < 25; i++){ 
      System.out.print(linkedStack.pop() + " "); 
     } 
     System.out.println(); 


     System.out.print("Linked Queue: " + linkedQueue.toString()); 


     System.out.print("Linked Queue: "); 
     for(int i = 0; i < 25; i++){ 
      System.out.print(linkedQueue.dequeue() + " "); 
     } 
     System.out.println(); 


    } 

} 

Wenn ich Driver.java starte, erhalte ich die folgende Ausgabe.

Array Queue: 45 12 25 40 31 32 14 16 14 26 3 25 22 26 29 6 13 12 30 10 46 10 11 3 11 
Array Stack: 11 3 11 10 46 10 30 12 13 6 29 26 22 25 3 26 14 16 14 32 31 40 25 12 45 


Linked Stack as string: 45 
12 
25 
40 
31 
32 
14 
16 
14 
26 
3 
25 
22 
26 
29 
6 
13 
12 
30 
10 
46 
10 
11 
3 
11 


Linked Stack: Exception in thread "main" jsjf.exceptions.EmptyCollectionException: The list is empty. 
    at jsjf.LinkedList.removeLast(LinkedList.java:135) 
    at jsjf.LinkedListStack.pop(LinkedListStack.java:24) 
    at jsjf.Driver.main(Driver.java:46) 

Answer 1

Sieht aus wie Sie zählen nicht in Ihrem Add-Methoden für die verknüpfte Liste erhöhen, sondern verwenden Zählung, wenn seine leeren oder nicht zu ermitteln.