CODEWITHSUNDEEP
cdata-structures
byrondrossos
byrondrossos

Reputation: 2117

What data structure to use to emulate an array in which one can add data in any position?

I want to store a small amount of items( less than 255) which have constant size (a c char )and be able to do the following operations:

I have tried using an array and making a function to add a value by moving all items after it a place forward.Same thing can happen with deleting, but it is too inefficient.Of course, I do not mind having to use a library, long as it is readily available and free.

Upvotes: 1

Views: 100

Answers (2)

Karoly Horvath
Karoly Horvath

Reputation: 96258

  • Array - access: O(1), insert: O(n)
  • Double-linked list - access O(n), previous/next: O(1), insert(*): O(1)
  • RB tree with number of childs stored: O(log n) for all operations.

(*): You need the traverse the list first to get to the position (O(n)).

Note: no, the array is not messy, it's really simple to implement. Also as you can see, depending on the usage, it can be quite efficient.

Based on the number of elements, and your remark to array implementation you should stick to arrays.

Upvotes: 5

ThiefMaster
ThiefMaster

Reputation: 318508

You could use a double-linked list for it. However, this won't work if you want to keep the array behaviour (e.g. accessing elements quickly (O(1), for a LL it's O(n)) by their index)

Upvotes: 0

Related Questions