At any point in time I have a list of N points, points will be added and removed making the number of total points change over time. If I just use an array to store this information, I'm concerned that it will slow things down a lot because the computer will have to move things around in memory as the number of elements change.

What is a way to store this information where it is efficient to add and remove elements but still easy to access the information stored in the array for simple functions/plotting? I'm using matlab, which hopefully doesn't constrain me too much.

  • $\begingroup$ Linked list may be the solution, check out mathworks.com/help/matlab/matlab_oop/… $\endgroup$ May 11 '20 at 1:40
  • $\begingroup$ Last time I benchmarked it (which, admittedly, was various versions ago), Matlab's OOP was painfully slow. I'd be surprised if a linked list implemented in pure Matlab were any good for computationally intensive work. $\endgroup$ May 11 '20 at 20:21
  • $\begingroup$ @ Federico Poloni Why are we talking about OOP here? Linked lists (and similar dynamic memory structures) is all about pointer manipulation, nothing to do with OOP, right? $\endgroup$ May 14 '20 at 4:46

Let me start with the following: Even very good and experienced programmers have a very hard time estimating whether a particular piece of code is performance critical or not. This has given rise to the adage "Premature optimization is the root of all evil", which can be translated as "Unnecessarily optimizing code leads to obscure code that will be difficult to maintain, debug, and will contain lots of bugs". The upshot is this: Unless you have concrete evidence that whatever algorithm you choose is in fact slow, choose the simplest data structure and algorithm you can think of!

Now to the question at hand: There are a number of data structures that are typically used for your case and that are optimized for specific cases.

  • If you know that you will only add or remove elements of your set at the end of the set, then you would typically use a "stack". This happens if new elements come in at random times and when it doesn't matter which elements are worked on -- just take the topmost one on the stack.

  • If you only want to add elements to the end of the set, and want to work on (and remove) the element that has been in the set the longest, then you will want to use a "double-ended queue" ("deque"). This models a stack where you only ever remove the bottom-most element.

  • If removal can happen to any element in the set, then you can use a "linked list" where insertion and removal is cheap, but finding an element might be expensive (because you might have to search through all elements to find it).

  • If removal can happen to any element in the set, and you need an efficient way of finding a particular element, then you want to use a "set".

I'm not a matlab guy, so don't know under what name these data structures are available there. But they're widely used in all programming languages and I would be very surprised if they are not available in matlab in some form or other.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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