Find most "academic" implementation of doubly linked list

Question

Recently, a company has asked me to make an implementation of a doubly linked list with unity tests to test my skills. In the task description they specified that the solution should be as academic as possible. After seeing the test, they said it was not passed, so, since they have not specified what could be improved or what was directly wrong, I was hoping to find the answer here.

Here is my code

package org.raider.list;

/**
 * Lista doblemente enlazada con métodos básicos de inserción, consulta y
 * borrado
 *
 * @author Raider
 * @param <E>
 *
 */
public class CustomDoubleLinkedList<E> {

    transient CustomNode<E> first;

    transient CustomNode<E> last;

    transient int length;

    /**
     * Constructor básico
     */
    public CustomDoubleLinkedList() {
        this.first = null;
        this.last = null;
        this.length = 0;
    }

    /**
     * Método para comprobar si la lista está vacia
     *
     * @return
     */
    public boolean isEmpty() {
        return this.length == 0 && this.first == null && this.last == null;
    }

    /**
     * Devuelve el tamaño de la lista
     *
     * @return número de elementos de la lista
     */
    public int size() {
        return this.length;
    }

    /**
     * Agrega un elemento al final de la lista
     *
     * @param element
     */
    public void add(E element) {
        final CustomNode<E> lastElm = this.last;
        final CustomNode<E> newCustomNode = new CustomNode<>(lastElm, element, null);
        this.last = newCustomNode;
        if (lastElm == null) {
            this.first = newCustomNode;
        } else {
            lastElm.nextItem = newCustomNode;
        }
        this.length++;
    }

    /**
     * Agrega un elemento al principio de la lista
     *
     * @param element
     */
    public void addAtBegin(E element) {
        final CustomNode<E> firstElm = this.first;
        final CustomNode<E> newCustomNode = new CustomNode<>(null, element, firstElm);
        this.first = newCustomNode;
        if (firstElm == null) {
            this.last = newCustomNode;
        } else {
            firstElm.prevItem = newCustomNode;
        }
        this.length++;
    }

    /**
     * Agrega un elemento en una determinada índice (comienza en 0)
     *
     * @param elem  elemento a agregar
     * @param index índice
     */
    public void addAt(E elem, int index) {
        if (index == 0) {
            addAtBegin(elem);
            return;
        } else {
            CustomNode<E> existingNode =  searchNode(index);
            CustomNode<E> newElem = new CustomNode<>(null, elem, null);

            CustomNode<E> tmp = existingNode.prevItem;

            newElem.nextItem = existingNode;
            tmp.nextItem = newElem;
            newElem.prevItem = tmp;
            existingNode.prevItem = newElem;

        }
        this.length++;
    }

    /**
     * Agregamos todos los elementos de una lista en una determinada posición de
     * otra
     *
     * @param index lugar a partir del que añadiremos la otra lista
     * @param list  lista a añadir
     */
    public void addAll(int index, CustomDoubleLinkedList list) {
        int originalSize = list.size();
        if (originalSize > 0) {
            CustomNode<E> prev;
            CustomNode<E> next;
            if (index == originalSize) {
                next = null;
                prev = this.last;
            } else {
                next = searchNode(index);
                prev = next.prevItem;
            }

            for (int i = 0; i < originalSize; i++) {
                E e = (E) list.get(i);
                CustomNode<E> newNode = new CustomNode<>(prev, e, null);
                if (prev == null) {
                    this.first = newNode;
                } else {
                    prev.nextItem = newNode;
                }
                prev = newNode;
            }

            if (next == null) {
                this.last = prev;
            } else {
                prev.nextItem = next;
                next.prevItem = prev;
            }

            this.length += originalSize;
        }
    }

