Efficient way to insert a value into an array?

Question

I need to insert a value into an array... ideally I could just start with List<myObj>, but the methods I need to use return myObj[] instead.

I always need to insert a value into the first position, and rather than worm the values already in the array... I came up with the following scheme..

    List<myObj> list = array.ToList<myObj>();
        if (list.Count > 0 && list != null)
        {
            list.Insert(0, InsertRecord(myParam)); // InsertRecord() is one of my methods...
        }
        return list.ToArray();

My question is... is this even remotely efficient? Is there a better way to go about doing what I need to accomplish?

What are you really trying to do here? How do you read from the List? Randomly? First item? Last item? Enumerate the whole list? — Andrew Barber
– Andrew Barber, Commented Dec 12, 2011 at 23:18
@AndrewBarber: ToList does not in fact create a copy of the array, it uses the List<T> constructor that takes an IEnumerable<T> and wraps it. — Ed Swangren
– Ed Swangren, Commented Dec 12, 2011 at 23:19
@EdS. I actually meant his ToArray() call at the end... oops. But, am I right there, anyway? — Andrew Barber
– Andrew Barber, Commented Dec 12, 2011 at 23:20
@AndrewBarber: Yes, that one does. It uses a Buffer<T> and the Buffer constructor performs a copy. — Ed Swangren
– Ed Swangren, Commented Dec 12, 2011 at 23:23
Do you need to return an array or consume an array (or both)? — user166390
– user166390, Commented Dec 12, 2011 at 23:27

Jorgesys · Accepted Answer · 2017-09-19 19:57:52Z

7

I think you can save some time with

var newArray = new myObj[oldArray.Length  + 1];    
oldArray.CopyTo(newArray, 1);
newArray[0] = InsertRecord(myParam);

edited Sep 19, 2017 at 19:57

Jorgesys

127k26 gold badges347 silver badges276 bronze badges

answered Dec 12, 2011 at 23:17

Henk Holterman

276k33 gold badges353 silver badges540 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Magnus Over a year ago

Isn't better to work with a list until you need to return an array and than just call ToArray as he is doing. As List Add is o(n) only when capacity is reached.

user166390 Over a year ago

I think it still has the same bounds, though, even if a potentially better wall-clock. (Assuming Insert is O(1) amortized and the copy is O(n) and that only one item is added between needing it as an array.)

Henk Holterman Over a year ago

There is no way to avoid the O(n) copying here. This answer is just aiming at the lowest overhead. Going through List<> just adds a lot of steps.

Jon Hanna Over a year ago

@Magnus it depends, it looks like the OP is adding sporadically, so Henk's is better, but you'd be more efficient if there were several inserts in a row.

Borophyll Over a year ago

@firthh It seems trivial but I only need to insert into the first position of the array and I only need to do it once. Since that is the case, increasing the size of the array by 1 does actually make sense

|

Adam Mihalcin · Accepted Answer · 2011-12-12 23:22:05Z

The List<T> class is backed by an array, so there is no difference in performance between using a List to insert at index 0 and using an array to insert at index 0, except that the BCL developers have tested far more extensively for performance. Don't take the performance hit of the ToList method and List<T> constructor, since a new array allocation is happening behind the scenes anyway.

Worse, you might need two array allocations with your posted code, since the List<T> constructor (called by ToList) may allocate an array of exactly the size of array, and then the Add method has to allocate a new array just to perform the insertion. Unlikely, but possible.

In short, allocate the new array yourself.

EDIT:

Given that your method needs to return an array, it doesn't make any sense at all to go through a list. With a list, you are going to copy the original array into the array backing the List<T>, then insert, then copy that backing array into another array to be returned from your method. That makes two array allocations minimum, plus the possible third that I mentioned above. Using raw arrays guarantees exactly one array allocation.

Collectives™ on Stack Overflow

Efficient way to insert a value into an array?

2 Answers 2

9 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related