Circular list vs. doubly-linked list: which is faster?

Question

In this post, I will compare performance of a circular list and a conventional list with head/tail -references:

package com.github.coderodde.sentinellisttexperiment;

public class SentinelListtExperiment {
    
    private static final int ADD_FIRST_N    = 50_000_000;
    private static final int ADD_LAST_N     = 50_000_000;
    private static final int REMOVE_FIRST_N = 50_000_000;
    private static final int REMOVE_LAST_N  = 50_000_000;
    
    public static void main(String[] args) {
        LinkedList list1 = new LinkedList();
        CircularList list2 = new CircularList();
        
        run(list1);
        System.out.println("----------------");
        run(list2);
    }
    
    private static void run(LinkedList list) {
        long duration = 0L;
        duration += runAddFirst(list);
        duration += runAddLast(list);
        duration += runRemoveFirst(list);
        duration += runRemoveLast(list);
        System.out.println(
                list.getClass().getSimpleName() 
                        + " in total " 
                        + duration 
                        + " ms.");
    }
    
    private static long runAddFirst(LinkedList list) {
        long time = System.currentTimeMillis();
        
        for (int i = 0; i < ADD_FIRST_N; i++) {
            list.addFirst(i);
        }
        
        long duration = System.currentTimeMillis() - time;
        
        System.out.println(
                "addFirst on "
                        + list.getClass().getSimpleName()
                        + ": " 
                        + duration 
                        + " ms.");
        
        return duration;
    }
    
    private static long runAddLast(LinkedList list) {
        long time = System.currentTimeMillis();
        
        for (int i = 0; i < ADD_LAST_N; i++) {
            list.addLast(i);
        }
        
        long duration = System.currentTimeMillis() - time;
        
        System.out.println(
                "addLast on "
                        + list.getClass().getSimpleName()
                        + ": " 
                        + duration 
                        + " ms.");
        
        return duration;
    }
    
    private static long runRemoveFirst(LinkedList list) {
        long time = System.currentTimeMillis();
        
        for (int i = 0; i < REMOVE_FIRST_N; i++) {
            list.removeFirst();
        }
        
        long duration = System.currentTimeMillis() - time;
        
        System.out.println(
                "removeFirst on "
                        + list.getClass().getSimpleName()
                        + ": " 
                        + duration 
                        + " ms.");
        
        return duration;
    }
    
    private static long runRemoveLast(LinkedList list) {
        long time = System.currentTimeMillis();
        
        for (int i = 0; i < REMOVE_LAST_N; i++) {
            list.removeLast();
        }
        
        long duration = System.currentTimeMillis() - time;
        
        System.out.println(
                "removeLast on "
                        + list.getClass().getSimpleName()
                        + ": " 
                        + duration
                        + " ms.");
        
        return duration;
    }
}

class Node {
    int data;
    Node prev;
    Node next;
    
    Node(int data) {
        this.data = data;
    }
}

class LinkedList {
    Node head;
    Node tail;
    int size;
    
    void addFirst(int data) {
        Node n = new Node(data);
        
        if (head == null) {
            head = tail = n;
        } else {
            n.next = head;
            head.prev = n;
            head = n;
        }
        
        size++;
    }
    
    void addLast(int data) {
        Node n = new Node(data);
        
        if (tail == null) {
            head = tail = n;
        } else {
            n.prev = tail;
            tail.next = n;
            tail = n;
        }
        
        size++;
    }
    
    int get(int i) {
        Node n = head;
        
        for (; n != null && i > 0; i--, n = n.next) {
            
        }
        
        return n.data;
    }
    
    void removeFirst() {
        if (size == 0) {
            return;
        }
        
        if (size == 1) {
            head = tail = null;
        } else {
            head.next.prev = null;
            head = head.next;
        }
        
        size--;
    }
    
    void removeLast() {
        if (size == 0) {
            return;
        }
        
        if (size == 1) {
            head = tail = null;
        } else {
            tail.prev.next = null;
            tail = tail.prev;
        }
        
        size--;
    }
    
    int size() {
        return size;
    }
}

class CircularList extends LinkedList {
    Node sentinel = new Node(Integer.MIN_VALUE);
    
    CircularList() {
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }
    
    void addFirst(int data) {
        Node n = new Node(data);
        n.prev = sentinel;
        n.next = sentinel.next;
        sentinel.next.prev = n;
        sentinel.next = n;
        size++;
    }
    
    void addLast(int data) {
        Node n = new Node(data);
        n.prev = sentinel.prev;
        n.next = sentinel;
        sentinel.prev.next = n;
        sentinel.prev = n;
        size++;
    }
    
    int get(int i) {
        Node n = sentinel.next;
        
        for (; n != null && i > 0; i--, n = n.next) {
            
        }
        
        return n.data;
    }
    
    void removeFirst() {
        if (size == 0) {
            return;
        }
        
        Node n = sentinel.next;
        n.next.prev = sentinel;
        sentinel.next = n.next;
        n.prev = n.next = null;
        size--;
    }
    
