Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

So here it is, my implementation in Java. I have coded against Java's List<E> interface as if my LinkedList<E> could replace the standard java.util.LinkedList<E> and it should make no difference.
I am however aware of that I did not implement Deque<E>, as only implementing List<E> is a task on its own already.
This code has been implemented using Java 8.

/**
 *
 * @author Frank van Heeswijk
 * @param <E>   Type of elements the list stores
 */
public class LinkedList<E> implements List<E> {
    /** Fake head node, meaning that it is not part of the List<E> it represents. **/
    private Node head;

    /** Fake tail node, meaning that it is not part of the List<E> it represents. **/
    private Node tail;

    /** If this list is a sublist of a LinkedList, then the parent will be in this variable. **/
    private LinkedList<E> parentList;

    /** The amount of modifications that occured to this LinkedList so far. **/
    private int modificationsCount;

    /** The size of this LinkedList. **/
    private int size;

    public LinkedList() { 
        this(Collections.emptyList());
    }

    public LinkedList(final Collection<? extends E> collection) {
        this.head = new Node(null);
        this.tail = new Node(null);
        connect(head, tail);
        addAll(collection);
    }

    private LinkedList(final Node head, final Node tail, final int size, final LinkedList<E> parentList) {
        this.head = head;
        this.tail = tail;
        this.size = size;
        this.parentList = parentList;
    }

    @Override
    public int size() {
        return size;
    }

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

    @Override
    public boolean contains(final Object object) {
        return iteratorToStream().anyMatch(elem -> elem.equals(object));
    }

    @Override
    public Iterator<E> iterator() {
        return listIterator();
    }

    @Override
    public Object[] toArray() {
        return iteratorToStream().toArray();
    }

    @Override
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(final T[] elemArray) {
        Objects.requireNonNull(elemArray);
        if (size() > elemArray.length) {
            return (T[])toArray();
        }
        Iterator<E> iterator = iterator();
        int index = 0;
        while (iterator.hasNext()) {
            Object next = iterator.next();
            elemArray[index++] = (T)next;
        }
        for (int i = index; i < elemArray.length; i++) {
            elemArray[i] = null;
        }
        return elemArray;
    }

    @Override
    public boolean add(final E element) {
        add(size(), element);
        return true;
    }

    @Override
    public boolean remove(final Object object) {
        ListIterator<E> listIterator = listIterator();
        while (listIterator.hasNext()) {
            if (listIterator.next().equals(object)) {
                listIterator.remove();
                return true;
            }
        }
        return false;
    }

    @Override
    public boolean containsAll(final Collection<?> collection) {
        Objects.requireNonNull(collection);
        return collection.stream().allMatch(this::contains);
    }

    @Override
    public boolean addAll(final Collection<? extends E> collection) {
        return addAll(size(), collection);
    }

    @Override
    public boolean addAll(final int index, final Collection<? extends E> collection) {
        Objects.requireNonNull(collection);
        assertIndexExclusive(index);
        if (collection.isEmpty()) {
            return false;
        }
        ListIterator<E> listIterator = listIterator(index);
        collection.forEach(listIterator::add);
        return true;
    }

    @Override
    public boolean removeAll(final Collection<?> collection) {
        Objects.requireNonNull(collection);
        if (collection.isEmpty()) {
            return false;
        }
        int deletions = 0;
        ListIterator<E> listIterator = listIterator();
        while (listIterator.hasNext()) {
            E next = listIterator.next();
            if (collection.stream().anyMatch(elem -> elem.equals(next))) {
                listIterator.remove();
                deletions++;
            }
        }
        return (deletions > 0);
    }

    @Override
    public boolean retainAll(final Collection<?> collection) {
        Objects.requireNonNull(collection);
        if (collection.isEmpty()) {
            return false;
        }
        int deletions = 0;
        ListIterator<E> listIterator = listIterator();
        while (listIterator.hasNext()) {
            E next = listIterator.next();
            if (collection.stream().noneMatch(elem -> elem.equals(next))) {
                listIterator.remove();
                deletions++;
            }
        }
        return (deletions > 0);
    }

