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?
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)




Community Treasure Hunt

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

Start Hunting!