What is the type of linked list where order doesn't matter

Question

I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about linked listed implementation:

Insertion into a singly-linked list is a nice exercise in pointer manipulation, as shown below. Since we have no need to maintain the list in any particular order, we might as well insert each new item in the simplest place. Insertion at the beginning of the list avoids any need to traverse the list, but does require us to update the pointer (denoted l) to the head of the data structure.

I'm wondering what kind of list is that because I can't use it for index based access. All other basic implementations I've seen provide index based access.

When searching for an item, their implementation shows direct object comparison:

list *search_list(list *l, item_type x)
{
    if (l == NULL) return(NULL);
    if (l->item == x)
        return(l);
    else
        return( search_list(l->next, x) );
}

So I'm thinking maybe they didn't account for index based access.

This book also distinguishes Container and Dictionary categories of DS:

We use the term container to denote a data structure that permits storage and retrieval of data items independent of content. They are distinguished by the particular retrieval order they support (LIFO, FIFO). By contrast, dictionaries are abstract data types that retrieve based on key values or content.

It seems that the linked listed implementation at hand falls into a container category with the object reference as the key, something alike a map DS.

Is this assumption valid?

Answer 1

I took a look at the book you are referencing, and it does appear that Steven Skiena made an unordered Dictionary implemented as a linked list. It's not a terribly efficient data structure, but he was only using it to illustrate basic linked list coding techniques, so I expect he just wanted to keep things as simple as possible.

For what it's worth, a stack is a container that only allows you to add to or access from the very top item, which isn't really index based in the way we'd usually use that term. I mention this only to highlight that Containers do not need to have index-based retrieval.