[code] KWLinkedList.java

/**
 ///////////////////////////////////////////
 Prepared by: OL Academy
 Whatsapp:    66939059
 Instagram:   olearninga
 Website:     www.olearninga.com
 Last Update: 10 NOV 2023
 ///////////////////////////////////////////
 */

import java.util.AbstractSequentialList;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;


public class KWLinkedList<E> extends AbstractSequentialList<E> {
    // Data Fields

    private Node<E> head = null;
    /**
     * A reference to the end of the list.
     */
    private Node<E> tail = null;
    /**
     * The size of the list.
     */
    private int size = 0;

    /**
     * Insert an object at the beginning of the list.
     *
     * @param item - the item to be added
     */
    public void addFirst(E item) {
        Node<E> newNode = new Node(item);
        if (head == null)
            head = tail = newNode;
        else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }

    /**
     * Insert an object at the end of the list.
     *
     * @param item - the item to be added
     */
    public void addLast(E item) {
        Node<E> newNode = new Node(item);
        if (head == null)
            head = tail = newNode;

        else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        size++;
    }

    /**
     * Get the first element in the list.
     *
     * @return The first element in the list.
     */
    public E getFirst() {
        if (head == null)
            throw new NoSuchElementException();
        return head.data;
    }

    /**
     * Get the last element in the list.
     *
     * @return The last element in the list.
     */
    public E getLast() {
        if (head == null)
            throw new NoSuchElementException();
        return tail.data;
    }


    /**
     * Return an Iterator to the list
     *
     * @return an Itertor to the list
     */
    public Iterator<E> iterator() {
        KWListIter iterator = new KWListIter(0);
        return iterator;
    }

    /**
     * Return a ListIterator to the list
     *
     * @return a ListItertor to the list
     */
    public ListIterator<E> listIterator() {
        KWListIter iterator = new KWListIter(0);
        return iterator;
    }

    /**
     * Return a ListIterator that begins at index
     *
     * @param index - The position the iteration is to begin
     * @return a ListIterator that begins at index
     */
    public ListIterator<E> listIterator(int index) {
        KWListIter iterator = new KWListIter(index);
        return iterator;
    }

    /**
     * Return a ListIterator that begins at the same
     * place as an existing ListIterator
     *
     * @param iter - The other ListIterator
     * @return a ListIterator that is a copy of iter
     */
    public ListIterator<E> listIterator(ListIterator<E> iter) {
        KWListIter iterator = new KWListIter((KWListIter) iter);
        return iterator;
    }

    /**
     * Add an item at the specified index.
     *
     * @param index The index at which the object is to be
     *              inserted
     * @param obj   The object to be inserted
     * @throws IndexOutOfBoundsException if the index is out
     *                                   of range (i < 0 || i > size())
     */
    @Override
    public void add(int index, E obj) {
        listIterator(index).add(obj);
    }

    /**
     * Get the element at position index.
     *
     * @param index Position of item to be retrieved
     * @return The item at index
     */
    @Override
    public E get(int index) {
        return listIterator(index).next();
    }

    /**
     * Return the size of the list
     *
     * @return the size of the list
     */
    @Override
    public int size() {
        return size;
    }

    // Inner Classes

    /**
     * A Node is the building block for a double-linked list.
     */
    private static class Node<E> {

        /**
         * The data value.
         */
        public E data;
        /**
         * The link to the next node.
         */
        public Node<E> next = null;
        /**
         * The link to the previous node.
         */
        public Node<E> prev = null;

        /**
         * Construct a node with the given data value.
         *
         * @param dataItem The data value
         */
        private Node(E dataItem) {
            data = dataItem;
        }

        public String getData() {
            if (data == null)
                return "null";
            else
                return (String) data;
        }
    } //end class Node

    /**
     * Inner class to implement the ListIterator interface.
     */
    private class KWListIter implements ListIterator<E> {

        /**
         * A reference to the next item.
         */
        private Node<E> nextItem;
        /**
         * A reference to the last item returned.
         */
        private Node<E> lastItemReturned;
        /**
         * The index of the current item.
         */
        private int index = 0;

        /**
         * Construct a KWListIter that will reference the ith item.
         *
         * @param i The index of the item to be referenced
         */
        public KWListIter(int i) {
            // Validate i parameter.
            if (i < 0 || i > size) {
                throw new IndexOutOfBoundsException(
                        "Invalid index " + i);
            }
            lastItemReturned = null; // No item returned yet.
            // Special case of last item.
            if (i == size) {
                index = size;
                nextItem = null;
            } else { // Start at the beginning
                nextItem = head;
                for (index = 0; index < i; index++) {
                    nextItem = nextItem.next;
                }
            }
        }

