Replacing two dimensional array with other data structure

Sounds like the data structure you have is a sparse matrix and I'm going to point you to Are there any storage optimized Sparse Matrix implementations in C#?

You can create a key for a dictionary from the array coordinates. Something like:

int key = x * 46000 + y;

(This naturally works for coordinates resembling an array up to 46000x46000, which is about what you can fit in an int. If you need to represent a larger array, you would use a long value as key.)

With the key you can store and retreive the object in a Dictionary<int, YourClass>. Storing and retrieving values from the dictionary is quite fast, not much slower than using an array.

You can iterate the items in the dictionary, but you won't get them in a predictable order, i.e. not the same as looping the x and y coordinates of an array.

If you need high performance you can roll down your own data structure. If the objects can be contained in only one container and not moved to other containers, you can do a custom hashset like data structure.

You add X, Y and Next fields into your class. You make a singly linked list of your object stored in an array that is your hash table. This can be very very fast.

I wrote it from scratch, there may be bugs. Clear, and rehash are not implemented, this is a demonstration only. Complexity of all operation is averaged O(1).

To make easy to enumerate on all nodes skipping empty nodes, there is a doubly linked list. Complexity of insertion and removal from a doubly linked list is O(1), and you will be able to enumerate all nodes skipping unused nodes, so the complexity for enumerating all nodes is O(n) where n is the number of nodes, not the "virtual" size of this sparse matrix.

Using a doubly linked list you can enumerate items in the same order as you insert it. The order is unrelated to X and Y coordinates.

public class Node
{
    internal NodeTable pContainer;
    internal Node pTableNext;
    internal int pX;
    internal int pY;
    internal Node pLinkedListPrev;
    internal Node pLinkedListNext;
}

public class NodeTable :
    IEnumerable<Node>
{
    private Node[] pTable;
    private Node pLinkedListFirst;
    private Node pLinkedListLast;

    // Capacity must be a prime number great enough as much items you want to store.
    // You can make this dynamic too but need some more work (rehashing and prime number computation).
    public NodeTable(int capacity)
    {
        this.pTable = new Node[capacity];
    }

    public int GetHashCode(int x, int y)
    {
        return (x + y * 104729); // Must be a prime number
    }

    public Node Get(int x, int y)
    {
        int bucket = (GetHashCode(x, y) & 0x7FFFFFFF) % this.pTable.Length;
        for (Node current = this.pTable[bucket]; current != null; current = current.pTableNext)
        {
            if (current.pX == x && current.pY == y)
                return current;
        }
        return null;
    }

    public IEnumerator<Node> GetEnumerator()
    {
        // Replace yield with a custom struct Enumerator to optimize performances.
        for (Node node = this.pLinkedListFirst, next; node != null; node = next)
        {
            next = node.pLinkedListNext;
            yield return node;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    public bool Set(int x, int y, Node node)
    {
        if (node == null || node.pContainer != null)
        {
            int bucket = (GetHashCode(x, y) & 0x7FFFFFFF) % this.pTable.Length;

            for (Node current = this.pTable[bucket], prev = null; current != null; current = current.pTableNext)
            {
                if (current.pX == x && current.pY == y)
                {
                    this.fRemoveFromLinkedList(current);

                    if (node == null)
                    {
                        // Remove from table linked list

                        if (prev != null)
                            prev.pTableNext = current.pTableNext;
                        else
                            this.pTable[bucket] = current.pTableNext;
                        current.pTableNext = null;
                    }
                    else
                    {
                        // Replace old node from table linked list

                        node.pTableNext = current.pTableNext;
                        current.pTableNext = null;

                        if (prev != null)
                            prev.pTableNext = node;
                        else
                            this.pTable[bucket] = node;

                        node.pContainer = this;
                        node.pX = x;
                        node.pY = y;

                        this.fAddToLinkedList(node);
                    }

                    return true;
                }
                prev = current;
            }

            // New node.

            node.pContainer = this;
            node.pX = x;
            node.pY = y;

            // Add to table linked list

            node.pTableNext = this.pTable[bucket];
            this.pTable[bucket] = node;

            // Add to global linked list

            this.fAddToLinkedList(node);

            return true;
        }
        return false;
    }

    private void fRemoveFromLinkedList(Node node)
    {
        Node prev = node.pLinkedListPrev;
        Node next = node.pLinkedListNext;

        if (prev != null)
            prev.pLinkedListNext = next;
        else
            this.pLinkedListFirst = next;

        if (next != null)
            next.pLinkedListPrev = prev;
        else
            this.pLinkedListLast = prev;

        node.pLinkedListPrev = null;
        node.pLinkedListNext = null;
    }

    private void fAddToLinkedList(Node node)
    {
        node.pLinkedListPrev = this.pLinkedListLast;
        this.pLinkedListLast = node;
        if (this.pLinkedListFirst == null)
            this.pLinkedListFirst = node;
    }
}

arrays give multiple features:

• A way of organizing data as a list of elements
• A way to access the data elements by index number (1st, 2nd, 3rd etc)

But a common downside (depends on the language and runtime) is that arrays are often work poorly as a sparse data structure--if you don't need all of the array elements then you end up with wasted memory space.

So, yes, a hashtable will usually save space over an array.

But You asked My main aim is to reduce the number of iterations only by changing the data structure. In order to answer that question, we need to know more about your algorithm--what you're doing in each loop of your program.

For example, there are many ways to sort an array or a matrix. The different algorithms for sorting use differing numbers of iterations.