troubleshooting Question

Accessing Stack Methods Implemented in Generic Double Linked List Class

Avatar of AttilaB
AttilaB asked on
Java
3 Comments1 Solution597 ViewsLast Modified:
Hi everybody,
I had to implement a stack collection inside a doubly linked list class with generic elements.
The doubly linked list seems to be working fine, I can append elements, remove, etc.,
after I make an instance of it and work with the generic nodes the code of which is also enclosed here.

Since Stack methods are also implemented in DLinkedList, in some cases I would like to use it as a stack pushing elements on it, popping elements, etc.

It only partially seems to work that way, or even though I created an Iterator for it, I don't seem to be able to use it with the iterator when pushing or popping elements on the stack collection instance.

So, this is what I am doing:

// DLinkedList is where LStack is implemented
DLinkedList<String> rev1 = new DLinkedList<String>();  
Iterator iterator = rev1.iterator();
        
rev1.push(new Node<String>("Test1"));
rev1.push(new Node<String>("Test2"));
rev1.push(new Node<String>("Test3"));

System.out.println("rev1.length(): " + rev1.length());  // Prints the right value: 3

System.out.println("\nContents of the DLinkedList Node<String> type stack:");

while(!rev1.isEmpty())
    System.out.println(rev1.pop().element); 

/* Problem !!! : It will only print the following:
Contents of the DLinkedList Node<String> type stack:
Test2
Test3
*/

// What happened with Test1   ????

/*
while(iterator.hasNext()){
    System.out.println(iterator.next().element); 
}
*/

// This last one above will not even compile !
// Iterator.next() should return a Node instance, and
// iterator.next().element should give me the data inside
// the Doubly Linked list node, which is a String.

// What am I missing here?

So, what am I missing here?

How can you extract the data inside the elements of a doubly linked list of Nodes
with the iterator used?

How can you pop the Node instance and extract the data from a Stack of
Node instances, with the stack implemented inside the doubly linked list?

Thank you for your help.

The Node class:

public class Node<E> {
	public E element;
	public Node<E> next;
	public Node<E> prev;
	
public Node(E element, Node<E> prev, Node<E> next)
	{
		this.element = element;
		this.prev = prev;
		this.next = next;
	}
	
	public Node(E element)
	{
		this(element, null, null);
	}

public Node next() {
		
		return next;
	}
}

The Doubly linked list class:

import java.util.Iterator;

/** Doubly linked list **/

public class DLinkedList<E extends Comparable<E>> /* implements List<E> , LStack<E> */ {  
    E element;     // Value for this node
    Node<E> head;
    Node<E> tail;
    public Node<E> curr;
    int count;

    public int getCount() {
        return count;
    }

    /** Constructor */
    public DLinkedList() {
        head =null;
    }
    
    /* IMPLEMENTING METHODS SPECIFIED IN List INTERFACE STARTS HERE: */
    
    // Inserting to the front of the list:
        public void insert(Node<E> newNode) {
            if (head == null) {
                head = newNode;
                tail = newNode;
                newNode.prev = null;
                newNode.next = null;
            } else {
                insertBefore(head, newNode);
            }
        }
        
    // Appending to the end of the list:    
    public void append(Node<E> newNode) {
        if (tail == null) {
            insert(newNode);
        } else {
            insertAfter(tail, newNode);
        }
    }
    
    
// Remove node from list:
    public void remove(Node<E> node) {
        if (node.prev == null) {
            head = node.next;
        } else {
            node.prev.next = node.next;
        }

        if (node.next == null) {
            tail = node.prev;
        } else {
            node.next.prev = node.prev;
        }
    }
    
    // It will move the cursor to the head position
    public void moveToStart(){
        if (head != null) {
            curr = head;
        }
    }
    
    // It will move the cursor to the tail position
    public void moveToEnd(){
        if (tail != null) {
            curr = tail;
        }
    }
    
    // It will move the cursor to the previous position
    public void prev(){
        curr = curr.prev;
    }
    
    // It will move the cursor to the next position
    public void next(){
        curr = curr.next;
    }
    
    
    // Returns the cursor position                    
    public int currPos(){
       int position = 0;

          // Needs to be implemented
       
       return position;
    }
    public boolean moveToPos(int pos){ 
        boolean isMoved = false;
        
        // Needs to be implemented

        return isMoved;
    }
    
    // Get the value field of a certain element of the list:
    public Node<E> getValue(E element) {
        for (Node<E> cursor = head; cursor != null; cursor = cursor.next) {
            if (cursor.element.equals(element)) {
                return cursor;
            }
        }

        return null;
    }
    
