Linked List: Is this solution good?

Question

I was looking for a way to avoid starting from the head of the list each time I want to find a node, so I thought of assigning indexes to nodes, keeping a pointer to a random (not exactly random; see below) node and then finding the pointer that's closest to the index I want to find. Allow me to explain with code:

// head and last are pointers to the first and last items of a doubly-linked list
// current is a pointer that will change over time. It's used as a temporary pointer
template <class T>a
Node<T>* List<T>::get_closest(Node<T> node, int& difference) {
    int curr_to_i = current->index - node->index;
    int last_to_i = last->index - node->index;
    Node* closest = node->index < abs(curr_to_i) ? head : current;
    closest = closest->index < abs(last_to_i) ? closest : last;
    difference = closest->index - node->index;
    return closest;
}

/*
 * This functions adds a node with the given value to the given index. The node at that
 * index and all the following are moved, and the new node is inserted before them.
 */ 
template <class T>
bool List<T>::add(T value, int index) {
    if (index < 0) { //Invalid index
        return false;
    } else if (index == last->index +1) {
        push(value);
        return true;
    } else if (index > 0) {
        Node* new_n = new Node;
        new_n->value = value;
        new_n->index = index;
        int difference;
        Node* closest = get_closest(new_n, difference);
        if (difference < 0) {
            for (int i = 0; i < abs(difference); i++) {
                current = current->previous;
            }
        } else if (difference > 0) {
                for (int i = 0; i < abs(difference); i++) {
                current = current->next;
            }
        } /* current now points to the node we want to move */
        new_n->previous = current->previous;
        new_n->next = current;
        current->previous->next = new_n;
        current->previous = new_n;
        if (index == 0) {
            root = new_n;
        }
        new_n = new_n->next;
        while (new_n != null) {
            new_n->index++;
            new_n = new_n->next;
        }
        return true;        
    }
}

Is this more efficient than starting from the head and advancing forward a number of times?

Answer 1

It looks like insertion would become a lot more expensive. Why not write a test program and time the difference?

Answer 2

If you need to access elements in the middle of the list, then you're better off using an array. A list is an abstract data structure (ADT) that can be implemented various ways. What you've essentially done is create a redundant representation that has the overhead of both methods.

The advantage of a linked list is that inserts can be very fast at the head of the list - O(1) vs. O(n) for an array. However, since you have to maintain your index, you have O(N) overhead anyways for inserts.

If you need indexing, just use an array. Simpler and faster.

Answer 3

Your pseudo-random index can potentially be close to the beginning of the list (just to illustrate), causing shifts of every element in the list thereafter. This makes the insertion into a linked list very expensive, so much so that it becomes pointless to have a linked list, you can just use an array.

Answer 4

It sounds to me like you're trying to invent Skip Lists, which is a sort of balanced, sorted tree.

Probably what you really want is to use something like boost::multi_index, which will allow you to use a combination of indices to get good performance on a range of operations. One of the examples has a very similar feel to what you're trying to do.

Before attempting to use something like this, you should profile your actual uses to determine if there is any real benefit of optimizing that part of your code, and then if it turns out to be a bottleneck, try many different combinations of structures to see which one actually performs the best on your specific use. Unless your data set is quite large, a std::vector will almost always be the fastest, because of locality.