    void removeLast() {
        if (size == 0) {
            return;
        }
        
        Node n = sentinel.prev;
        n.prev.next = sentinel;
        sentinel.prev = n.prev;
        n.prev = n.next = null;
        size--;
    }
}

Unit tests follow:

package com.github.coderodde.sentinellisttexperiment;

import static org.junit.Assert.assertEquals;
import org.junit.Before;
import org.junit.Test;

public abstract class AbstractListTest {

    protected LinkedList ll;
    
    @Before
    public void setUp() {
        while (ll.size() > 0) {
            ll.removeFirst();
        }
    }

    @Test
    public void testAddFirst() {
        for (int i = 1; i <= 5; i++) {
            ll.addFirst(i);
        }
        
        for (int i = 1, j = 4; j >= 0; --j, i++) {
            assertEquals(i, ll.get(j));
        }
    }
    
    @Test
    public void testAddLast() {
        for (int i = 1; i <= 5; i++) {
            ll.addLast(i);
        }
        
        for (int i = 1, j = 0; j < 5; j++, i++) {
            int temp = ll.get(j);
            assertEquals(i, temp);
        }
    }
    
    @Test
    public void testRemoveFirst() {
        ll.removeFirst();
        ll.addFirst(1);
        assertEquals(1, ll.size());
        assertEquals(1, ll.get(0));
        ll.removeFirst();
        assertEquals(0, ll.size());
    }
    
    @Test
    public void testRemoveLast() {
        ll.removeLast();
        ll.addFirst(1);
        assertEquals(1, ll.get(0));
        assertEquals(1, ll.size());
        ll.removeLast();
        assertEquals(0, ll.size());
    }
}

package com.github.coderodde.sentinellisttexperiment;

public class CircularListTest extends AbstractListTest {
    
    public CircularListTest() {
        this.ll = new CircularList();
    }
}

package com.github.coderodde.sentinellisttexperiment;

public class LinkedListTest extends AbstractListTest {
    
    public LinkedListTest() {
        this.ll = new CircularList();
    }
}

Typical output

addFirst on LinkedList: 6802 ms.
addLast on LinkedList: 6837 ms.
removeFirst on LinkedList: 1378 ms.
removeLast on LinkedList: 1184 ms.
LinkedList in total 16201 ms.
----------------
addFirst on CircularList: 7397 ms.
addLast on CircularList: 10960 ms.
removeFirst on CircularList: 2860 ms.
removeLast on CircularList: 2634 ms.
CircularList in total 23851 ms.

Critique request

As always, I would like to hear anything that comes to mind.

Answer 1

• I am surprised that CircularList.addLast is so much slower than CircularList.addFirst, since their implementations are essentially identical. This hints that there is something wrong in benchmarking. I am not a Java expert enough to pinpoint the problem.

• Semantics of CircularList.get is dubious. With the proper i the loop may end up in sentinel (you don't test i against size), and return sentinel's data. I don't think it is intended.

  Also notice that n != null test is redundant. In a circular list it is not possible.

• LinkedList.get throws when i >= size. This shall be annotated.

• DRY. In LinkedList.addFirst, the head becomes n no matter what. Consider

    if (head == null) {
        tail = n;
    } else {
        n.next = head;
        head.prev = n;
    }
    head = n;
  

  Ditto for addLast.

• Tests are incomplete. I'd like to see testing get() with i > size and i < 0.

  Also, prev is never explicitly exercised. A reverse get perhaps?

Answer 2

What can I do with a LinkedList, a CircularList?
I miss a documented interface.
The one thing I can see that I can do given a node in a circular list that is not possible to the same degree in an open one is get the \$k\$-next node.
Symmetrical add&remove procedures are no longer needed without an in-circle sentinel:

    void addLast(int data) {
        addFirst(data);
        tail = tail.next;
    }

    void removeLast() {
        if (size == 0)
            return;
        tail = tail.prev;
        removeFirst();
    }

What difference can using a sentinel make, what difference does having a list member make?
You can search a list without checking end-of-list.
Whether kept all the time or just when needed, it makes searches using it a mutating operation, impeding concurrency.

CircularList inherits an unused head and tail.

FWIW, after adding System.gc(), warm-up and repetitions the benchmark still showed irritating variability (with full usage of both cores and threads/core).

If get() used an accessor head(), CircularList didn't need to re-implement it.

class LinkedList {
    Node head, tail;
    int size;

    /** @return Node at index i */
    Node getNode(int i) {
        if (size <= 1)
            return tail;
        i %= size;
        Node n;
        if (i <= size/2) {
            for (n = head() ; --i >= 0 ; )
                n = n.next;
        } else {
            for (n = tail ; ++i < size ; )
        //    i = size - i;
        //    for (n = tail ; --i > 0 ; )
                n = n.prev;
        }
        return n;
    }

    int get(int i) {
        Node n = getNode(i);
        if (null != n)
            return n.data;
        throw Up;
    }
}

class CircularList {
    Node tail;

    void addFirst(int data) {
        Node n = new Node(data);
        
        if (0 == size) {
            tail = n.next = n;
        } else {
            Node head = tail.next;
            head.prev = tail.next = n;
            n.next = head;
        }
        n.prev = tail;
        
        size++;
    }
}