The difference between array and arraylist

From Array To Arraylist

Written by: maffelu , 2009-09-08 18:06:09

The basic collections in C# are arrays, single dimensioned, multi-dimensioned or jagged. They are fast and easy to use in a very basic way. Arrays are, however, immutable and thus cannot be altered after having been created.
Example:

            Item[] items = new Item[3];

            items[0] = new Item(1);

            items[1] = new Item(2);

            items[2] = new Item(3);

            items[3] = new Item(4); //ERROR: No room for this one

The problem we see above is that we have created an array that can hold up to three elements. When we try to insert another, we get an IndexOutOfBounds exception thrown because the array can’t fit it.

One solution is of course to create an array with room for a thousand elements, but that would be a terrible waste of memory.

This can only be solved by creating a bigger array with more room and transfer the whole array over to the new array and continue from there. This has to be done every time the elements exceeds the array bounds:

            Item[] items = new Item[3];

            items[0] = new Item(1);

            items[1] = new Item(2);

            items[2] = new Item(3);



            //Create a temporary array with the new size


            Item[] temp = new Item[items.Length + 1];



            for (int i = 0; i < items.Length; i++) {

                //Copy the old array to the temporary one


                temp[ i] = items[ i];

            }

            //Copy over the temporary array with a new size


            //to the old array again.


            items = temp;



            //Add item


            items[3] = new Item(4);

Problem solved! Well, sort of. This is totally useless unless you know exactly how many elements to throw into the array from the start. If you do know, then you will probably set the right size straight off.
One way would be to actually create a class to handle this. We’ll create a class called ItemList which will have an Add method that takes care of all of this.

    public class ItemList{

        private Item[] _items;

        public void Add(Item item) {}

    }

This method will hold the array and come up with a clever way to check the array every time you want to add an element to see if it has to be resized. Excelent. Sadly, a normal array doesn’t have a method to check how many elements are in an array, only the size of the array, so we will have to start with a method to count all the elements in the list. We will also add a Size property to get the size of the array.

    public class ItemList{

        private Item[] _items;

        public int Size {

            get { return this._items.Length; }

        }

        public void Add(Item item) {}

        public int Count() {

            int elements = 0;

            for (int i = 0; i < this.Size; i++) {

                if (this._items[ i] != null) {

                    elements++;

                }

            }

            return elements;

        }

    }

Right. The Count() method will loop through each element in the array, and add it to the count if it’s not null. Great, the class is already useful, you can now use it to see how many elements are in the array.
Above code, however, will fail since the array is never initiated. But how will it be initiated, what size should we use? Well, I guess it depends on what we’re gonna use it for. In this case, we will usually just deal with 3-5 items, so a size of 5 seems reasonable. We’ll add a constant to represent the size of the array and a constructor to initiate it.

    public class ItemList{

        private const int _defaultSize = 5;

        private Item[] _items;

        public int Size {

            get { return this._items.Length; }

        }

        public ItemList(){

            //Initate and set a default size for the array


            this._items = new Item[_defaultSize];

        }

        public void Add(Item item) {}

        public int Count() {

            int elements = 0;

            for (int i = 0; i < this.Size; i++) {

                if (this._items[ i] != null) {

                    elements++;

                }

            }

            return elements;

        }

    }

Now we can actually use this class, like this:

    class Program{

        static void Main(string[] args){



            ItemList items = new ItemList();

            Console.WriteLine("ItemList count: {0}", items.Count());            

            Console.Read();

        }

    }

