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;
}
}