>>55028747
>not just storing a reference to the last element to make appending constant time

>>55029668
this

>>55029668
This but still most of the time might as well use an array

>>55029668
>allocating memory per link is fast as long as you do it at the end

>>55029858
>copying the whole array onto a larger one is faster than allocating a new node

What's the difference between an ArrayList and a LinkedList? Thought they were the same. Or is an ArrayList actually a vector or something?

>>55029668
Array append already is (amortized) constant time because it uses a geometric progression for allocation sizes.

>>55029951
ArrayList is like vector in C++.

>>55030083
Hows about Java?

>>55030113
It works like a linked list but uses a dynamically resizable array to store things. A java LinkedList uses node objects to store things/reference nodes.

>>55029668
As others have mentioned, array lists have amortized constant time append without having to remember the end.

They also have muchmuch better density and memory locality, so many fewer cache misses and page faults when working with them.

Linked lists were ok back in the 80's when PC's didn't have caches or virtual memory, but their main purpose nowadays is as baby's first pointer-based data structure in CPSC 101.

mem

>>55029951
A linked list stores every node in random non-contiguous locations in memory. This makes memory fetches slower because storing nodes in random memory locations isn't cache friendly. Arrays have much faster access times because cpu and ram can fetch local data faster.

My response is really an oversimplification and you should really read a computer architecture book if you want to know more.

can /g/ sort a linked list on this whiteboard
?