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
*
* @author Raider
* @param <E>
*
*/

transient CustomNode<E> first;

transient CustomNode<E> last;

transient int length;

/**
* Constructor básico
*/
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
*/
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
*/
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) {
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
*/
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 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.junit.jupiter.api.Test;

@Test

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() {

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

}

@Test
public void isEmpty() {

assertEquals(true, strList.isEmpty());
assertEquals(false, strList.isEmpty());

}

@Test
public void size() {

assertEquals(0, strList.size());

assertEquals(4, strList.size());

}

@Test

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

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

@Test

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("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());

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

@Test

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("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() {

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() {

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());

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() {

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() {

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

}

@Test
public void indexOf() {

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

• what is academic solution? Aug 27 '19 at 13:08
• I don't know, I expect someone can tell me... Aug 27 '19 at 13:11
• maybe you should have asked for clarification on the academic requirement Aug 27 '19 at 13:25
• @SharonBenAsher Usually, one that is needlessly complicated and has no practical use except to impress other academics. Aug 28 '19 at 0:54
• An academic solution would be one that closely syncs up to the concept of a linked-list, without regard for implementation concerns. By contrast, normally when you program up stuff, you'd be interested in making your code as useful as possible -- you might put in optimizations, omit features no one'd ever use, add in features that're very helpful even if they're not necessary for a "linked list", etc.. I mean, yeah, you should probably ask for clarification, but it sounds like they're asking you for a concept-first implementation rather than something someone'd actually want to use.
– Nat
Aug 29 '19 at 1:56

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 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:

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> {

} else {
}
}

public boolean contains(T element) {
return false;
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.

• When I hear about "academic-style double-linked list", the first thing that comes to my mind is "persistent data structures". So, the add() method would return a new linked list, etc. Aug 28 '19 at 20:31
• @Joker_vD A persistent doubly-linked list is not a trivial thing Sep 19 '19 at 18:14

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() {

assertEquals(true, strList.isEmpty());
assertEquals(false, strList.isEmpty());

}


could become something more like the below

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

@Test
public void nonEmptyListReturnsFalseOnIsEmpty() {
assertFalse(strList.isEmpty());
}

@Test
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.getFirst();
}

• 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).

• one solution for that tripple bool check is to only check one of them, and add asserts for the other 2 (en.wikibooks.org/wiki/Java_Programming/Keywords/assert) in production code, the asserts should be disabled, since the class 'should' be written in a way these asserts never trigger. Aug 27 '19 at 21:12

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....

• As I said in 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. But not implement equals() and hashCode() it's a really big mistake, thanks Aug 27 '19 at 13:18
• what does it mean "it would not be used"? anyway, you can look for missing functionality in those interfaces. and implementing methods of Object is a basic requirement. like I said, the class does not support comparing two lists at all Aug 27 '19 at 13:21
• They said I mustn't implement collection Aug 27 '19 at 13:23
• The OP's last edit of the question invalidates this answer. I suggest we roll back the question, what do you think? Aug 27 '19 at 13:47
• 1) in my comment I explained that collection interfaces can be used as source to show missing functionality 2) I further explained about the critical importance of the contract specified in Object Aug 27 '19 at 13:58

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.