Implementing an efficient Linked List

Currently I’m doing some refactoring on my Circuit Simulator. For this, I sourced out the graph functionality into an own library, which currently relies on the Java Collections. A problem is, that the Java Collections size() method returns an Integer. That means, if I have more than ~2 billion elements in the list – Javas Integers are signed 32 bit values – the returned size value will be invalid. Because there is no technical limit to the size of the graph to be stored by the graph library except available main memory, I had to find a solution.
so decided to write my own library, called HugeCollections, being able to correctly handle such an amount of elements. One part of it was an implementation of a Linked List which should be as efficient as possible.

Data structure

In a Linked List, there exists an anchor element pointing to the first entry and each entry itself points to the next entry in the list. For my implementation if have chosen the data structure of a doubly Linked List, which means that each entry also points to its predecessor.

This slideshow requires JavaScript.

The pointer of the anhor, which points to the last element is not mandatory, but I used it in my Linked List implementation for speeding up adding elements to the end of the list. Without it, the function which adds the element would have to iterate through the whole list to find the reference to the last element of the list. This approach also allows optimizing the way of reversing the iteration direction of the list.

Another small optimization is related to the size() method. This method returns the amount of elements currently being stored in the list. One approach would be to iterate through each element of the list while counting them on demand. But a more optimal way for implementation is the use of a field in the class managing the list, which stores the current size of the list. each time the add() or remove() method of the list is called, the value of this field gets updated. So when the size of the list shall be determined, the related function only have to return the value of this field instead of counting all elements on demand.

Initialization

When the constructor of the Linked List class is called, a new anchor is created and the size field is set to zero.

this.anchor = new ListEntry<>();
this.size = BigInteger.ZERO;

For simplifying the implementation, I reused the ListEntry class with a element pointer which points to null instead of creating a specialized ListAnchor class. For completeness I attached the source code of the ListEntry class:

protected class ListEntry {
    private E element;
    private ListEntry previous;
    private ListEntry next;

    private ListEntry(){
        this.element = null;
        this.next = null;
        this.previous = null;
    }

    private ListEntry(E element, ListEntry previous, ListEntry next) {
        this.element = element;
        this.previous = previous;
        this.next = next;
    }

    public E getElement() {
        return element;
    }

    public ListEntry getPrevious() {
        return previous;
    }

    public ListEntry getNext() {
        return next;
    }

    public void setElement(E element) {
        assert element != null;
        this.element = element;
    }

    public void setPrevious(ListEntry previous) {
        this.previous = previous;
    }

    public void setNext(ListEntry next) {
        this.next = next;
    }
}

Adding elements to the list

  • Go to the position at which the new element shall be inserted
    • If the current element has a predecessor do the following steps:
      • create a new entry having the current one as ist successor and the predecessor of the current entry as ist predecessor
      • set the successor of the curent elements predecessor to the newly created entry
    • Else do this steps:
      • create a new entry having no predecessor and the current element as its successor
      • set the next-pointer of the anchor to the newly created element
  • Increment the size field by one
public boolean add(BigInteger index, V element) {
    assert index != null;
    assert element != null;
    checkIndex(index);
    BigInteger i = BigInteger.ZERO;
    HugeLinkedListIterator iterator = (HugeLinkedListIterator) iterator();
    while (iterator.hasNext()){
        assert i.compareTo(index) <= 0;
        V elem = iterator.next();
        if (i.compareTo(index) == 0){
            break;
        }
    }
    ListEntry current = iterator.getCurrent();
    if (iterator.hasPrevious()){
        ListEntry entry = new ListEntry<>(element, iterator.getPrevious(), current);
        iterator.getPrevious().setNext(entry);
    }
    else {
        ListEntry entry = new ListEntry<>(element, null, current);
        getAnchor().setNext(entry);
    }
    setSize(size().add(BigInteger.ONE));
    return true;
}

private void checkIndex(BigInteger index) {
    if (index.compareTo(BigInteger.ZERO) < 0){         throw new IndexOutOfBoundsException("Negative index values are not allowed");     }     if (index.compareTo(this.size()) > 0){
        throw new IndexOutOfBoundsException(String.format("No such index number: %s", index));
    }
}

Removing an element from the list

  • If the element to remove has a predeccessor do the following steps:
    • If the element has a successor do following:
      • Set the next-pointer of the predecessor to the successor of the element to delete
      • Set the previous-pointer of the successor to the predecessor of the element to delete
    • Else set the next-pointer of the predecessor to null
    • Decrement the size field by one
  • Else do following steps:
    • If the element to delete have a successor do the following steps:
      • Decrement the size field by one
      • Set the next-pointer of the anchor to the successor of the element to delete
      • Set the previous-pointer of the succesor of the element to delete to null
    • Else do following:
      • Set the next-pointer of the anchor to null
      • Set the size field to zero
      • Set the previous-pointer of the anchor to null
