Also another way to implement "linked lists" is to create two arrays:
values = [5,6,2,4,8]
next = [1,2,3,4, null]
Here the next array basically stores the pointers to the next "node".
My parallel processing professor says this is the "correct way" to do linked lists because it allows much greater levels of concurrency. But really its kind of a hybrid between the array list / dynamic array and the classical disjoint linked list approach. One big advantage is its MUCH better cache behavior and its ability to store the data in a compact form that is better with the cache.
Finally, this approach allows you to have several "next" arrays holding links in different order (which is useful for atomic behavior during parallel or concurrent processing).
Also another way to implement "linked lists" is to create two arrays:
values = [5,6,2,4,8]
next = [1,2,3,4, null]
Here the next array basically stores the pointers to the next "node".
My parallel processing professor says this is the "correct way" to do linked lists because it allows much greater levels of concurrency. But really its kind of a hybrid between the array list / dynamic array and the classical disjoint linked list approach. One big advantage is its MUCH better cache behavior and its ability to store the data in a compact form that is better with the cache.
Finally, this approach allows you to have several "next" arrays holding links in different order (which is useful for atomic behavior during parallel or concurrent processing).
This is really cool! Thank you for sharing!