    @Override
    public void clear() {
        if (isEmpty()) {
            return;
        }
        connect(head, tail);
        modifySize(-size());
    }

    @Override
    public E get(final int index) {
        assertIndex(index);
        return listIterator(index).next();
    }

    @Override
    public E set(final int index, final E element) {
        if (this == element) {
            throw new IllegalArgumentException();
        }
        assertIndex(index);
        ListIterator<E> listIterator = listIterator(index);
        E old = listIterator.next();
        listIterator.set(element);
        return old;
    }

    @Override
    public void add(final int index, final E element) {
        if (this == element) {
            throw new IllegalArgumentException();
        }
        assertIndexExclusive(index);
        ListIterator<E> listIterator = listIterator(index);
        listIterator.add(element);
    }

    @Override
    public E remove(final int index) {
        assertIndex(index);
        ListIterator<E> listIterator = listIterator(index);
        E old = listIterator.next();
        listIterator.remove();
        return old;
    }

    @Override
    public int indexOf(final Object object) {
        ListIterator<E> listIterator = listIterator();
        while (listIterator.hasNext()) {
            if (listIterator.next().equals(object)) {
                return listIterator.nextIndex() - 1;
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(final Object object) {
        ListIterator<E> listIterator = listIterator(size());
        while (listIterator.hasPrevious()) {
            if (listIterator.previous().equals(object)) {
                return listIterator.previousIndex() + 1;
            }
        }
        return -1;
    }

    @Override
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }

    @Override
    public ListIterator<E> listIterator(final int index) {
        assertIndexExclusive(index);
        ListIterator<E> listIterator;
        if (isEmpty()) {
            listIterator = listNodeIteratorEmpty();
        }
        else if (index <= size() / 2) {
            listIterator = listNodeIteratorFromHead();
            while (listIterator.hasNext() && index != listIterator.nextIndex()) {
                listIterator.next();
            }
        }
        else {
            listIterator = listNodeIteratorFromTail();
            while (listIterator.hasPrevious() && index != listIterator.nextIndex()) {
                listIterator.previous();
            }
        }
        return listIterator;
    }

    @Override
    public List<E> subList(final int fromIndex, final int toIndex) {
        if (fromIndex < 0 || toIndex > size() || fromIndex > toIndex) {
            throw new IndexOutOfBoundsException();
        }
        if (toIndex - fromIndex == 0) {
            return new LinkedList<>(head, head.next, 0, this);
        }
        ListIterator<Node> listIterator = new LinkedListNodeListIterator();
        while (listIterator.hasNext() && fromIndex != listIterator.nextIndex()) {
            listIterator.next();
        }
        Node fromNode = listIterator.next();
        while (listIterator.hasNext() && toIndex != listIterator.nextIndex()) {
            listIterator.next();
        }
        Node toNode = listIterator.previous();
        return new LinkedList<>(fromNode.previous, toNode.next, toIndex - fromIndex, this);
    }

    @Override
    public boolean equals(final Object other) {
        if (other == null) {
            return false;
        }
        if (!(other instanceof List<?>)) {
            return false;
        }
        List<?> otherList = (List<?>)other;
        if (size() != otherList.size()) {
            return false;
        }
        Iterator<E> iterator = iterator();
        Iterator<?> otherIterator = otherList.iterator();
        while (iterator.hasNext() && otherIterator.hasNext()) {
            E next = iterator.next();
            Object otherNext = otherIterator.next();
            if (!Objects.equals(next, otherNext)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public int hashCode() {
        return Objects.hash(iteratorToStream().toArray());
    }

    @Override
    public String toString() {
        return "[" + iteratorToStream()
                .map(object -> (object == null ? "null" : object.toString()))
                .collect(Collectors.joining(", ")) + "]";
    }

    private void assertIndex(final int index) {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException();
        }
    }

    private void assertIndexExclusive(final int index) {
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException();
        }
    }

    private void modifySize(final int deltaSize) {
        size += deltaSize;
        if (parentList != null) {
            parentList.modifySize(deltaSize);
        }
    }

    private void incrementModificationsCount() {
        modificationsCount++;
        if (parentList != null) {
            parentList.incrementModificationsCount();
        }
    }

    private Stream<E> iteratorToStream() {
        return StreamSupport.stream(spliterator(), false);
    }

    private LinkedListListIterator listNodeIteratorEmpty() {
        return new LinkedListListIterator(-1, head, 0, tail);
    }

    private LinkedListListIterator listNodeIteratorFromHead() {
        return new LinkedListListIterator(-1, head, 0, head.next);
    }

    private LinkedListListIterator listNodeIteratorFromTail() {
        return new LinkedListListIterator(size() - 1, tail.previous, size(), tail);
    }

    @SafeVarargs
    private final void connect(final Node... nodes) {
        if (nodes.length == 0 || nodes.length == 1) {
            throw new IllegalArgumentException();
        }
        for (int i = 0; i < nodes.length - 1; i++) {
            Node node = nodes[i];
            node.next = nodes[i + 1];
            nodes[i + 1].previous = node;
        }
    }

    private class Node {
        public E value;
        public Node next;
        public Node previous;

        public Node(final E value) {
            this.value = value;
        }

        public boolean hasNext() {
            return (next != null);
        }

        public boolean hasPrevious() {
            return (previous != null);
        }

        @Override
        public String toString() {
            return "(" + value + ")";
        }
    }

    private class LinkedListListIterator implements ListIterator<E> {
        private Node next;
        private Node previous;
        private int nextIndex;
        private int previousIndex;

        private boolean removeAllowed;
        private boolean forward;
        private int expectedModificationsCount;

        public LinkedListListIterator(final int previousIndex, final Node previousNode, final int nextIndex, final Node nextNode) {
            this.next = nextNode;
            this.previous = previousNode;
            this.nextIndex = nextIndex;
            this.previousIndex = previousIndex;
            this.expectedModificationsCount = modificationsCount;
        }

        @Override
        public boolean hasNext() {
            return (next != tail);
        }

        @Override
        public E next() {
            checkConcurrentModification();
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            previous = next;
            next = next.next;
            nextIndex++;
            previousIndex++;
            forward = true;
            removeAllowed = true;
            return previous.value;
        }

        @Override
        public boolean hasPrevious() {
            return (previous != head);
        }

        @Override
        public E previous() {
            checkConcurrentModification();
            if (!hasPrevious()) {
                throw new NoSuchElementException();
            }
            next = previous;
            previous = previous.previous;
            previousIndex--;
            nextIndex--;
            forward = false;
            removeAllowed = true;
            return next.value;
        }

        @Override
        public int nextIndex() {
            if (next == null) {
                return size();
            }
            return nextIndex;
        }

        @Override
        public int previousIndex() {
            if (previous == null) {
                return -1;
            }
            return previousIndex;
        }

        @Override
        public void remove() {
            checkConcurrentModification();
            if (!removeAllowed) {
                throw new IllegalStateException();
            }
            if (forward) {
                previous = previous.previous;
                previousIndex--;
                nextIndex--;
            }
            else {
                next = next.next;
            }
            connect(previous, next);
            decrementSize();
            incrementModificationsCount();
            removeAllowed = false;
        }

        @Override
        public void set(final E element) {
            checkConcurrentModification();
            if (!removeAllowed) {
                throw new IllegalStateException();
            }
            Node old = (forward) ? previous : next;
            old.value = element;
        }

        @Override
        public void add(final E element) {
            checkConcurrentModification();
            Node node = new Node(element);
            connect(previous, node, next);
            previous = node;
            previousIndex++;
            nextIndex++;
            incrementSize();
            incrementModificationsCount();
            removeAllowed = false;
        }

        private void incrementSize() {
            modifySize(1);
        }

        private void decrementSize() {
            modifySize(-1);
        }

        private void incrementModificationsCount() {
            expectedModificationsCount++;
            LinkedList.this.incrementModificationsCount();
        }

        private void checkConcurrentModification() {
            if (modificationsCount != expectedModificationsCount) {
                throw new ConcurrentModificationException();
            }
        }
    }

    private class LinkedListNodeListIterator implements ListIterator<Node> {
        private Node previous = head;
        private Node next = head.next;
        private int previousIndex = -1;
        private int nextIndex = 0;

        @Override
        public boolean hasNext() {
            return (next != tail);
        }

        @Override
        public Node next() {
            previous = next;
            next = next.next;
            previousIndex++;
            nextIndex++;
            return previous;
        }

        @Override
        public boolean hasPrevious() {
            return (previous != head);
        }

        @Override
        public Node previous() {
            next = previous;
            previous = previous.previous;
            previousIndex--;
            nextIndex--;
            return next;
        }

        @Override
        public int nextIndex() {
            return nextIndex;
        }

        @Override
        public int previousIndex() {
            return previousIndex;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        @Override
        public void set(final Node node) {
            throw new UnsupportedOperationException();
        }

        @Override
        public void add(final Node node) {
            throw new UnsupportedOperationException();
        }
    }
}
share|improve this question
add comment

3 Answers 3

up vote 8 down vote accepted

Lots of extra objects

The largest single criticism I have is the creation of LinkedLists where they are not necessary. Creating Objects in Java is a performance issue, especially when done often.

Methods like the following:

@Override
public E get(final int index) {
    assertIndex(index);
    return listIterator(index).next();
}

Create an object (the ListIterator) in order to get a member. This is overkill.

This pattern is repeated often.

Rule of thumb, if your code is going to act on just one member in the list, then using an iterator is probably not the best solution.

Iterator "implemented"

The bulk of your logic is implemented in the ListIterator. This is a backwards way of doing it. The Iterator should call methods bck in the list, and not the other way around.

assertIndexExclusive

This should be called assertIndexInclusive (it includes the range end).

Bug in subList

The following code:

public List<E> subList(final int fromIndex, final int toIndex) {
    .....
    if (toIndex - fromIndex == 0) {
        return new LinkedList<>(head, head.next, 0, this);
    }

is buggy. Your code will create the sublist in the wrong place if, for example, fromIndx and toIndex are both 1.

Bugs in clear()

clear() is not modifying the modifiedCount. It should (but only if the list was not empty)

General, small things

  • iterator() should be really fast and 'tight'. Iterators are used extensively for things like enhanced-for loops in Java. Borrowing a LinkedList is a heavy-weight solution for something that should be fast.
  • head and tail in your LinkedList could be final.
share|improve this answer
add comment

You are using non-static inner classes for the items in your list (class Node). Using an inner class means every Node object has access to the enclosing object (LinkedList in your case).

Since you do not use that access in the class Node, you are wasting memory for no gains. Every Node object you create for your list also has an invisible reference to the enclosing LinkedList object. This increases the required memory for storing a list by about 20% (for lists that contain more than a few items).

This can be solved by using a static nested class instead. However, it's not possible to use the generic type (E) in the static class. But since the class is private, this is not required and can be changed to Object, as the class is not accessible from the outside (so your LinkedList class controls which object types are used, namely only the generic type).

share|improve this answer
1  
Good spot. As for the generic type of the Node, it can be declared with it's own generic type: private static final class Node<N> { .... } and then internally it will have public N value; and Node<N> next; .... etc. –  rolfl Apr 9 at 15:07
    
Good suggestion. A static nested class with its own generic type is probably the best way to go about this. –  Thalur Apr 9 at 15:17
add comment

While your code is meant to reinvent the wheel, I would suggest a way that involves slightly less reinvention: AbstractSequentialList. This class implements all methods in the list interface just using the ListIterator, so you only need to actually nclude code for the listIterator and size methods.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.