Linked list without objects

Here’s a linked list object pool for storing int values. It avoids using objects to represent linked list nodes, so it keeps memory use to a minimum. It’s singly-linked, and the arrays for next node and stored values are interleaved for cache friendliness.

I’ve been using it to splat render 1 million particles and it’s worked nicely for me. On the off chance that someone else might find it useful I thought I’d post it here.

Using it looks like:


LinkedListPool listPool = new LinkedListPool(1000000);
int list = listPool.getNewList(1); //gets a list with a single node storing the value 1
int last = list; //last will point to the end of the list
for(int i = 2; i < 10; i++)
	last = listPool.insertAfter(last,i); //adds a new node to the end of the list

while(list > 0){ //nodes that are 0 or less are empty
	int value = listPool.getValue(list);
	System.out.print(value+",");
	list = listPool.nextNode(list);
}
System.out.println();
//prints "1,2,3,4,5,6,7,8,9,"

The class LinkedListPool:

public class LinkedListPool {

	private int[] nextValues; //next nodes and values, interleaved
	
	private int[] availableStack;
	private int stackSize;
	private int stackOrderedTo;
	
	public LinkedListPool(int capacity) {
		nextValues = new int[capacity*2];
		availableStack = new int[capacity];
		stackOrderedTo = 0;
		clear();
	}
	
	/**
	 * Gets a new single node list.
	 * O(1)
	 * @param value The value for the first list item
	 * @return The node in the new list
	 */
	public int getNewList(int value) {
		stackSize--;
		int newNode = availableStack[stackSize];
		nextValues[newNode] = -1;
		nextValues[newNode+1] = value;
		return newNode;
	}
	
	/**
	 * Clears all lists. 
	 * Number of operations = lowest ID of all nodes deleted since last clear.
	 */
	public void clear() {
		for(int i = stackOrderedTo; i < availableStack.length; i++) 
			availableStack[i] = i*2;
		
		stackSize = availableStack.length;
		stackOrderedTo = availableStack.length;
	}
	
	/**
	 * Whether the pool has run out of nodes or not.
	 * O(1)
	 * @return
	 */
	public boolean isEmpty() {
		return stackSize < 1; //don't use 0th entry
	}
	
	/**
	 * Starts a new list by attaching to the front of node.
	 * Take care. Node ought not be in the middle of an existing list.
	 * O(1)
	 * @param node The first node in a list.
	 * @param insertValue The value to insert
	 * @return The new first node in the list.
	 */
	public int insertAtFront(int node, int insertValue) {
		int newNode = availableStack[stackSize-1];
		stackSize--;
		nextValues[newNode] = node;
		nextValues[newNode+1] = insertValue;
		return newNode;
	}
	
	/**
	 * Inserts an item into a list after the given node.
	 * O(1)
	 * @param node The node to add an item after
	 * @param insertValue The value to insert
	 * @return The new node.
	 */
	public int insertAfter(int node, int insertValue) {
		int newNode = availableStack[stackSize-1];
		stackSize--;
		nextValues[newNode] = nextValues[node];
		nextValues[node] = newNode;
		nextValues[newNode+1] = insertValue;
		return newNode;
	}
	
	/**
	 * Appends to the end of the list that this node belongs to.
	 * O(listLength)
	 * @param node Any node in the list.
	 * @param appendValue The value to append
	 * @return The new node.
	 */
	public int append(int node, int appendValue) {
		while(nextValues[node] > 0) node = nextValues[node];
		int newNode = availableStack[stackSize-1];
		stackSize--;
		nextValues[newNode] = -1;
		nextValues[node] = newNode;
		nextValues[newNode+1] = appendValue;
		return newNode;
	}
	
	/**
	 * Deletes a node, given its predecessor
	 * O(1)
	 * @param prevNode The node before the node to delete
	 * @param node The node to delete
	 */
	public void delete(int prevNode, int node) {
		nextValues[prevNode] = nextValues[node];
		availableStack[stackSize] = node;
		stackOrderedTo = Math.min(stackOrderedTo,stackSize);
		stackSize++;
	}
	
	/**
	 * Deletes a node, and any nodes after this in the list.
	 * O(listLength)
	 * @param prevNode
	 * @param node
	 */
	public void cropList(int prevNode, int node) {
		nextValues[prevNode] = -1;
		stackOrderedTo = Math.min(stackOrderedTo,stackSize);
		while(node > 0) {
			availableStack[stackSize] = node;
			stackSize++;
			node = nextValues[node];
		}
	}
	
	/**
	 * Gets the next node. 
	 * O(1)
	 * @param node The node who's successor is wanted
	 * @return The next node in the list, -1 or 0 indicate no next node.
	 */
	public int nextNode(int node) {
		return nextValues[node];
	}
	
	/**
	 * Gets the int value associated with a node
	 * O(1)
	 * @param node The node to get a value for
	 * @return The value
	 */
	public int getValue(int node) {
		return nextValues[node+1];
	}
	
	/**
	 * Sets the value for a node
	 * O(1)
	 * @param node
	 * @param value
	 */
	public void setValue(int node, int value) {
		nextValues[node+1] = value;
	}
	
	/**
	 * Increases size to 1.5x current capacity.
	 * O(poolSize)
	 * If the pool is not empty this does nothing.
	 */
	public void resize() {
		if(!isEmpty()) return;
		int newSize = (availableStack.length*3)/2;

		int[] newNextValues = new int[newSize*2];

		System.arraycopy(nextValues,0,newNextValues,0,nextValues.length);
		
		int[] newAvailable = new int[newSize];
		System.arraycopy(availableStack,0,newAvailable,newAvailable.length-availableStack.length,availableStack.length);
		for(int i = 0; i < newSize-availableStack.length; i++)
			newAvailable[i] = (availableStack.length+i)*2;

		stackSize = newSize-availableStack.length;
		stackOrderedTo += stackSize;
		nextValues = newNextValues;
		availableStack = newAvailable;
	}
}