Avatar of AttilaB
AttilaB
 asked on

Accessing Stack Methods Implemented in Generic Double Linked List Class

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?

Open in new window


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

Open in new window


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

Open in new window


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.
Java

Avatar of undefined
Last Comment
mccarl

8/22/2022 - Mon
ASKER CERTIFIED SOLUTION
mccarl

Log in or sign up to see answer
Become an EE member today7-DAY FREE TRIAL
Members can start a 7-Day Free trial then enjoy unlimited access to the platform
Sign up - Free for 7 days
or
Learn why we charge membership fees
We get it - no one likes a content blocker. Take one extra minute and find out why we block content.
Not exactly the question you had in mind?
Sign up for an EE membership and get your own personalized solution. With an EE membership, you can ask unlimited troubleshooting, research, or opinion questions.
ask a question
AttilaB

ASKER
Excellent. I really appreciate all your explanations and help. We managed to submit the college project this was part of ON TIME and 100% COMPLETE thanks to your help, last night. Plus I understand this much better now. Thank you.
mccarl

Not a problem, glad I could help ;)
Experts Exchange has (a) saved my job multiple times, (b) saved me hours, days, and even weeks of work, and often (c) makes me look like a superhero! This place is MAGIC!
Walt Forbes