    /**
     * Elimina todos los elementos de la lista
     */
    public void clear() {
        /*
         * Realmente podríamos eliminar el primero, el último y poner el tamaño a 0,
         * pero de esta forma nos aseguramos liberar memoria
         */
        CustomNode<E> cn = this.first;
        for (int i = 0; i < this.length; i++) {
            CustomNode<E> next = cn.nextItem;
            cn.item = null;
            cn.nextItem = null;
            cn.prevItem = null;
            cn = next;
        }
        this.first = null;
        this.last = null;
        this.length = 0;
    }

    /**
     * Elimina todos los elementos que coincidan
     *
     * @param element
     */
    public void remove(Object element) {
        for (int i = 0; i < this.length; i++) {
            CustomNode<E> node = searchNode(i);
            if (element == null) {
                if (node.item == null) {
                    deleteNode(node);
                }
            } else {
                if (element.equals(node.item)) {
                    deleteNode(node);
                }
            }
        }

    }

    /**
     * Elimina un elemento en determinado índice
     *
     * @param index
     */
    public void removeIndex(int index) {
        CustomNode<E> node = searchNode(index);
        deleteNode(node);
    }

    /**
     * Obtiene un elemento por su índice
     *
     * @param index índice
     * @return elemento
     * @throws NullPointerException si el objeto es null
     */
    public E get(int index) {
        CustomNode<E> node = searchNode(index);
        return node.item;
    }

    /**
     * Devuelve el primer elemento
     *
     * @return elemento
     */
    public E getFirst() {
        return this.first.item;
    }

    /**
     * Devuelve el ultimo elemento
     *
     * @return elemento
     */
    public E getLast() {
        return this.last.item;
    }

    /**
     * Devuelve el índice de un objeto, si no existe, devuelve -1
     *
     * @param element elemento a buscar
     * @return índice del objeto o -1
     */
    public int indexOf(E element) {
        int index = -1;
        for (int i = 0; i < this.length; i++) {
            // for (CustomNode<E> node = first; node != null; node = node.nextItem) {
            CustomNode<E> node = searchNode(i);
            if (element == null) {
                if (node.item == null) {
                    index = i;
                    break;
                }
            } else {
                if (element.equals(node.item)) {
                    index = i;
                    break;
                }
            }
        }
        return index;
    }

    /**
     * Elimina un nodo
     *
     * @param node
     */
    private void deleteNode(CustomNode<E> node) {
        final E element = node.item;
        final CustomNode<E> next = node.nextItem;
        final CustomNode<E> prev = node.prevItem;

        if (prev == null) {
            this.first = next;
        } else {
            prev.nextItem = next;
            node.prevItem = null;
        }

        if (next == null) {
            this.last = prev;
        } else {
            next.prevItem = prev;
            node.nextItem = null;
        }

        node.item = null;
        this.length--;
    }

    /**
     * Devuelve un nodo de una determinada posición
     *
     * @param index indice
     * @return nodo
     */
    private CustomNode<E> searchNode(int index) {
        /*
         * Si index < 0 cogeremos el primer elemento y si es mayor que la longitud
         * cogeremos el último
         */
        if (index < 0) {
            index = 0;
        }
        if (index < this.length) {
            CustomNode<E> aux = this.first;
            for (int i = 0; i < index; i++) {
                aux = aux.nextItem;
            }
            return aux;
        } else {
            CustomNode<E> aux = last;
            return aux;
        }
    }

    /**
     * Clase CustomNode (nombrada así debido a que ya existe una similar en java)
     * que usaremos para obtener los valores anterior y posterior de un determinado
     * elemento de la lista
     *
     * @author Raider
     *
     * @param <E> Parámetro genéico para que nuestra lista pueda aceptar todos los
     *            tipos de parámetros
     */
    private static class CustomNode<E> {
        E item;
        CustomNode<E> nextItem;
        CustomNode<E> prevItem;

        /**
         * Constructor de CustomNode
         *
         * @param prev    elemento anterior
         * @param element elemento referenciado
         * @param next    elemento siguiente
         */
        CustomNode(CustomNode<E> prev, E element, CustomNode<E> next) {
            this.item = element;
            this.nextItem = next;
            this.prevItem = prev;
        }
    }

}

