0

Let's say I need a queue for my project and the language I use does not have a built-in queue structure. So I decided to implement one myself. So I create an object with elements positions as the object's keys. I also keep track of where the head and the tail of my queue are. I increment and decriment those values when I enqueue and dequeue. Also when I dequeue I need to make sure the tail won't be before the head. And all that.

So will it be more efficient than using built-in arrays? Yeah, I know deleting athe first element of an array is pretty expensive in terms of efficiency. But usually languages provide a pretty good optimization for built-in structures.

And same question for the linked lists. Let's say I need to delete and insert elements in the middle of an array pretty often. Would creating a custom linked list, storing every element as an object with pointers, redirecting those pointers, keeping track of the head and the tail and all that... is it still better than using built-in and optimized arrays?

With that being said, which is a better solution? And how do I know when I need to choose the other option (like switching from built-in array to custom queue)? Maybe after certain amount of elements?

Improve this question
2
  • 5
    Which language are you using? Almost any language that anyone has ever heard of almost certainly either has a standard library implementation or a popular, supported, tested, robust, reliable, optimised 3rd-party library freely available which will provide you with a reliable implementation that you would not need to reinvent the wheel for yourself. There are plenty of use-cases where a linked list is more suitable than an array, but there's almost zero likelihood of anybody ever meeting a situation where the best solution is to write their own linked list.
    – Ben Cottrell
    Jan 8 at 11:45
  • 1
    Building correct data structures can be difficult, and building fast data structures is quite challenging as well. Intuitions about performance are often wrong, and linked lists in particular are really inefficient on modern hardware unless you're trying to build a lock-free LIFO queue (you probably want a b-tree/tree-of-arrays instead). However, standard library containers are often very general, and fail to optimize for your specific case. E.g. in one project I was able to significantly outperform C++'s std::unordered_map with a custom hashmap by exploiting relevant properties of my data.
    – amon
    Jan 9 at 10:12

1 Answer 1

Reset to default
4

Will a proper dynamic data structure be more efficient than simulating it with fixed-size arrays? Almost certainly yes. But is it a good idea to build one for your project? This depends on many other situational factors.

  • How much of a bottle-neck is deque access for the overall performance of your code base? It is entirely possible that using one data structure is twice as fast as another, but has negligible effect on the end-to-end performance.

  • How expensive is the time you spend on creating the new data structure, and over how much use can you amortize it? Depending on that ratio, the answer can be completely different.

A proper decision usually requires building an end-to-end MVP of your project and measuring whether the performance is acceptable, and if not, whether data structure access is the bottleneck. Then you can try the same measurement with your own deque and compare.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.