This will however output ’0’ since we haven´t added any elements yet. Back to the Add() method!
We will use pretty much the same method that we used in the beginning. The only difference is that every time we are forced to resize the array, we will double its capacity. That is a logical move and will prevent the array from being resized every time someone adds something.

    public class ItemList{

        private const int _defaultSize = 5;

        private Item[] _items;

        public int Size {

            get { return this._items.Length; }

        }

        public ItemList(){

            //Initate and set a default size for the array


            this._items = new Item[_defaultSize];

        }



        public int Count() {

            int elements = 0;

            for (int i = 0; i < this.Size; i++) {

                if (this._items[ i] != null) {

                    elements++;

                }

            }

            return elements;

        }

        public void Add(Item item) {



            if (Count() == this.Size) {



                //Create a new, temporary, array to hold the old values


                Item[] tempArray = new Item[this.Size];



                //Copy the old values to the temporary array


                for (int i = 0; i < this.Size; i++) {

                    tempArray[ i] = this._items[ i];

                }



                //Create a new size by doubling the old size


                int newSize = this.Size + this.Size;



                //Create a new array with the new and improved size


                this._items = new Item[newSize];



                //Copy back the old items to the new and improved array


                for (int i = 0; i < tempArray.Length; i++) {

                    this._items[ i] = tempArray[ i];

                }

            }



            //Add the new item


            int numberOfElements = Count();

            this._items[numberOfElements] = item;

        }

    }

The Add() method will now start by checking if the array is full. If the array is full it will create a temporary array with the same size as the old one and then the old values will be copied over to the temporary array.
We then create a new size by doubling the current size and reinstantiate the _items array with the new size. After that we copy back the old values since they were lost in the reinstantiation.
After all this, it’s just a matter of inserting the element after the last element currently in the array. We do this simply by counting the current elements and adding using the answer as index (since we start counting at 1 and not 0 we get the correct index as well).

Using this class is now quite easy:

    class Program{

        static void Main(string[] args){



            ItemList items = new ItemList();

            items.Add(new Item(1));

            items.Add(new Item(2));

            items.Add(new Item(3));

            items.Add(new Item(4));

            Console.WriteLine("ItemList count: {0}", items.Count());

            //ItemList count: 4


            Console.Read();

        }

    }

We now, however, come up with two problem.

We cannot select individual elements
We cannot remove individual elements

Right. This has to be fixed of course. We’ll start with the first problem since this is easily fixed. We will have to add an indexer to our class:

        public Item this[int index] {

            get {

                if ((index < 0) || index >= this.Size) {

                    throw new ArgumentOutOfRangeException();

                }

                return this._items[index];

            }

        }

What this means is that if someone uses our class with an indexer (like object[ i]) that indexer will be handled like a property. We make it readonly since it would be counter-effective to allow insertion by index when we have an Add method (we could however, later on, add an InsertAt() method if we’d want).
The second problem is a bit more delicate and requires its own method. We’ll call it RemoveAt() and it will allow the user to remove an item at a specific index. We also want all items below the removed item to move up a step, and this is how we’ll do it:

        public void RemoveAt(int index) {

            //Create a temporary array


            Item[] temp = new Item[this.Size - 1];

            int count = 0;



            //Loop through the array and copy the elements


            for (int i = 0; i < this.Size; i++) { 

                //Don't copy if it is the element we want to remove


                if ((i != index)) {

                    temp[count] = this._items[ i];

                    count++;

                }

            }

            this._items = temp;

        }

Now we can also remove elements from the list, and the list will be automatically fill the gap.

    class Program{

        static void Main(string[] args){



            ItemList items = new ItemList();

            items.Add(new Item(1));

            items.Add(new Item(2));

            items.Add(new Item(3));

            items.Add(new Item(4));



            items.RemoveAt(2);



            Console.WriteLine("ItemList count: {0}", items.Count());

            Console.WriteLine("ItemList length: {0}", items.Size);

            //ItemList count: 3


            //ItemList length: 4


            Console.Read();

        }

    }

The full ItemList class will now look like this:

using System;



namespace ArrayExample{



    public class ItemList{

        //===========CONSTANTS


        private const int _defaultSize = 5;



        //===========FIELDS


        private Item[] _items;



        //===========PROPERTIES


        /// <summary>


        /// Get the length of the collection


        /// </summary>


        public int Size {

            get { return this._items.Length; }

        }



        /// <summary>