And here JUnit tests (surely the worst part)

package org.raider.junit.tests;

import static org.junit.Assert.assertEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;

import org.aam.list.CustomDoubleLinkedList;
import org.junit.jupiter.api.Test;

class CustomDoubleLinkedListTest {

    CustomDoubleLinkedList<String> strList;

    @Test
    public void addAndGetTest() {
        strList = new CustomDoubleLinkedList();

        strList.add("pos 0");
        strList.add("pos 1");
        strList.add("pos 2");
        strList.add("pos 3");

        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 1", strList.get(1));
        assertEquals("pos 2", strList.get(2));
        assertEquals("pos 3", strList.get(3));
    }

    @Test
    public void outOfBounds() {
        strList = new CustomDoubleLinkedList();

        strList.add("pos 0");
        strList.add("pos 1");
        strList.add("pos 2");
        strList.add("pos 3");

        assertEquals("pos 3", strList.get(288));
        assertEquals("pos 0", strList.get(-100));

    }

    @Test
    public void isEmpty() {
        strList = new CustomDoubleLinkedList();

        assertEquals(true, strList.isEmpty());
        strList.add("pos 0");
        assertEquals(false, strList.isEmpty());

    }

    @Test
    public void size() {
        strList = new CustomDoubleLinkedList();

        assertEquals(0, strList.size());

        strList.add("pos 0");
        strList.add("pos 1");
        strList.add("pos 2");
        strList.add("pos 3");

        assertEquals(4, strList.size());

    }

    @Test
    public void addAtBegin() {
        strList = new CustomDoubleLinkedList();

        strList.add("pos 0");
        strList.add("pos 1");
        strList.add("pos 2");
        strList.add("pos 3");

        assertEquals("pos 0", strList.get(0));

        strList.addAtBegin("pos -1");

        assertEquals("pos -1", strList.get(0));
        assertEquals("pos 0", strList.get(1));
    }

    @Test
    public void addAt() {
        strList = new CustomDoubleLinkedList();

        strList.add("pos 0");
        strList.add("pos 1");
        strList.add("pos 2");
        strList.add("pos 3");

        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 1", strList.get(1));
        assertEquals("pos 2", strList.get(2));
        assertEquals("pos 3", strList.get(3));

        strList.addAt("pos x", 2);

        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 1", strList.get(1));
        assertEquals("pos x", strList.get(2));
        assertEquals("pos 2", strList.get(3));
        assertEquals("pos 3", strList.get(4));

        assertEquals(5, strList.size());

        strList.addAt("pos y", 0);

        assertEquals("pos y", strList.get(0));
    }

    @Test
    public void addAll() {
        strList = new CustomDoubleLinkedList();
        CustomDoubleLinkedList<String> listToAdd = new CustomDoubleLinkedList();

        strList.add("pos 0");
        strList.add("pos 1");
        strList.add("pos 2");
        strList.add("pos 3");

        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 1", strList.get(1));
        assertEquals("pos 2", strList.get(2));
        assertEquals("pos 3", strList.get(3));

        listToAdd.add("pos x");
        listToAdd.add("pos y");
        listToAdd.add("pos z");

        assertEquals("pos x", listToAdd.get(0));
        assertEquals("pos y", listToAdd.get(1));
        assertEquals("pos z", listToAdd.get(2));

        strList.addAll(2, listToAdd);

        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 1", strList.get(1));
        assertEquals("pos x", strList.get(2));
        assertEquals("pos y", strList.get(3));
        assertEquals("pos z", strList.get(4));
        assertEquals("pos 2", strList.get(5));
        assertEquals("pos 3", strList.get(6));
    }

