linkedlist.java

Linked List implementation for education purposes.

// A linked list is a sequence of nodes with efficient
// element insertion and removal.
// This class contains a subset of the methods of the
// standard java.util.LinkedList class.

import java.util.NoSuchElementException;

public class LinkedList
{
    //nested class to represent a node
    private class Node
    {
        public Object data;
        public Node next;
    }

    //only instance variable that points to the first node.
    private Node first;

    // Constructs an empty linked list.
    public LinkedList()
    {
        first = null;
    }


    // Returns the first element in the linked list.
    public Object getFirst()
    {
        if (first == null)
        {
            NoSuchElementException ex = new NoSuchElementException();
            throw ex;
        }
        else
            return first.data;
    }

    // Removes the first element in the linked list.
    public Object removeFirst()
    {
        if (first == null)
        {
            NoSuchElementException ex = new NoSuchElementException();
            throw ex;
        }
        else
        {
            Object element = first.data;
            first = first.next;  //change the reference since it's removed.
            return element;
        }
    }

    // Adds an element to the front of the linked list.
    public void addFirst(Object element)
    {
        //create a new node
        Node newNode = new Node();
        newNode.data = element;
        newNode.next = first;
        //change the first reference to the new node.
        first = newNode;
    }

    // Returns an iterator for iterating through this list.
    public ListIterator listIterator()
    {
        return new LinkedListIterator();
    }


    //nested class to define its iterator
    private class LinkedListIterator implements ListIterator
    {
        private Node position; //current position
        private Node previous; //it is used for remove() method

        // Constructs an iterator that points to the front
        // of the linked list.

        public LinkedListIterator()
        {
            position = null;
            previous = null;
        }

        // Tests if there is an element after the iterator position.
        public boolean hasNext()
        {
            if (position == null) //not traversed yet
            {
                if (first != null)
                    return true;
                else
                    return false;
            }
            else
            {
                if (position.next != null)
                    return true;
                else
                    return false;
            }
        }

        // Moves the iterator past the next element, and returns
        // the traversed element's data.
        public Object next()
        {
            if (!hasNext())
            {
                NoSuchElementException ex = new NoSuchElementException();
                throw ex;
            }
            else
            {
                previous = position; // Remember for remove

                if (position == null)
                    position = first;
                else
                    position = position.next;

                return position.data;
            }
        }

        // Adds an element before the iterator position
        // and moves the iterator past the inserted element.
        public void add(Object element)
        {
            if (position == null) //never traversed yet
            {
                addFirst(element);
                position = first;
            }
            else
            {
                //making a new node to add
                Node newNode = new Node();
                newNode.data = element;
                newNode.next = position.next;
                //change the link to insert the new node
                position.next = newNode;
                //move the position forward to the new node
                position = newNode;
            }
            //this means that we cannot call remove() right after add()
            previous = position;
        }

        // Removes the last traversed element. This method may
        // only be called after a call to the next() method.
        public void remove()
        {
            if (previous == position)  //not after next() is called
            {
                IllegalStateException ex = new IllegalStateException();
                throw ex;
            }
            else
            {
                if (position == first)
                {
                    removeFirst();
                }
                else
                {
                    previous.next = position.next; //removing
                }
                //stepping back
                //this also means that remove() cannot be called twice in a row.
                position = previous;
            }
        }

        // Sets the last traversed element to a different value.
        public void set(Object element)
        {
            if (position == null)
            {
                NoSuchElementException ex = new NoSuchElementException();
                throw ex;
            }
            else
                position.data = element;
        }
    } //end of LinkedListIterator class

    public String toString()
    {
        LinkedListIterator iterator1 = new LinkedListIterator();

        StringBuffer returnString = new StringBuffer(" ");
        returnString.append("{ ");

        while (iterator1.hasNext())
            returnString.append(iterator1.next()).append(" ");

        returnString.append("}\n");
        return returnString.toString();
    }


    public int size()
    {
        int size = 0;
        ListIterator it = this.listIterator();
        while (it.hasNext())
        {
            it.next();
            size++;
        }

        return size;
    }

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

    public int searchElement(Object element)
    {
        int pos = -1;
        int counter = 0;
        ListIterator it = listIterator();
        while (it.hasNext())
        {
            Object obj = it.next();
            if (obj != null)
            {
                if (obj.equals(element))
                {
                    pos = counter;
                    break;
                }
            }
            counter++;
        }
        return pos;
    }

    public void addElement(int index, Object element) throws IndexOutOfBoundsException
    {
        if (size() <= index && index>0)
            throw new IndexOutOfBoundsException();

        if (index < 0)
            throw new IndexOutOfBoundsException();

        if (size() == 0)
            addFirst(element);
        else
        {
            int counter = 0;
            ListIterator it = this.listIterator();
            while (it.hasNext())
            {
                if (counter == index)
                {
                    it.add(element);
                    return;
                }
                it.next();
                counter++;
            }
        }
    }

    public Object removeElement(int index)
    {
        if (size() <= index)
            throw new IndexOutOfBoundsException();

        if (index < 0)
            throw new IndexOutOfBoundsException();

        if (size() > 0)
        {
            int counter = 0;
            ListIterator it = this.listIterator();
            while (it.hasNext())
            {
                Object obj = it.next();
                if (counter == index)
                {
                    it.remove();
                    return obj;
                }
                counter++;
            }
        }

        return null;
    }

    public Object findSmallest() throws NoSuchElementException
    {
        if (size() == 0)
            throw new NoSuchElementException();

        String min = null;
        ListIterator it = listIterator();
        while (it.hasNext())
        {
            Object obj = it.next();
            if (obj instanceof String)
            {
                if (min == null)
                    min = (String) obj;
                else
                {
                    if (min.compareTo((String) obj) > 0)
                        min = (String) obj;
                }
            }
        }

        return min;
    }

    public void removeAllOccurrences(Object stringToBeRemoved)
    {
        if (size() == 0)
            return;

        ListIterator it = listIterator();
        while (it.hasNext())
        {
            Object obj = it.next();
            if (obj.equals(stringToBeRemoved))
            {
                it.remove();
                it = listIterator();
            }
        }
    }

} //end of LinkedList class