Linked lists in practice

Question

I have some questions about the ideas proposed in this video.

The speaker shows an array that holds values and pointers, and he also shows a separate "free" linked list, that is updated whenever an item is added/removed.

Why are these used? Doesn't using an array / limiting yourself to a set of free nodes defeat the purpose of a linked list?

Isn't one of the perk of using a linked list the ability to traverse fragmented data?

Why use these free nodes, when you can dynamically allocate storage?

The proposed structure, to me, doesn't seem dynamic at all, and is in fact a convoluted and inefficient array.

Answer 1

I have not watched the video, so I'll go by your description. There is an array of items which contain pointers to other items. These pointers form a linked list structure.

This sort of data structure tends to arise when a collection of items needs to be easy to traverse in multiple different orders. For example, a priority queue may need to be traversed both according to the elements' age and according to the elements' priority. This can be implemented with an array of elements, with new elements added at the end so that they're in age order, and a linked list or a search tree for priorities.

One common case for linked lists of array items is in a memory allocator. You ask, “Why use these free nodes, when you can dynamically allocate storage?” Well, what about the cases when you can't dynamically allocate storage, because you're implementing the dynamic storage allocator? The concept of “free list” is common to most memory allocators. A block of memory that isn't in use is an element of the free list. With fixed-size blocks, to free a block, you write a pointer to the current head of the free list at the beginning of the block, and you set the head of the free list to the address of this block. To allocate a block, you take the current head of the free list as the block to use, and set the head of the free list to the block that was second in the list. In pseudocode:

allocate() :=
    block := free_list_head
    if free_list_head is null: raise out_of_memory
    free_list_head := free_list_head.next
    return block
free(block) :=
    block.next := free_list_head
    free_list_head := block

Allocators for variable-sized blocks typically use fancier data structures so as to be able to merge adjacent blocks and find blocks of an appropriate size.

Answer 2

The linked list in the video keeps the data lexicographically sorted, while the table is not. The video is not trying to show the best way to maintain such order, just an example on something you could do with linked lists. It still takes O(N) comparison to find where to place the new item in the list, but it's actually faster than having to move the whole table to make space for the new item.

As Gilles said, it essentialy let's you get two different orderings in linear time just by traversing the list (data lexicographically sorted) or the table (data sorted by insertion time).