    @Test
    public void clear() {
        strList = new CustomDoubleLinkedList();

        strList.add("pos 0");
        strList.add("pos 1");
        strList.add("pos 2");
        strList.add("pos 3");

        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 1", strList.get(1));
        assertEquals("pos 2", strList.get(2));
        assertEquals("pos 3", strList.get(3));

        assertEquals(4, strList.size());

        strList.clear();
        assertThrows(NullPointerException.class, () -> strList.get(0));
        assertThrows(NullPointerException.class, () -> strList.get(1));
        assertThrows(NullPointerException.class, () -> strList.get(2));
        assertThrows(NullPointerException.class, () -> strList.get(3));

        assertEquals(0, strList.size());
    }

    @Test
    public void remove() {
        strList = new CustomDoubleLinkedList();

        strList.add("pos 0");
        strList.add("pos 1");
        strList.add("pos 2");
        strList.add("pos 3");

        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 1", strList.get(1));
        assertEquals("pos 2", strList.get(2));
        assertEquals("pos 3", strList.get(3));

        assertEquals(4, strList.size());

        strList.remove("pos 2");
        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 1", strList.get(1));
        assertEquals("pos 3", strList.get(2));

        assertEquals(3, strList.size());

        strList.add("pos 1");
        strList.add("pos 4");

        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 1", strList.get(1));
        assertEquals("pos 3", strList.get(2));
        assertEquals("pos 1", strList.get(3));
        assertEquals("pos 4", strList.get(4));

        assertEquals(5, strList.size());

        strList.remove("pos 1");

        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 3", strList.get(1));
        assertEquals("pos 4", strList.get(2));

        assertEquals(3, strList.size());

    }

    @Test
    public void removeIndex() {
        strList = new CustomDoubleLinkedList();

        strList.add("pos 0");
        strList.add("pos 1");
        strList.add("pos 2");
        strList.add("pos 3");

        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 1", strList.get(1));
        assertEquals("pos 2", strList.get(2));
        assertEquals("pos 3", strList.get(3));

        assertEquals(4, strList.size());

        strList.removeIndex(2);

        assertEquals("pos 0", strList.get(0));
        assertEquals("pos 1", strList.get(1));
        assertEquals("pos 3", strList.get(2));

        assertEquals(3, strList.size());

    }

    @Test
    public void getFirstAndLast() {
        strList = new CustomDoubleLinkedList();

        strList.add("pos 0");
        strList.add("pos 1");
        strList.add("pos 2");
        strList.add("pos 3");

        assertEquals("pos 0", strList.getFirst());
        assertEquals("pos 3", strList.getLast());

    }

    @Test
    public void indexOf() {
        strList = new CustomDoubleLinkedList();

        strList.add("pos 0");
        strList.add("pos 1");
        strList.add("pos 2");
        strList.add("pos 3");

        assertEquals(2, strList.indexOf("pos 2"));

    }

}

Could someone try to explain me where I can improve this code, what I forgot or what is the most academic way to do this?

EDIT: I didn't implement or extend from Collection or another interfaces/clasess because in the test it was specified that it would not be used

Answer 1

Next time you're in such a scenario, ask them to clarify what "academic" means. For me it means a solution that concentrates on the essence of data structure, not an implementation of a specific API. But we probably never know so let's not concentrate on that. Instead, let's look at the red flags...

(I have ignored the comments as I do not understand the language.)

Transient

The first red flag that jumps at me is the transient keywords. Your collection does not implement Serializable so the keyword does not mean anything. It's a sign to thereader that you don't understand what transient means.

Non-private fields

The fields in CustomeDoubleLinkedList are not private so they are visible to all classes defined in the same package, allowing for other parties to break the internal state of the collection.

Redundant code

The isEmpty() method relies on three different fields to figure out if it is empty. You should be confident enough in your code and tests to rely on just the length counter. If you use a static code analyzer it rises a flag every time you use "collection.size() == 0" and recommends to use "isEmpty()". Your isEmpty should work likewise.

Inconsistent naming

The add() and addAtBeginning() are a bit inconsistent. The latter explicitly states it adds to the beginning while the former has to rely on documentation. I would have been looking for addLast() and addFirst() or add() and addAt(0).

