Is it any way to implement a linked list with indexed access too?

Question

I'm in the need of sort of a linked list structure, but if it had indexed access too it would be great.

Is it any way to accomplish that?

EDIT: I'm writing in C, but it may be for any language.

Answer 1

You can probably use a tree for what you are aiming at. Make a binary tree that maintains the weights of each node of the tree (where the weight is equal to the number of nodes attached to that node, including itself). If you have a balancing scheme available for the tree, then insertions are still O(log n), since you only need to add one to the ancestor nodes' weights. Getting a node by index is O(log n), since you need only look at the indices of the ancestors of your desired node and the two children of each of those ancestors.

Answer 2

For achieving array like indexing in languages like C++, Java, Python, one would have to overload the array indexing operator [] for a class which implements the linked list data structure. The implementation would be O(n). In C since operator overloading is not possible, hence one would have to write a function which takes the linked list data structure and a position and returns the corresponding object.

In case a faster order access is required, one would have to use a different data structure like the BTree suggested by jprete or a dynamic array (which automatically grows as and when new elements are added to it). A quick example would be std::vector in C++ standard library.

Answer 3

SQL server row items in the clustered index are arranged like so:

   .
 /  \   
/\  /\  
*-*-*-*

The linked list is in the leaves (*-*-*). The linked list is ordered allowing fast directional scanning, and the tree serves as a `road-map' into the linked-list. So you would need a key-value pair for your items and then a data structure that encapsulates the tree and linked list.

so your data structure might look something like this:

struct ll_node
{
     kv_pair current;
     ll_node * next;
};

struct tree_node
{
   value_type value;
   short isLeaf;        

   union
   {
      tree_node * left_child;
      kv_pair * left_leaf;
   }
   union
   {
      tree_node * right_child;
      kv_pair * right_leaf
   }
};

struct indexed_ll
{
    tree_node * tree_root;
    ll_node * linked_list_tail;
};

Answer 4

One method of achieving your goal is to implement a random or deterministic skip list. On the bottom level - you have your linked list with your items.

In order to get to elements using indexes, you'll need to add information to the inner nodes - of how many nodes are in the low most level, from this node until the next node on this level. This information can be added and maintained in O(logn).

This solution complexity is: Add, Remove, Go to index, all work in O(logn).

The down side of this solution is that it is much more difficult to implement than the regular linked list. So using a regular linked list, you get Add, Remove in O(1), and Go to index in O(n).