How to use a Linked-List implementation with this Hash Function to avoid collisions?

Question

So for my assignment in my class this week, I have to demonstrate a hash function that stores data into a data structure and use a linked list implementation to avoid collisions. Given the source code from my professor, he stated that the code was correct but to change the array solution to a linked list. I'm not sure what he meant by that but here is the code below:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace Hashing
{
class hashFunction
{
    public hashFunction() { }


    public int HashFunc(String s, String[] arr)
    {
        int total = 0;
        char[] cname = s.ToCharArray();
        for (int i = 0; i < cname.Length; i++)
            total += 37 * total + (int)cname[i];
        total = total % arr.Length;
        if (total < 0)
            total += arr.Length;
        return (int)total;
    }

    public int Collision(int oldHashKey, String[] arr)
    {
        int newHashKey = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            newHashKey = 2 * oldHashKey - 1;
            if (arr[newHashKey] == null)
                break;
        }
        return (int)newHashKey;
    }
}


class Program
{
    static void Main(string[] args)
    {
        String[] names = new String[10007];
        String[] Animals = new String[] { "Lions", "Tigers", "Bears", "Aligators", "Snakes", "Eagles" };
        storeMessage(names, Animals);
    }

        public static void storeMessage(String[] arrMessage, String[] arrAnimal)
    {
        hashFunction newHashKey = new hashFunction();
        int[] arrayKeys = new int[arrAnimal.Length];
        String nm; int hashVal;
        for (int i = 0; i < 6; i++)
        {
            nm = arrAnimal[i];
            hashVal = newHashKey.HashFunc(nm, arrMessage);
            while (arrMessage[hashVal] != null)
                hashVal = newHashKey.Collision(hashVal, arrMessage);
            arrMessage[hashVal] = nm;
            arrayKeys[i] = hashVal;
        }
    }
}

}

It is somewhere with the method for the Collisions that it has to be linked list according to his instruction but I'm not sure.

Answer 1

See LinkedList.

LinkedList allows fast inserts and removes. It implements a linked list. Each object is separately allocated. Certain operations do not require the whole collection to be copied. In many common cases LinkedList hinders performance.

An example for implementing this in the Collisions:

public int Collision(int oldHashKey, LinkedList<string> arr)
{
    int newHashKey = 0;
    for (int i = 0; i < arr.Count; i++)
    {
        newHashKey = 2 * oldHashKey - 1;
        if (arr[newHashKey] == null)
            break;
    }
    return (int)newHashKey;
}

Notice that nothing much really changed. It's just that a LinkedList behaves like a List because it implements ICollection and IEnumerable. It's more convenient than a plain old array because you can just call the method Add and Remove if needed.