        /// Select an item in the collection by its indexer


        /// </summary>


        /// <param name="index">The item index</param>


        /// <returns>The item located at the specified index</returns>


        /// <exception cref="ArgumentOutOfRangeException">


        /// If index is outside the boundries of the collection, 


        /// this exception will be thrown


        /// </exception>


        public Item this[int index] {

            get {

                if ((index < 0) || index >= this.Size) {

                    throw new ArgumentOutOfRangeException();

                }

                return this._items[index];

            }

        }

        

        //===========CONSTRUCTOR


        public ItemList(){

            //Initate and set a default size for the array


            this._items = new Item[_defaultSize];

        }



        //===========METHODS


        /// <summary>


        /// Adds an Item object to the collection


        /// </summary>


        /// <param name="item">The Item object to add</param>


        public void Add(Item item) {



            if (Count() == this.Size) {



                //Create a new, temporary, array to hold the old values


                Item[] tempArray = new Item[this.Size];



                //Copy the old values to the temporary array


                for (int i = 0; i < this.Size; i++) {

                    tempArray[ i] = this._items[ i];

                }



                //Create a new size by doubling the old size


                int newSize = this.Size + this.Size;



                //Create a new array with the new and improved size


                this._items = new Item[newSize];



                //Copy back the old items to the new and improved array


                for (int i = 0; i < tempArray.Length; i++) {

                    this._items[ i] = tempArray[ i];

                }

            }



            //Add the new item


            int numberOfElements = Count();

            this._items[numberOfElements] = item;

        }



        /// <summary>


        /// Adds a range of Item objects to the collection


        /// </summary>


        /// <param name="items">An Item object array</param>


        public void AddRange(Item[] items) {

            foreach (Item i in items) {

                this.Add(i);

            }

        }



        /// <summary>


        /// Returns the number of actual elements in the collection


        /// </summary>


        /// <returns>


        /// An integer representing the actual elements in the collection


        /// </returns>


        public int Count() {

            int elements = 0;

            for (int i = 0; i < this.Size; i++) {

                if (this._items[ i] != null) {

                    elements++;

                }

            }

            return elements;

        }



        /// <summary>


        /// Removes an element in the array.


        /// Elements that comes after will move up one step


        /// </summary>


        /// <param name="index">The index of the element to remove</param>


        public void RemoveAt(int index) {

            //Create a temporary array


            Item[] temp = new Item[this.Size - 1];

            int count = 0;



            //Loop through the array and copy the elements


            for (int i = 0; i < this.Size; i++) {

                //Don't copy if it is the element we want to remove


                if ((i != index)) {

                    temp[count] = this._items[ i];

                    count++;

                }

            }

            this._items = temp;

        }



        /// <summary>


        /// Empties the collection


        /// </summary>


        public void Empty() {

            this._items = new Item[_defaultSize];

        }

    }

}



using System;



namespace ArrayExample{

    class Program{

        static void Main(string[] args){



            ItemList items = new ItemList();

            items.Add(new Item(1));

            items.Add(new Item(2));

            items.Add(new Item(3));

            items.Add(new Item(4));



            items.RemoveAt(2);



            Console.WriteLine("ItemList count: {0}", items.Count());

            Console.WriteLine("ItemList length: {0}", items.Size);

            //ItemList count: 3


            //ItemList length: 4


            Console.Read();

        }

    }

}

Luckily you don’t have to do this all the time, there is a class in the .NET library already that is called ArrayList that does all this. But that class works just like the ItemList class that we created. There is no magic behind it, all it does is resize the array when it has to.
There are now, from C# 2.0, more complex collection utilities to use with generics. The List<T> and Dictionary<T> classes makes working with collections even easier, but deep down in the bottom of these classes is an array working, just like the one in the ItemList.

There are no comments on this article.

Leave a message!

If you have any question or just want to leave a message, just fill out the form below!

Your e-mail will not be visible in your post, it is for validation reasons only

Name:
E-mail:
Comment: