Title: LinkedList Implementations
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

LinkedList Implementations

class LinkedList implements List

A LinkedList is not as good as an ArrayList for random access, but is a better if you are creating linked lists and you need to access or insert at either end of the list. The ArrayList on the other hand is somewhat inefficient for inserting into the middle of the list. Because LinkedLists are often used to implement Queues, accessing or modifying the head or the tail of the Queue is important. You can see this by looking at the following table which includes the extra methods available for LinkedList that go beyond the required List interface.

Proto-Type | Description
void addFirst(E e) | Inserts the given element at the beginning of this list.
void addLast(E e) | Appends the given element to the end of this list.
E getFirst() | Returns the first element in this list.
E getLast() | Returns the last element in this list.
E removeFirst() | Removes and returns the first element from this list.
E removeLast() | Removes and returns the last element from this list.

In order to implement the above, you will find that it is useful to have a doubly linked list. This is the technique that is normally used.

However, it is useful to look at what happens if you try to create a singly linked list:

MySinglyLinkedList.java



import java.util.Iterator;


public class MySingleLinkedList<T> {
    private Node head=null;
    private Node tail=null;
    private int totalSize = 0;

    /****** Inner Class *****/
    class Node
    {
        T value;
        Node next;

        Node(T value)
        {
            this.value = value;
            next = null;
        }

    }

    /******* Inner class Iterator *****/
    class MyIterator implements Iterator<T>
    {
        private Node nextNode = head;

        @Override
        public boolean hasNext() {
            if (nextNode== null)
                return false;
            return true;
        }

        @Override
        public T next() {
            T value = nextNode.value;
            nextNode = nextNode.next;
            return value;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Iterator.remove not implemented");

        }

    }

    public Iterator<T> iterator()
    {
        return new MyIterator();
    }


    public boolean add(T value)
    {
        Node n = new Node(value);
        if (tail == null)
        {
            // First node to be added to the List
            tail = head = n;
        }
        else
        {
            tail.next = n;
            tail = n;
        }
        totalSize += 1;
        return true;
    }
    public void addFirst(T value)
    {
        Node n = new Node(value);
        n.next = head;
        if (head != null)
        {
            head = n;
        }
        else
        {
            // First node to be added to the List
            head = tail = n;
        }
        totalSize +=1;
    }
    public T getFirst()
    {
        return head.value;
    }
    public T getlast()
    {
        return tail.value;
    }

    void addLast(T value)
    {
        add(value);
    }
    T removeFirst()
    {
        if (head == null)
            throw new RuntimeException("MySingleLinkedList.removeFirst call on empty list");
        Node n = head;
        head = n.next;
        totalSize -= 1;
        return n.value;
    }

    T removeLast()
    {
        throw new UnsupportedOperationException("MySingleLinkedList.removeLast not implemented");
    }




    public static void main(String[] args) {
        MySingleLinkedList<String> ml = new MySingleLinkedList<String>();

        ml.add("one");
        ml.add("two");
        ml.add("three");
        ml.add("four");
        ml.add("five");

        System.out.println("Front = "+ ml.getFirst());
        System.out.println("Last = " + ml.getlast());


        Iterator<String> iter = ml.iterator();

        while (iter.hasNext())
        {
            String s = iter.next();
            System.out.println(s);
        }

        ml.removeFirst();

        System.out.println("After removeFirst");
        iter = ml.iterator();
        while (iter.hasNext())
        {
            String s = iter.next();
            System.out.println(s);
        }



    }

}


Doubly Linked List (MyLinkedListFirst.java)

MyLinkedListFirst.java



import java.util.Iterator;

import my_linked_list.MyLinkedList.Node;


public class MyLinkedListFirst<T> {
    private Node header = new Node();
    private int totalSize = 0;

    /****** Inner Class *****/
    class Node
    {
        T value;
        Node next;
        Node previous;

        Node()
        {
            value = null;
            next = this;
            previous = this;
        }

        Node(T value, Node curr)
        {
            this.value = value;
            next = curr;
            previous = curr.previous;
            curr.previous.next = this;
            curr.previous = this;
        }


    }

    /******* Inner class Iterator *****/
    class MyIterator implements Iterator<T>
    {
        Node lastNode = header;
        Node nextNode = header;

        @Override
        public boolean hasNext() {
            if (nextNode.next == lastNode)
                return false;
            return true;
        }

        @Override
        public T next() {
            nextNode = nextNode.next;
            return nextNode.value;
        }

        @Override
        public void remove() {
            removeNode(nextNode);

        }

    }

    public Iterator<T> iterator()
    {
        return new MyIterator();
    }

    private void addNode(T value, Node curr)
    {
        new Node(value, curr);
        totalSize += 1;
    }

    public boolean add(T value)
    {
        addNode(value, header);
        return true;
    }
    void addLast(T value)
    {
        add(value);
    }
    public void addFirst(T value)
    {
        addNode(value, header.next);
    }
    public T getFirst()
    {
        return header.next.value;
    }
    public T getlast()
    {
        return header.previous.value;
    }

    private void removeNode(Node n)
    {
        n.previous.next = n.next;
        n.next.previous = n.previous;
        totalSize-=1;
    }
    T removeFirst()
    {
        Node n = header.next;
        T value = n.value;
        removeNode(n);
        return value;
    }

    T removeLast()
    {
        Node n = header.previous;
        T value = n.value;
        removeNode(n);
        return value;
    }


    public int size() {

        return totalSize;
    }
    public boolean isEmpty() {
        if (totalSize==0)
            return true;
        else
            return false;
    }
    public void clear() {
         header = new Node();
         totalSize = 0;
    }


    public static void main(String[] args) {
        MyLinkedListFirst<String> ml = new MyLinkedListFirst<String>();

        ml.add("three");
        ml.add("four");
        ml.add("five");
        ml.addFirst("two");
        ml.addFirst("one");

        System.out.println("Front = "+ ml.getFirst());
        System.out.println("Last = " + ml.getlast());


        Iterator<String> iter = ml.iterator();

        while (iter.hasNext())
        {
            String s = iter.next();
            if (s.equals("three"))
                iter.remove();
            System.out.println(s);
        }
        System.out.println("After removing three");
        iter = ml.iterator();
        while (iter.hasNext())
        {
            String s = iter.next();
            System.out.println(s);
        }

        ml.removeFirst();

        System.out.println("After removeFirst");
        iter = ml.iterator();
        while (iter.hasNext())
        {
            String s = iter.next();
            System.out.println(s);
        }


        ml.removeLast();

        System.out.println("After removeLast");
        iter = ml.iterator();
        while (iter.hasNext())
        {
            String s = iter.next();
            System.out.println(s);
        }

    }

}


Implementing the List interface

You could now add implements List<T> to your MyLinkedListFirst.java. Then add all the required methods.

See MyLinkedList.java

Last Updated:

July 22, 2014 9:57 PM