public void remove() {
    HugeLinkedList<E>.ListEntry<E> previous;
    HugeLinkedList<E>.ListEntry<E> next;

    if (current.previous != null){
        previous = current.previous;
        if (hasNext()){
            next = current.next;
            previous.next = next;
            next.previous = previous;
        }
        else {
            previous.next = null;
        }
        assert list.size.compareTo(BigInteger.ZERO) > 0;
        this.list.size = this.list.size.subtract(BigInteger.ONE);
    }
    else {
        if (current.next != null){
            HugeLinkedList<E>.ListEntry<E> nextEntry = current.next;
            assert this.list.size.compareTo(BigInteger.ZERO) > 0;
            this.list.size = this.list.size.subtract(BigInteger.ONE);
            this.list.anchor.next = nextEntry;
            nextEntry.setPrevious(null);
            return;
        }
        this.list.anchor.next = null;
        this.list.size = BigInteger.ZERO;
        this.list.anchor.previous = null;
    }
}

Iterating through the list

When iterating in forward direction, start with the anchor and follow the next-pointers until the next-pointer of the current element is null. Iterating in reverse direction is similar, but you have to follow the previous-pointers instead and stop when the previous-pointer of the current elemen is null.

public boolean hasNext() {
    if (moveForward){
        return current.next != null;
    }
    return current.previous != null;
}

public E next() {
    if (!hasNext()){
        throw new NoSuchElementException("There is no next element");
    }
    if (moveForward){
        current = current.next;
    }
    else {
        current = current.previous;
    }
    return current.element;
}

 

Maybe the lookup of an entry in the list could further be optimized by segmenting the List and storing a reference to the first element and some metainformation (smallest value, highest value, smallest index and highest index) in an Array of fixed size. When the list grows, the segments are realigned and the metainformation will be updated. This would increase the time needed for adding or removing elements, but should speed up finding elements in the list. At some time I will make an implementation and check this out.

Advertisements

How to use mocks

At this weekend I decided to refactor some parts of the circuit simulator, because its source slowly becomes confusing. In detail I began to extract the graph package of the simulator into a new module which can also be used in other projects relying on a graph library. While I was doing this I found out how I can use Mockito for improving my unit tests.

Mockito is a framework for mock creation. This means it wraps classes which your unit tests depend on into dummy classes returning some hardcoded values.

The advantage of this is, that you don’t need working implementations of interfaces which are dependencies of your unit tests but not being part of the functionality you want to test.

Here is an example of an unit test using mocks:

class DijkstraAlgorithmTest {
    private Graph<Integer> graph;
    private List<Node<Integer>> nodes;