The addAll() doesn't convey in it's name that it requires an index parameter like addAt() does.

The removeIndex() is inconsitent with addAt(). Should be removeAt().

Range checking

The addAt method does not check if index is beyond the size of the collection. A method that returns a valid value with invalid input is surprising behaviour which welcomes programming errors from the caller. An IllegalArgumentException should be thrown here.

Inconsistent parameters

The addAt and addAll have the index parameter at different part of the method signature. It should be first or last in both.

Generics or not?

The addAll does not use the generic type declared in the class signature.

Unnecessary code

The clear-method should just set the first and last to null and size to zero and let the garbage collector deal with the rest.

No null checking

The getFirst and getLast throw NullPointerExceptions if the list is empty.

Code duplication

You have copy-pasted the linking of nodes to their successors and predecessors to several places. Those should have been refactored to private methods like "insertAfter(existingNode, newNode)" and "insertBefore(existingNode, newNode)" or made that operation a function of the Node.

There may be more, but I have to go now.

Edit:

Academic shmacademic

I want to contemplate this a bit. A linked list is a recursive data structure consisting of a head node and a tail (which is a linked list). Prolog programmers know this by heart. Your solution is pragmatic and concentrates on the collection API.

It may have been that they wanted you to concentrate more on the recursive nature of the Node-class. Something like this (you need to imagine the double linking :) ):

public class LinkedList<T> {
    private T head = null;
    private LinkedList<T> tail = null;

    public void add(T element) {
        if (head == null) {
            head = element;
            tail = new LinkedList<>();
        } else {
            tail.add(element);
        }
    }

    public boolean contains(T element) {
        if (head == null) {
            return false;
        } else if (head.equals(element)) {
            return true;
        } else {
            return tail.contains(element);
        }
    }

    ...
}

Anyway... What you can get out of this is knowing that asking clarifying questions in a job interview is a good thing.

Answer 2

With regard to the academic solution, perhaps they were referring to things like you would see in an assignment such as line lengths, appropriate naming and use of visibility modifiers, no compilation errors, etc.

• I feel your javadocs could have been better, equally there are @params that have no detail about the expected parameter such as in the add(E element) and addAtBegin(E element) methods.
• There were a few places where you should have used generics such as the addAll(int index, CustomDoubleLinkedList list) method should have been public void addAll(int index, CustomDoubleLinkedList<? extends E> list)

There were a few improvements you could make to the unit tests as well. While it looks like the code coverage is 90%, there are lots of edge cases and subtleties that aren't clear and the unit tests tell as much about what you can do with a class as what you can't do with it.

• You are mixing jUnit 4 and 5
  • org.junit.Assert.assertEquals is jUnit 4, while
  • org.junit.jupiter.api.Assertions.assertThrows is jUnit 5.
• If you are using jUnit 5 the public is not required for each method. It was excluded for the class but not the tests.
• You didn't use the <> operator on any of the instantiations of the CustomDoubleLinkedList.
• Ideally you should have one assert per method.
  • This isn't a hard and fast rule but for testing a method like isEmpty() it may be preferable.
  • If the list should return true to isEmpty() once everything has been removed, a test should assert that.

@Test
public void isEmpty() {
    strList = new CustomDoubleLinkedList();

    assertEquals(true, strList.isEmpty());
    strList.add("pos 0");
    assertEquals(false, strList.isEmpty());

}

could become something more like the below

@Test
public void emptyListReturnsTrueOnIsEmpty() {
    strList = new CustomDoubleLinkedList();
    assertTrue(strList.isEmpty());
}

@Test
public void nonEmptyListReturnsFalseOnIsEmpty() {
    strList = new CustomDoubleLinkedList();
    strList.add("pos 0");
    assertFalse(strList.isEmpty());
}

@Test
public void addedToAndRemovedFromListReturnsTrueOnIsEmpty() {
    strList = new CustomDoubleLinkedList();
    strList.add("pos 0");
    strList.remove("pos 0");
    assertTrue(strList.isEmpty());
}

