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.
l
insentinellisttexperiment
comes from. Whence the doublet
?) \$\endgroup\$CircularList
isn't what I expected at all: Singly linked, justList.tail
.) (What did you expect? Try adding searches, successful and not.) \$\endgroup\$LinkedList
that is a wrapper around JRELinkedList
and compare results too :-) \$\endgroup\$