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.


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; = null;
        this.previous = null;

    private ListEntry(E element, ListEntry previous, ListEntry next) {
        this.element = element;
        this.previous = previous; = 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) { = 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;
    BigInteger i = BigInteger.ZERO;
    HugeLinkedListIterator iterator = (HugeLinkedListIterator) iterator();
    while (iterator.hasNext()){
        assert i.compareTo(index) <= 0;
        V elem =;
        if (i.compareTo(index) == 0){
    ListEntry current = iterator.getCurrent();
    if (iterator.hasPrevious()){
        ListEntry entry = new ListEntry<>(element, iterator.getPrevious(), current);
    else {
        ListEntry entry = new ListEntry<>(element, null, current);
    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 =;
   = next;
            next.previous = previous;
        else {
   = null;
        assert list.size.compareTo(BigInteger.ZERO) > 0;
        this.list.size = this.list.size.subtract(BigInteger.ONE);
    else {
        if ( != null){
            HugeLinkedList<E>.ListEntry<E> nextEntry =;
            assert this.list.size.compareTo(BigInteger.ZERO) > 0;
            this.list.size = this.list.size.subtract(BigInteger.ONE);
   = nextEntry;
        } = 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 != null;
    return current.previous != null;

public E next() {
    if (!hasNext()){
        throw new NoSuchElementException("There is no next element");
    if (moveForward){
        current =;
    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.


Setting up KVM on Debian Stretch

Since a few months I have Debian 9 (“Stretch”) running on my notebook. Yesterday I wanted to install a virtual machine with Windows 7 running on it for testing some applications. So I tried to install VirtualBox through the Debian repository but I had to find out, that VirtualBox no longer is contained in the repository. So I tried to make it run by installing the .deb package provided on oracles website, but I did not make it. Because of this I decided to check out KVM. This is a virtualisation software being contained in the linux kernel and some forum entries on google claim it is as fast as VirtualBox, but on my system it took some configuration before I was able to successfully start a VM on with it.

First of all, you need to check if your System has the Intel-VT or AMD-V instruction set, because KVM will not be able to run without it. According to, this can be done the following way:

# sudo apt-get install msr-tools
# sudo modprobe msr
# sudo rdmsr 0x3a

If the result of this call is 3 or 5, the instruction set is supported. Now install the client software:

# sudo apt-get install qemu-kvm

You also should add a GUI for more comfortable configuration:

# sudo apt-get install virt-manager

When you now try to start the VM, you maybe will get following message:

failed to initialize: permission denied

As stated out on issue #1095, You solve this by restarting the KVM kernel modules:

# sudo rmmod kvm_intel
# sudo rmmod kvm
# sudo modprobe kvm
# sudo modprobe kvm_intel

Now you can create a new virtual machine and starting it using virt-manager.