Lab 23: Linked List

The code below is a slightly modified version of Listing 12.12 from your textbook. It implements a basic linked list. For this lab you will implement the missing methods in the code below.

/**
 * LinkedList.java
 * 
 * @author Jose M Vidal  A slight modification of Listing
 *         12.12 from the textbook. Created on Apr 5, 2012
 * 
 */

public class LinkedList<T> {

    /**
     * The ListNode is a private inner class of the LinkedList.
     */
    private class ListNode {
        /**
         * The data this node holds
         */
        private T data;

        /**
         * A reference to the next node on the list. next is null if this node
         * is the tail.
         */
        private ListNode next;

        public ListNode() {
            next = null;
            data = null;
        }

        public ListNode(T data, ListNode next) {
            this.data = data;
            this.next = next;
        }

        public T getData() {
            return data;
        }

        public ListNode getNext() {
            return next;
        }
     }

    private ListNode head;

    public LinkedList() {
        head = null;
    }

    /**
     * Adds data at the head of the list.
     * 
     * @param data
     */
    public void add(T data) {
        head = new ListNode(data, head);
    }

    /**
     * Adds data to the end of the list.
     * 
     * @param data
     */
    public void append(T data) {
    //TODO: add your code here
    }

    /**
     * Insert data into list so that it is at position index. If index is too
     * large, or small, we throw an exception.
     * 
     * @param index
     * @param data
     * @throws Exception
     */
    public void insert(int index, T data) throws Exception {
    //TODO: add  your code here
    }

    /**
     * Turns this list into a pretty String, like: 1 -> 5 -> 8 -> null
     */
    public String toString() {
    //TODO: add your code here
    }

    public static void main(String[] args) {
        LinkedList<Integer> l = new LinkedList<Integer>();
        l.add(13);
        l.add(5);
        l.add(8);
        System.out.println(l);
        l.append(55);
        l.append(21);
        System.out.println(l);
        System.out.println("insert 33 at position 3");
        try {
            l.insert(3, 33);
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println(l);

        System.out.println("insert 2 at position 0");
        try {
            l.insert(0, 2);
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println(l);

        System.out.println("insert 77 at position 7");
        try {
            l.insert(7, 77);
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println(l);

        System.out.println("try to insert 100 at position 100");
        try {
            l.insert(100, 100);
        } catch (Exception e) {
            System.out.println("ERROR:" + e.getMessage());
        }
        System.out.println(l);

    }

}

Add your methods so that when we run that main it prints out:

8 -> 5 -> 13 -> null
8 -> 5 -> 13 -> 55 -> 21 -> null
insert 33 at position 3
8 -> 5 -> 13 -> 33 -> 55 -> 21 -> null
insert 2 at position 0
2 -> 8 -> 5 -> 13 -> 33 -> 55 -> 21 -> null
insert 77 at position 7
2 -> 8 -> 5 -> 13 -> 33 -> 55 -> 21 -> 77 -> null
try to insert 100 at position 100
ERROR:index is longer than the list
2 -> 8 -> 5 -> 13 -> 33 -> 55 -> 21 -> 77 -> null

As always, turn it in on the dropbox.cse.sc.edu.