Which data structure is like a combination of a doubly-linked list and an array?

Question

Is there any already created structure which would be simply basic array of doubly linked list nodes?

I mean then you use get(int index) it would return element directly from array (array[i].element). With this structure I could easily do foreach too because every element would be linked to each other, so I would not need to think about blank array places.

Q: Why I need this ? A: I have unlimited memory, I know how big array I need and I want that structure would be fastest.

• NathanOliver: Are you looking for a std::array<std::list, some_size>?
• erip: Maybe std::deque?
• erip: @NathanOliver It seems OP wants an array of nodes, not an array of lists.
• Vaidotas Beržinskas: Yes I want array of nodes. Node contains left node, right node and element.
• David Haim: it's either a linked list, or an array, there is no hybrid. the best I can think of is an array of pointers to nodes.

Answer 1

Here is a small C++11 container guide, just set your constraints and follow the arrows:

enter image description here

IMO std::deque is the most probable candidate.

In case you want to create something yourself, here is an example of how could it look like:

struct Node{
 // constructor
 Node (int v, Node* n = 0, Node* p = 0) 
 : value(v), next(n), prev(p) { }
 // data member
 int value;
 // pointer to next node
 Node* next;
 // pointer to previous node
 Node* prev;
};
size_t number_of_nodes = 10;
Node* ptr = new Node[number_of_nodes];

• Vaidotas Beržinskas: Now I'm thinking that adding new element in "my structure" would be like doubly linked list which means that complexity would be about O(n). Other functions complexity would be like std::deque. So I think your answer is closest to answer.
• erip: So you were just looking for a vanilla node?
• Vaidotas Beržinskas: I was looking for structures which would be as fast in adding, removing and getting elements as array. Also I needed foreach loop. In basic array if I do foreach loop then I need to deal with empty array places, so I thinked about continuosly linking elements to neighour in array and then I could just skip this empty array places.
• erip: @Vinigas All standard containers support for each loop. Even normal arrays do: ideone.com/Q2212M
• Vaidotas Beržinskas: You used integer array, but if I use the pointer array then I don't want to throgh array elements which countains NULL. for_each goes through every single array element. E.g. I have array which size is 100. Whole array is filled with NULLs. Then I add two element's in array with random index. And then I do for_each I actually want to do loop only 2 times, not 100.

Answer 2

Based on your description, I think the most fitting data structure would be a double-ended queue; or, in C++, a std::deque.

How it's like a doubly-linked list:

• Stores back and front pointers
  • {push,pop}_{front,back} are O(1)
• Doesn't need reallocs when expansion is necessary

How it's like an array:

• Allows subscript indexing
  • O(1) random access

The get operation you're looking for is operator[] or std::deque::at.

Some considerations are that insertion/removal of elements not on polar ends of the structure (i.e., somewhere in the middle) are average case O(n) on the number of elements for the same reason it's O(n) to remove an element from a basic array.

Obligatory basic-use-case

• Ziezi: by "bracket indexing" do you mean subscript operator[ ]? :)
• erip: @simplicisveritatis Edited. ;)

Answer 3

I think what you are looking for is the container deque already present in the STL. See -> http://en.cppreference.com/w/cpp/container/deque If it is not the one you are looking for, you probably find the container you need here --> http://www.cplusplus.com/reference/stl/

Hope this help