LLList.java

Download 
1/*2 * LLList.java3 *4 * Computer Science S-22, Harvard University5 */6 7import java.util.*;8 9/*10 * A class that implements our simple List interface using a linked list.11 * The linked list includes a dummy head node that allows us to avoid12 * special cases for insertion and deletion at the front of the list.13 */14public class LLList implements List {15    // Inner class for a node.  We use an inner class so that the LLList16    // methods can access the instance variables of the nodes.17    private class Node {18        private Object item;19        private Node next;20        21        private Node(Object i, Node n) {22            item = i;23            next = n;24        }25    }26    27    // fields of the LLList object28    private Node head;     // dummy head node29    private int length;    // # of items in the list30    31    /*32     * Constructs a LLList object for a list that is initially empty.33     */34    public LLList() {35        head = new Node(null, null);36        length = 0;37    }38    39    /*40     * Constructs an LLList object containing the items in the specified array41     */42    public LLList(Object[] initItems) {43        head = new Node(null, null);44        45        Node prevNode = head;46        for (int i = 0; i < initItems.length; i++) {47            Node nextNode = new Node(initItems[i], null);48            prevNode.next = nextNode;49            prevNode = nextNode;50        }51        52        length = initItems.length;53    }54    55    /* 56     * length - returns the number of items in the list 57     */58    public int length() {59        return length;60    }61    62    /* 63     * isFull - always returns false, because the linked list can64     * grow indefinitely and thus the list is never full.65     */66    public boolean isFull() {67        return false;68    }69    70    /* 71     * getNode - private helper method that returns a reference to the72     * ith node in the linked list.  It assumes that the value of the73     * parameter is valid.  74     * 75     * If i == -1, it returns a reference to the dummy head node.76     */77    private Node getNode(int i) {78        Node trav = head;79        int travIndex = -1;80        81        while (travIndex < i) {82            travIndex++;83            trav = trav.next;84        }85        86        return trav;87    }88    89    /* 90     * getItem - returns the item at position i in the list 91     */92    public Object getItem(int i) {93        if (i < 0 || i >= length) {94            throw new IndexOutOfBoundsException();95        }96        97        Node n = getNode(i);98        return n.item;99    }100    101    /* 102     * addItem - adds the specified item at position i in the list,103     * shifting the items that are currently in positions i, i+1, i+2,104     * etc. to the right by one.  Always returns true, because the list105     * is never full.106     *107     * We don't need a special case for insertion at the front of the108     * list (i == 0), because getNode(0 - 1) will return the dummy109     * head node, and the rest of insertion can proceed as usual.110     */111    public boolean addItem(Object item, int i) {112        if (item == null || i < 0 || i > length) {113            throw new IllegalArgumentException();114        }115        116        Node newNode = new Node(item, null);117        Node prevNode = getNode(i - 1);           118        newNode.next = prevNode.next;119        prevNode.next = newNode;120        121        length++;122        return true;123    }124    125    /* 126     * removeItem - removes the item at position i in the list,127     * shifting the items that are currently in positions i+1, i+2,128     * etc. to the left by one.  Returns a reference to the removed129     * object.130     *131     * Here again, we don't need a special case for i == 0 (see the132     * note accompanying addItem above).133     */134    public Object removeItem(int i) {135        if (i < 0 || i >= length) {136            throw new IndexOutOfBoundsException();137        }138        139        Node prevNode = getNode(i - 1);           140        Object removed = prevNode.next.item;141        prevNode.next = prevNode.next.next;142        143        length--;144        return removed;145    }146    147    /*148     * toString - converts the list into a String of the form 149     * {item0, item1, ...}150     */151    public String toString() {152        String str = "{";153        154        Node trav = head.next;    // skip over the dummy head node155        while (trav != null) {156            str = str + trav.item;157            if (trav.next != null) {158                str = str + ", ";159            }160            trav = trav.next;161        }162        163        str = str + "}";164        return str;165    }166    167    /*168     * iterator - returns an iterator for this list169     */170    public ListIterator iterator() {171        return new LLListIterator();172    }173    174    /*175     * private inner class for an iterator over an LLList176     */177    private class LLListIterator implements ListIterator {178        private Node nextNode;       // the next node to visit    179        180        public LLListIterator() {181            nextNode = head.next;    // skip over the dummy head node182        }183        184        /*185         * hasNext - does the iterator have additional items to visit?186         */187        public boolean hasNext() {188            return (nextNode != null);189        }190        191        /*192         * next - returns a reference to the next Object in the iteration193         */194        public Object next() {195            if (nextNode == null) {196                throw new NoSuchElementException();197            }198            199            Object item = nextNode.item;200            nextNode = nextNode.next;201            return item;202        }203    }204}