Array of pointers to elements in a linked list

[Una]

Hello all,

I'm trying to implement a data structure consisting of an array of link lists, where each element (value from a given range [1..N]) can appear only once in this array of link-lists structure.

In order to reduce the complexity of delete operation to O(1), I want to include an array of size N, one for each possible value, where each element of this array points to the corresponding element in the array of linked-lists.

I implemented the array of linked-list part. However, this additional array of pointers is causing me trouble.

I would be grateful for any suggestions.

Una

[Gaminic]

I don't really get the problem. Why not simply keep an unorganized array of items and keep the linking internal?

cstruct LItem {
    int myInt;
    char myChar;
    Litem *next, *prev;
};
int main() {
    LItem[50] myList;
    // fill in data
    LItem[3].next = &LItem[9];
    return 0;
}

The handy thing is that you can refer directly using array indeces ("I need the 5th item"), which reduces complexity to O(1) for delete ("Delete the 5th item" -> access myList[4], adjust prev/next of neighbors). If you need reverse access as well, you can add an int "index" to LItem. That way, you can fetch its array position while browsing through the LL via pointers.

The second handy thing is that you can use dynamic allocation and delete every element simultaneously rather than implementing some odd recursive delete call in the destructor.

[Una]

Thanx for your reply. I found the mistake in my code.

I did not use an array of items since in my case it would be too space consuming. I need a large number of arrays, many of them which are often empty.