English is currently available.
Java DISCUSSION
My data structures course says a linked list has O(1) insertion and removal while an array list is O(n), so I used LinkedList for a buffer of about 100,000 measurement objects where I insert and remove in the middle. A quick benchmark shows ArrayList is faster for almost every operation I try, including the middle inserts.
Is the textbook complexity wrong, or is my benchmark? When is LinkedList actually the right choice, and what should I use for a FIFO queue of samples?
The complexity is right but incomplete: insertion into a linked list is O(1) only once you are standing at the node. list.add(index, x) and list.remove(index) on a LinkedList must first walk to the position, which is O(n) pointer chasing. It starts from whichever end is nearer, so up to n/2 steps.
ArrayList.add(index, x) finds the slot immediately and shifts the tail with System.arraycopy. For 100,000 elements a middle insert moves 50,000 references, about 200 KB at 4 bytes each, as one fast block copy of contiguous memory. Walking 50,000 nodes scattered across the heap means up to 50,000 potential cache misses, which is far slower.
Memory layout is the deciding constant factor. ArrayList stores its references in one contiguous array: 4 bytes per element with compressed references, 8 without, plus some spare capacity. It grows by about 50 percent when full, so appends are amortised O(1). LinkedList allocates a node object per element holding the item and the next and previous references plus an object header, around 24 bytes per node on a typical 64-bit JVM, and gives the garbage collector more to do.
get(i) is O(1) on ArrayList and O(n) on LinkedList, so an indexed for loop over a linked list is O(n²). With 100,000 elements and an average walk of n/4, that is about 2.5 billion node steps. Always traverse a LinkedList with for-each or an iterator.
Where LinkedList wins in principle is insertion and removal through an iterator during a traversal: ListIterator.add() and remove() are O(1) at the cursor, whereas each removal through an ArrayList iterator shifts the tail. Even so, for bulk removal ArrayList.removeIf(predicate) compacts the array in one pass, O(n) in total.
Insertion at the front is the other textbook case: LinkedList.addFirst is O(1) and ArrayList.add(0, x) is O(n). But ArrayDeque also does that in O(1), without allocating a node per element. In practice the situations in which LinkedList is the best choice are rare, so default to ArrayList and measure before switching.
For a FIFO of samples use ArrayDeque: queue.addLast(sample) and queue.pollFirst(). It is a circular buffer over an array, amortised O(1) at both ends, with no node objects; it does not accept null elements. Between a producer thread such as a serial reader and a consumer thread, use an ArrayBlockingQueue with a fixed capacity: put blocks when it is full and take blocks when it is empty, and offer returns false instead of blocking if you would rather drop samples.
On the benchmark itself: hand-written timing loops mislead on the JVM because of JIT warm-up and dead-code elimination, so use JMH for anything that will drive a decision. When the element count is known, new ArrayList<>(100_000) avoids the repeated growth copies.