    @BeforeEach
    void setUp() throws EdgeException {
        nodes = new LinkedList<>();
        for (int i = 0; i < 10; i++){
            Node<Integer> node = mock(Node.class);
            nodes.add(node);
            when(node.getData()).thenReturn(i);
            when(node.toString()).thenReturn(String.valueOf(i));
        }

        List<Edge<Integer>> edges = new ArrayList<>();
        Edge<Integer> edge;
        edge = mock(Edge.class); //0
        when(edge.getTarget(nodes.get(0))).thenReturn(nodes.get(1));
        when(edge.getTarget(nodes.get(1))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(0))).thenReturn(nodes.get(1));
        edges.add(edge);
        edge = mock(Edge.class); //1
        when(edge.getTarget(nodes.get(1))).thenReturn(nodes.get(4));
        when(edge.getTarget(nodes.get(4))).thenReturn(nodes.get(1));
        when(edge.getSource(nodes.get(4))).thenReturn(nodes.get(1));
        when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(4));
        edges.add(edge);
        edge = mock(Edge.class); //2
        when(edge.getTarget(nodes.get(4))).thenReturn(nodes.get(6));
        when(edge.getTarget(nodes.get(6))).thenReturn(nodes.get(4));
        when(edge.getSource(nodes.get(6))).thenReturn(nodes.get(4));
        when(edge.getSource(nodes.get(4))).thenReturn(nodes.get(6));
        edges.add(edge);
        edge = mock(Edge.class); //3
        when(edge.getTarget(nodes.get(0))).thenReturn(nodes.get(6));
        when(edge.getTarget(nodes.get(6))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(6))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(0))).thenReturn(nodes.get(6));
        edges.add(edge);
        edge = mock(Edge.class); //4
        when(edge.getTarget(nodes.get(6))).thenReturn(nodes.get(2));
        when(edge.getTarget(nodes.get(2))).thenReturn(nodes.get(6));
        when(edge.getSource(nodes.get(2))).thenReturn(nodes.get(6));
        when(edge.getSource(nodes.get(6))).thenReturn(nodes.get(2));
        edges.add(edge);
        edge = mock(Edge.class); //5
        when(edge.getTarget(nodes.get(2))).thenReturn(nodes.get(1));
        when(edge.getTarget(nodes.get(1))).thenReturn(nodes.get(2));
        when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(2));
        when(edge.getSource(nodes.get(2))).thenReturn(nodes.get(1));
        edges.add(edge);
        edge = mock(Edge.class); //6
        when(edge.getTarget(nodes.get(2))).thenReturn(nodes.get(3));
        when(edge.getTarget(nodes.get(3))).thenReturn(nodes.get(2));
        when(edge.getSource(nodes.get(3))).thenReturn(nodes.get(2));
        when(edge.getSource(nodes.get(2))).thenReturn(nodes.get(3));
        edges.add(edge);
        edge = mock(Edge.class); //7
        when(edge.getTarget(nodes.get(1))).thenReturn(nodes.get(3));
        when(edge.getTarget(nodes.get(3))).thenReturn(nodes.get(1));
        when(edge.getSource(nodes.get(3))).thenReturn(nodes.get(1));
        when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(3));
        edges.add(edge);

        graph = mock(Graph.class);
        when(graph.getAllNodes()).thenReturn(new HashSet<>(nodes));
        when(graph.getAllEdges()).thenReturn(new HashSet<>(edges));
        when(graph.getEdges(nodes.get(0))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(0),
                edges.get(3)
        )));
        when(graph.getEdges(nodes.get(1))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(0),
                edges.get(1),
                edges.get(5),
                edges.get(7)
        )));
        when(graph.getEdges(nodes.get(2))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(4),
                edges.get(5),
                edges.get(6)
        )));
        when(graph.getEdges(nodes.get(3))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(6),
                edges.get(7)
        )));
        when(graph.getEdges(nodes.get(4))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(1),
                edges.get(2)
        )));
        when(graph.getEdges(nodes.get(6))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(2),
                edges.get(3),
                edges.get(4)
        )));
    }

    @Test
    void apply1() {
        assertEquals(new Path<>(Arrays.asList(
                nodes.get(0),
                nodes.get(1),
                nodes.get(3)
        )), new DijkstraAlgorithm<Integer>().apply(graph, new DijkstraAlgorithm.Parameters<>(nodes.get(0), nodes.get(3))));
    }

    @Test
    void apply2() {
        assertEquals(new Path<>(Arrays.asList(
                nodes.get(4),
                nodes.get(1),
                nodes.get(3)
        )), new DijkstraAlgorithm<Integer>().apply(graph, new DijkstraAlgorithm.Parameters<>(nodes.get(4), nodes.get(3))));
    }
}

 

Let’s take a more detailed look into what happens in this piece of code. First a list of mocked objects of type Node is created. Node is an interface representing nodes in a graph.

nodes = new LinkedList<>();
        for (int i = 0; i < 10; i++){
            Node<Integer> node = mock(Node.class);
            nodes.add(node);
            when(node.getData()).thenReturn(i);
            when(node.toString()).thenReturn(String.valueOf(i));
        }

The mock(Node.class) instruction creates a new instance of an anonymous class implementing the interface Node.At this point, all methods of the created instance will return null. To be able to work with that instance, it is necessary to specify for each function the unit test will use what it should do.

This is done by the when(…).then(…) instructions:

when(node.getData()).thenReturn(i);

This specifies, that the value of the loop counter i shall be returned when the function getData() of the Node instance is called.

when(node.toString()).thenReturn(String.valueOf(i));

I included this for debugging purposes. It returns the loop counter i formatted into a String when the toString() method of the instance is called. The unit test itself does not use this function, but it make debugging easier because I better can see which node I have when looking at the variables stack of my IDE.

After this it is necessary to mock some edge instances for the graph to be tested:

List<Edge<Integer>> edges = new ArrayList<>();
        Edge<Integer> edge;
        edge = mock(Edge.class); //0
        when(edge.getTarget(nodes.get(0))).thenReturn(nodes.get(1));
        when(edge.getTarget(nodes.get(1))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(0))).thenReturn(nodes.get(1));
        edges.add(edge);
        ...

Create a new mocked instance of an Edge by calling mock(Edge.class). Now specify the getTarget(…) and getSource(…) functions of the Edge:

when(edge.getTarget(nodes.get(0))).thenReturn(nodes.get(1));

This specifies that the node at position 1 of the list nodes shall be returned when getTarget(…) is called for the Edge with the node at position 0 of the list nodes.

when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(0));

This specifies that the node at position 0 of the list nodes is being returned when calling getSource(…) for the Edge with the node at position 1 of the list nodes.

The same way the a mocked instance of Graph is created. Then the actual test is created:

@Test
    void apply1() {
        assertEquals(new Path<>(Arrays.asList(
                nodes.get(0),
                nodes.get(1),
                nodes.get(3)
        )), new DijkstraAlgorithm<Integer>().apply(graph, new DijkstraAlgorithm.Parameters<>(nodes.get(0), nodes.get(3))));
    }

As you can see, you now can use the mocked instances like normal implementations of Graph, Edge and Node.