While you have said you were asked not to implement Java Collections, the Deque interface getFirst() method says you should throw a no such element exception if the deque is empty. This test throws a null pointer instead

@Test
public void test() {
    strList = new CustomDoubleLinkedList<>();
    strList.getFirst();
}

Answer 3

• searchNode(int i) performs a loop. Wrapping it inside yet another loop makes indexOf and remove(Object element) quadratic in the length of the list, instead of linear which they supposed to be.

• Testing for emptiness via this.length == 0 && this.first == null && this.last == null; feels strange. It is enough to test just for length. If first and/or last happen to be non-null in this situation means that integrity of the list is broken, and probably should cause an exception.

• add and addAtBegin are bit more wordy than necessary. You don't really need lastElm/firstElm.

  While we are here, their names should be more symmetric. Traditionally they are append and prepend, or addFirst/addLast (or even push_front/push_back in C++ parlance).

Answer 4

Your class does not implement any of Java collection interfaces. the solution is meant to be an implementation of a linked list that can be used as drop-in replacement for any java list/collection (and also queue). if you look at the LinkedList from the jdk, you will see just what functionality you are missing. (for example, iterator, subList)

now I see that the class does not even implement the most basic contract from Object (namely, equals() and hashCode()) so you cannot safely compare two lists or put one in hash map....

Answer 5

Since this is the fifth answer I shall try not to repeat many things that have already been said.

---

    public void addAll(int index, CustomDoubleLinkedList list) {
        int originalSize = list.size();
        if (originalSize > 0) {

If this were instead if (originalSize == 0) return; then the rest of the method could save one level of indentation.

            if (index == originalSize) {

I don't understand this line at all, and I think it might be buggy. Why compare an index into this list with the length of the other one?

            for (int i = 0; i < originalSize; i++) {
                E e = (E) list.get(i);

There are two big problems with that line. Firstly, list.get(i) on a linked list inside a loop. This turns a method which should take linear time into a method which takes quadratic time. Secondly, the cast: this would be unnecessary if the argument were properly typed (as CustomDoubleLinkedList<? extends E>).

---

    public void clear() {
        /*
         * Realmente podríamos eliminar el primero, el último y poner el tamaño a 0,
         * pero de esta forma nos aseguramos liberar memoria
         */
        CustomNode<E> cn = this.first;
        for (int i = 0; i < this.length; i++) {
            CustomNode<E> next = cn.nextItem;
            cn.item = null;
            cn.nextItem = null;
            cn.prevItem = null;
            cn = next;
        }
        this.first = null;
        this.last = null;
        this.length = 0;
    }

The reasoning in the comment assumes either that the class is somehow leaking its nodes (in which case you should fix that problem instead) or that the garbage collector is broken (which is highly unlikely). So this turns a method which should take constant time into a method which takes linear time for no good reason.

---

    /**
     * Elimina todos los elementos que coincidan
     *
     * @param element
     */
    public void remove(Object element) {
        for (int i = 0; i < this.length; i++) {
            CustomNode<E> node = searchNode(i);

Was this really what the spec asked for? java.util.Collection.remove removes one instance (and returns a bool indicating whether it found one to remove or not).

Also, this has the same problem of turning a linear method into a quadratic one by using searchNode inside a loop.

---

    public int indexOf(E element) {
        int index = -1;
        for (int i = 0; i < this.length; i++) {
            // for (CustomNode<E> node = first; node != null; node = node.nextItem) {
            CustomNode<E> node = searchNode(i);

Same problem. In fact, worse: it seems that you commented out the correct solution, which might make the interviewer think that you couldn't get it to work.

---

            CustomNode<E> aux = last;
            return aux;

Why not just return last;?

---

    private void deleteNode(CustomNode<E> node) {
        final E element = node.item;

What's element for?

---

While I can't be sure what the interviewer meant by "academic", I think it's very probable that they expected to see every method implemented with the best possible asymptotic complexity.