4

I have a char array in C#. 

var arr = new char[3] { 'a','b','c' };

How do I add spaces to the end of it without creating a new array?

result: arr = { 'a', 'b', 'c', ' ', ' ', ' ' };

This might sound similar to VB.NET's ReDim. But I'm not sure that is what I want either. I want to preserve the elements inside of it and not instantiate a new array behind the scenes.

Is this only possible with Generic Collections and ArrayList?

Thanks

The Internet
  • 7,959
  • 10
  • 54
  • 89
  • 4
    "I know its possible in Java to do it in place." I'd be really interested in knowing how, I'm fairly sure it's not. – millimoose Aug 15 '12 at 20:39
  • Are the arrays we're talking about large enough or so large in number that ones created in the background really do matter for as long as it'll take gc to grab the old ones? – jwrush Aug 15 '12 at 20:41
  • @millimoose You know what, you're right. It's not possible in Java. +1 – The Internet Aug 15 '12 at 20:42
  • possible duplicate of [Resizing big arrays](http://stackoverflow.com/questions/11842405/resizing-big-arrays) – Martin Liversage Aug 15 '12 at 20:42
  • Yes but as Martin pointed out Lists are just abstractions over arrays. So they create and recreate arrays in the background, so it's no help. – The Internet Aug 15 '12 at 20:49
  • Ack. Well, then I guess you have to use a linked list, and you do end up paying for it slightly in terms of complexity. – jwrush Aug 15 '12 at 20:52
  • Who voted to close this? – The Internet Aug 15 '12 at 20:55
  • @jwrush `List` does not have O(1) addition and removal. It has O(1) addition/removal only at the end. If it's an arbitrary index then it's O(n). Additionally, you don't `have` to use a `LinkedList` to get a dynamically resizable data structure; that is just one data structure (of a number of possibilities) that is dynamically resizable. `LinkedList`, while it's big O is good for adding/removal near the ends, is still almost always slower than array-backed structures in practice. The overhead is constant, yes, but still quite large in comparison. – Servy Aug 15 '12 at 21:02
  • @Servy See MSDN: "This property provides the ability to access a specific element in the collection by using the following syntax: myCollection[index]. Retrieving the value of this property is an O(1) operation; setting the property is also an O(1) operation." (http://msdn.microsoft.com/en-us/library/0ebtbkkc.aspx) – jwrush Aug 15 '12 at 21:04
  • 1
    @jwrush Yes, reading/setting are both O(1). That's not what you said. You said adding/removing, both of which are O(n). – Servy Aug 15 '12 at 21:05

2 Answers2

8

Unfortunately, arrays are pre-fixed by design. This is important because it will reserve the necessary amout of memory at the heap.

So, to answer your requirement about not creating a new one: it won't be possible.

There is, however, a work-around. Look the following method:

Array.Resize(ref myArr, myArr.Length + 5);

It works as described at the source:

This method allocates a new array with the specified size, copies elements from the old array to the new one, and then replaces the old array with the new one.

If array is null, this method creates a new array with the specified size.

If newSize is greater than the Length of the old array, a new array is allocated and all the elements are copied from the old array to the new one. If newSize is less than the Length of the old array, a new array is allocated and elements are copied from the old array to the new one until the new one is filled; the rest of the elements in the old array are ignored. If newSize is equal to the Length of the old array, this method does nothing.

This method is an O(n) operation, where n is newSize.

This means that myArr will be updated to reference the new array. However, if there is another reference to the original array, this won't be updated (it will keep referencing the older version).

Source: MSDN

Andre Calil
  • 7,652
  • 34
  • 41
  • 3
    The original question states "I want to preserve the elements inside of it and not instantiate a new array behind the scenes". If you read the MSDN page, it explicitly says that it creates a new array and copies the elements into it. – Daniel Mann Aug 15 '12 at 20:42
  • @DanielMann I didn't read the question carefuly, will update the answer – Andre Calil Aug 15 '12 at 20:45
8

No, this is not possible using an array, generic or otherwise.. AFAIK, there is no way to dynamically resize an array. Use a List instead.

As Martin pointed out in the comments, even the List class uses an array in its internal implementation. If you want to truly be able to dynamically resize a data structure without reinitializing it, you must implement your own version of a linked list.

System.Collections.Generic contains a class called LinkedList that represents a doubly-linked list (meaning that each node has a reference to both the next and the previous node), but I'm not sure if its internal implementation uses an array..

Daniel
  • 2,944
  • 3
  • 22
  • 40
  • 3
    `List` uses an array as the backing store so that doesn't help. There is no way to dynamically resize a block of memory allocated on the managed heap. – Martin Liversage Aug 15 '12 at 20:47
  • Well, honestly, when I think List I think linked list, which is dynamically resizeable (right?).. If its internal implementation uses an array, however, then you're correct. I'll edit my post to reflect this. – Daniel Aug 15 '12 at 20:49
  • Agreed. When an array is created, the property IsFixedSize (IList) is True. According [http://msdn.microsoft.com/en-us/library/system.array.isfixedsize.aspx](Microsoft) "An array with a fixed size does not allow the addition or removal of elements after the array is created, but it allows the modification of existing elements." So use other Collection. – Jonathan Simon Prates Aug 15 '12 at 20:57
  • @MartinLiversage While `List` technically violates the OPs requirement of resizing an array, it probably is what he actually wants to use in practice, because odds are he doesn't really need to dynamically resize an array. Suggesting it, as done in this answer, is correct. – Servy Aug 15 '12 at 21:04