        /**
         * Construct a KWListIter that is a copy of another KWListIter
         *
         * @param other The other KWListIter
         */
        public KWListIter(KWListIter other) {
            KWListIter itr = new KWListIter(0);
            itr.index = other.index;
            itr.lastItemReturned = other.lastItemReturned;
            itr.nextItem = other.nextItem;
        }

        /**
         * Indicate whether movement forward is defined.
         *
         * @return true if call to next will not throw an exception
         */
        @Override
        public boolean hasNext() {
            return nextItem != null;
        }

        /**
         * Move the iterator forward and return the next item.
         *
         * @return The next item in the list
         * @throws NoSuchElementException if there is no such object
         */
        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            lastItemReturned = nextItem;
            nextItem = nextItem.next;
            index++;
            return lastItemReturned.data;
        }

        /**
         * Indicate whether movement backward is defined.
         *
         * @return true if call to previous will not throw an exception
         */
        @Override
        public boolean hasPrevious() {
            return (nextItem == null && size != 0)
                    || (nextItem.prev != null);
        }

        /**
         * Return the index of the next item to be returned by next
         *
         * @return the index of the next item to be returned by next
         */
        @Override
        public int nextIndex() {
            return index;
        }

        /**
         * Return the index of the next item to be returned by previous
         *
         * @return the index of the next item to be returned by previous
         */
        @Override
        public int previousIndex() {
            return index - 1;
        }

        /**
         * Move the iterator backward and return the previous item.
         *
         * @return The previous item in the list
         * @throws NoSuchElementException if there is no such object
         */
        @Override
        public E previous() {
            if (!hasPrevious())
                throw new NoSuchElementException();

            else if (nextItem == null) // Iterator past the last element
                nextItem = tail;

            else {
                nextItem = nextItem.prev;
            }
            lastItemReturned = nextItem;
            index--;
            return lastItemReturned.data;
        }

        /**
         * Add a new item between the item that will be returned
         * by next and the item that will be returned by previous.
         * If previous is called after add, the element added is
         * returned.
         *
         * @param obj The item to be inserted
         */
        @Override
        public void add(E item) {
            Node<E> newNode = new Node<>(item);
            if (head == null)
                head = tail = newNode;

// Insert at head.
            else if (nextItem == head) {

                newNode.next = nextItem;
                nextItem.prev = newNode;
                head = newNode;
            }

// Insert at tail.
            else if (nextItem == null) {
                tail.next = newNode;
                newNode.prev = tail;
                tail = newNode;
            }
// Insert into the middle.
            else {
                newNode.prev = nextItem.prev;
                nextItem.prev.next = newNode;
                newNode.next = nextItem;
                nextItem.prev = newNode;
            }

// Increase size and index and set lastItemReturned.
            size++;
            index++;
            lastItemReturned = null;
        } // End of method add.


        /**
         * Remove the last item returned. This can only be
         * done once per call to next or previous.
         *
         * @throws IllegalStateException if next or previous
         *                               was not called prior to calling this method
         */
        @Override
        public void remove() {
            //case1: lastItemReturned null
            if (lastItemReturned == null)
                throw new IllegalStateException();

                //case2: lastItemReturned in the first node
            else if (lastItemReturned == head) {
                head = head.next;
                if (head == null)
                    tail = null;
                else
                    head.prev = null;
                size--;
            }

            //case3: lastItemReturned in the last node
            else if (lastItemReturned == tail) {
                tail = tail.prev;
                tail.next = null;
                size--;
            }

            //case4: lastItemReturned in the middle
            else {
                lastItemReturned.prev.next = lastItemReturned.next;
                lastItemReturned.next.prev = lastItemReturned.prev;
                lastItemReturned = null;
            }
        }


        /**
         * Replace the last item returned with a new value
         *
         * @param item The new value
         * @throws IllegalStateException if next or previous
         *                               was not called prior to calling this method
         */
        @Override
        public void set(E item) {

            lastItemReturned.data = item;
        }


        /**
         * Method to find the index of the first occurence of an item in the list
         *
         * @param target The item being sought
         * @return The index of the first occurence of the tartet item
         * or -1 if the item is not found.
         */
        //@Override
        public int indexOf(Object target) {

            return -1;
        }


        /**
         * Method to find the index of the last occurence of an item in the list
         *
         * @param target The item being sought
         * @return The index of the last occurence of the tartet item
         * or -1 if the item is not found.
         */
        //   @Override
        public int lastIndexOf(Object target) {

            return -1;
        }

        /**
         * Method to return the index of the minimum item in the list
         * It is assumed that each item in the list implements Comparable
         *
         * @return Index of the minimum item in the list
         * or -1 if the list is empty
         * @throws ClassCastExcepition if the list elements do not implement Comparable
         */
        public int indexOfMin() {

            return 0;
        }

    }
}