    /* IMPLEMENTING METHODS SPECIFIED IN List INTERFACE ENDS HERE: */
    
    /* ADDITIONAL METHODS START HERE: */
    public void insertAfter(Node<E> node, Node<E> newNode) {
        newNode.prev = node;
        newNode.next = node.next;

        if (node.next == null) {
            tail = newNode;
        } else {
            node.next.prev = newNode;
        }
        node.next = newNode;
    }

    public void insertBefore(Node<E> node, Node<E> newNode) {
        newNode.prev = node.prev;
        newNode.next = node;
        if (node.prev == null) {
            head = newNode;
        } else {
            node.prev.next = newNode;
        }
        node.prev = newNode;

    }

    public void removeFront() {
        if (head != null) {
            remove(head);
        }
    }

    public void removeEnd() {
        if (tail != null) {
            remove(tail);
        }
    }

/* ADDITIONAL METHODS ENDS HERE: */


/* ITERATOR METHODS: */
    
    public <E extends Comparable<? super E>> void selectionSort(E[] A) {
        int j, k, minIndex;
        E min;
        int N = A.length;

        for (k = 0; k < N; k++) {
            min = A[k];
            minIndex = k;
            for (j = k + 1; j < N; j++) {
                if (A[j].compareTo(min) < 0) {
                    min = A[j];
                    minIndex = j;
                }
            }
            A[minIndex] = A[k];
            A[k] = min;
        }
    }

    private void swap(int[] array, int i, int j) {
        //Implement here
        int temp = 0;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // Iterator inner class defined for DLinkedlist collection:
    // Iterator method for returning iterator:
    public Iterator iterator() {
        return new MyIterator();
    }

    // Inner class MyIterator implementing Iterator:
    private class MyIterator implements Iterator<E> {
        private Node<E> node;
        private Node<E> prev;
        private Node<E> prev2;
        private boolean okToRemove;
        private int expectedNum;

        private MyIterator() {
            node = head;
            prev = null;
            prev2 = null;
            okToRemove = false;
            // can remove only if we call next first
        }

        public boolean hasNext() {
            if (node != null)
                return true;
            else
                return false;
        }

public E next() {
            E toReturn = node.element;
            prev2 = prev;
            prev = node;
            node = node.next;
            okToRemove = true;
            return toReturn;
        }

public void remove() {
            if (!okToRemove)
                throw new IllegalStateException();
            if (prev2 == null) {
                // not assigned yet
                head = node;
            } else {
                prev2.next = node;
            }
            prev = prev2;
            okToRemove = false;
            expectedNum++;
        }
    }
    
    /* ITERATOR METHODS END HERE */
  
    
    /* IMPLEMENTING STACK METHODS STARTS HERE */
    
    public void clear(){
        head = null;
    }
    
      public void push(Node<E> newNode) {
          this.append(newNode);
          count++;
      }
      
      public Node<E> pop() {
          
          if (head != null) {  // if head is NOT null, reduce count, remove and return head node
              count--;
              remove(head);
              return head;
          }
          return null;   // if head IS null, then return null

      }
      
      
    public Node<E> topValue(){
            //Check if the DLL list is empty
             if(this.isEmpty())
                 return null;
                System.out.println("Double Linked list is empty, cannot retrieve first element");
             
             //Get the Node after the head
             Node<E> cursor = head;
             cursor = cursor.next;
             //return the element 
              return cursor;
         }
      
      public int length(){
          return count;
      }
      
      public void printValues() {
          if (isEmpty())
            System.out.println("Stack is Empty");
          else
          {
              System.out.println("List of elements in the stack:");
              for (Node<E> cursor = head; cursor != null; cursor = cursor.next) {
                  String printString = String.valueOf(cursor.element);
                    System.out.print(printString + "  ");
          }
      }
      
      }  
      
    /* IMPLEMENTING STACK METHODS ENDS HERE */
      
    /* ADDITIONAL STACK METHOD USED IN PROGRAM */
      
      // If the head is null, the list is empty:
    public boolean isEmpty() {
        if (count == 0)
            return true;
        else
            return false;
    }
}

Note: DLinkedList  is supposed to implement 2 interfaces, but I took them out with commenting at the top of class, so that I don't have to include these.
ASKER CERTIFIED SOLUTION
mccarl
IT Business Systems Analyst / Software Developer
Join our community to see this answer!
Unlock 1 Answer and 3 Comments.
Start Free Trial
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 1 Answer and 3 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros