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:

1
2
3
4
5
6
7
8
9
10
11
12
13

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

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