CIS 260 GTestLinkedList.java

Code

/*
    GTestLinkedList.java
    Dave Klick
    2014-03-26
    
    Linked list implementation that accepts any type of object.
*/

class LinkedList<T> {
    private class Node<T> {
        T data;
        Node<T> next;
        
        public Node(T obj) {
            data = obj;
            next = null;
        }
        
        public Node(Node<T> n) {
            data = n.data;
            next = null;
        }
        
        public String toString() {
            return data.toString();
        }
        
    }

    private Node<T> head = null;
    private int count = 0;

    public void addFirst(T data) {
        Node<T> newnode = new Node<T>(data);
        newnode.next = head;
        head = newnode;
        count++;
    }
    
    public void addLast(T data) {
        Node<T> newnode = new Node<T>(data);
        if (head == null) {
            head = newnode;
        } else {
            Node<T> cur = head;
            while (cur.next != null) cur = cur.next;
            cur.next = newnode;
        }
        count++;
    }
    
    public void add(T data) { addLast(data); }

    // could also use: return count == 0;
    public boolean isEmpty() { return head == null; }   

    public int length() { return count; }
    public int size() { return count; }
   
    public T first() {
        if (head == null) return null;
        else return head.data;      
    }
    
    public T getFirst() { return first(); }
    
    public T last() {
        if (head == null) return null;
        Node<T> cur = head;
        while (cur.next != null) cur = cur.next;
        return cur.data;      
    }

    public T getLast() { return last(); }

    public T removeFirst() {
        if (head == null) return null;
        else {
            T data = head.data;
            head = head.next;
            count--;
            return data;
        }
    }
    
    public T removeLast() {
        if (head == null) return null;
        Node<T> prev = null;
        Node<T> cur = head;
        while (cur.next != null) {
            prev = cur;
            cur = cur.next;
        }
        if (prev != null) prev.next = null;
        else head = null;
        count--;
        return cur.data;
    }

    public boolean remove(T data) {
        if (head == null) return false;
        Node<T> prev = null;
        Node<T> cur = head;
        while (cur != null) {
            if (!cur.data.equals(data)) {
                prev = cur;
                cur = cur.next;
            } else {
                if (cur == head) head = cur.next;
                else prev.next = cur.next;
                count--;
                return true;
            }
        }
        return false;
    }
   
    public T remove(int ndx) {
        if (ndx < 0 || ndx >= count) throw new IndexOutOfBoundsException();
        
        T data = null;
        if (ndx == 0) {  // removing head of list
            data = head.data;
            head = head.next;
        } else {
            Node<T> prev = null;
            Node<T> cur = head;
            while (ndx-- > 0) {
                prev = cur;
                cur = cur.next;
            }
            data = cur.data;
            prev.next = cur.next;
        }
        count--;
        return data;
    }
    
    public void clear() {
        while (!isEmpty()) removeFirst();
    }
    
    public T get(int ndx) {
        if (ndx < 0 || ndx >= count) throw new IndexOutOfBoundsException();
        Node<T> cur = head;
        while (ndx-- > 0) cur = cur.next;
        return cur.data;
    }

    public T set(int ndx, T newdata) {
        if (ndx < 0 || ndx >= count) throw new IndexOutOfBoundsException();
        Node<T> cur = head;
        while (ndx-- > 0) cur = cur.next;
        T olddata = cur.data;
        cur.data = newdata;
        return olddata;
    }

    public void add(int ndx, T data) {
        if (ndx < 0 || ndx > count) throw new IndexOutOfBoundsException();
        if (ndx == 0) addFirst(data);
        else {
            Node<T> cur = head;
            while (--ndx > 0) cur = cur.next;
            Node<T> newnode = new Node<T>(data);
            newnode.next = cur.next;
            cur.next = newnode;
            count++;
        }
    }

    public void insert(int ndx, T data) { add(ndx, data); }
    
    public boolean contains(T data) {
        Node<T> cur = head;
        while (cur != null) {
            if (cur.data.equals(data)) return true;
            cur = cur.next;
        }
        return false;
    }

    public int indexOf(T data) {
        Node<T> cur = head;
        int ndx = 0;
        while (cur != null) {
            if (cur.data.equals(data)) return ndx;
            cur = cur.next;
            ndx++;
        }
        return -1;
    }
    
    public String toString() {
        StringBuilder s = new StringBuilder();
        Node<T> cur = head;
        while (cur != null) {
            if (s.length() > 0) s.append(", ");
            s.append(cur.data.toString());
            cur = cur.next;
        }
        return s.toString();
    }
}

public class GTestLinkedList {
    public static void main(String[] args) {
        // first test - construction and adding elements
        LinkedList<String> lst = new LinkedList<String>();
        lst.addFirst("First");
        lst.add("Second");
        lst.addLast("Last");
        lst.add(1, "New second");
        lst.set(2, "Third");
        lst.addFirst("Zeroth");
        lst.addLast("Last + 1");
        lst.insert(4, "Fourth");
        lst.add(7, "End of list");
        System.out.println("Length of list: " + lst.length());
        System.out.println(lst);
        System.out.println();
        
        // second test - finding elements
        System.out.println("Element in first position is: " + lst.getFirst());
        System.out.println("Element in last position is: " + lst.getLast());
        System.out.println("Element in position 2 is: " + lst.get(2));
        System.out.println("\"Third\" is in position: " + lst.indexOf("Third"));
        System.out.println("\"Fifth\" is in position: " + lst.indexOf("Fifth"));
        System.out.printf("The list does %scontain \"Third\"\n", lst.contains("Third") ? "" : "not ");
        System.out.printf("The list does %scontain \"Fifth\"\n", lst.contains("Fifth") ? "" : "not ");
        System.out.println();
        
        // third test - deleting elements
        System.out.println("Removing \"Fourth\"");
        lst.remove("Fourth");
        System.out.println("Removing last item in list");
        lst.removeLast();
        System.out.println("Removing first item in list");
        lst.removeFirst();
        System.out.println("Removing last item in list by index");
        lst.remove(lst.size()-1);
        System.out.println(lst);
        System.out.println("Clearing list");
        lst.clear();
        System.out.println("List now contains: " + lst);
   }
}