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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top