Efficiently inserting an element into an array

37 views (last 30 days)
I have a 1xn array A and need to insert a number x between the mth and (m+1)th element.
I know this can be done by
A = [A(1:m),x,A(m+1:end)]
but I am not sure how MATLAB processes this - it could possibly involve re-assigning the entire latter section of the array, taking O(n) time. I suspect this is the case as a program that applies this many times is running quite slowly.
Is there a more efficient way to do this?
  13 Comments
Dave B
Dave B on 17 Aug 2021
"Are there other data structures, in MATLAB or not, that can insert in sublinear time?"
I'd think the standard datatype for fast insertion is a linked list, there isn't a built-in linked list in MATLAB (to my knowledge), but you can implement your own. https://www.mathworks.com/help/matlab/matlab_oop/example-implementing-linked-lists.html The example is for doubly linked and you could probably simplify by making a singly linked.

Sign in to comment.

Accepted Answer

Walter Roberson
Walter Roberson on 17 Aug 2021
Edited: Walter Roberson on 17 Aug 2021
Create a binary tree from cell arrays. Nodes are cell if they are branches, non-cell if they are terminal.
It is common to use an implementation where each node has a slot for a value plus a left and right slot (possibly empty); this avoids reallocation of nodes, and can avoid having to chase down to the leaves every time.
... Would it be acceptable to use Containers.map ? https://www.mathworks.com/help/matlab/map-containers.html Those are, if I recall correctly, implemented as hash tables.

More Answers (0)

Products


Release

R2019b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!