X468: Iterators DoublyLinkedList remove()

0 / 50

For this question, assume the following implementation of a doubly linked list:

 public static class DLList<T> implements Iterable...

X468: Iterators DoublyLinkedList remove()

For this question, assume the following implementation of a doubly linked list:

    public static class DLList<T> implements Iterable<T> {
        private int numberOfEntries;
        private Node<T> head;
        private Node<T> tail;

        public DLList() {
            head = null;
            tail = null;
            this.numberOfEntries = 0;
        }// end default constructor



        public boolean isEmpty() {
            return numberOfEntries == 0;
        }

        public int getNumberOfEntries() {
            return numberOfEntries;
        }

        public void clear() {
            head = null;
            tail = null;
            this.numberOfEntries = 0;
        }

        public Iterator<T> iterator() {
            return new DLListIterator();
        }

        ...

        // Node
        public class Node<E> {
            private E data; // Entry in bag
            private Node<E> next; // Link to next node
            private Node<E> previous; // Link to previous Node

            public Node(E dataPortion) {
                this(dataPortion, null);
            } // end constructor


            public Node(E dataPortion, Node<E> nextNode) {
                this(dataPortion, nextNode, null);
            } // end constructor


            public Node(E dataPortion, Node<E> nextNode, Node<E> previousNode) {
                data = dataPortion;
                next = nextNode;
                previous = previousNode;
            } // end constructor


            public E getData() {
                if (data != null) {
                    return data;
                }
                return null;
            }


            public Node<E> getNext() {
                return next;
            }


            public void setNext(Node<E> newNext) {
                next = newNext;
            }


            public Node<E> getPrevious() {
                return previous;
            }


            public void setPrevious(Node<E> newPrevious) {
                previous = newPrevious;
            }

        } // end Node


        // Iterator
        public class DLListIterator implements Iterator<T> {
            private Node<T> current;
            private boolean canRemove;

            public DLListIterator() {
                // get first non-sentinal node
                current = head;
                canRemove = false;
            }


            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public void next() {
                ...
            }// end remove
        }// end iterator

    }

Implement the remove() method in the Iterator class. Check the javadocs if you need help remembering what this method is supposed to do! You can find documentation for the Iterators at: https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

For remove there are a couple of cases it's important to think about. Removing from the front of the list, from the back, and from the middle may all involve different logic.

For example, consider a doubly linked list that looks like this:

  A <--> B <--> C <--> D <--> E 
  ^
  |
Current

Initially, current would point to A. After next() is run once, the list would look like this:

  A <--> B <--> C <--> D <--> E 
         ^
         |
      Current

running remove() now should remove A.

  B <--> C <--> D <--> E
  ^
  |
Current

Then after 2 calls to next() running remove() now should remove C.

  B <-->  D <--> E
          ^
          |
        Current

It is also important to consider the case where current is null, this means E should be removed.

Your Answer:

Feedback

Your feedback will appear here when you check your answer.