How to modify my CustLinkedList to implement insert more efficiently

Question

I created a custom linked list on a whiteboard, for learning purposes. CustDoublyLinkedList class with the nested Node class, but when it is time to insert, at the specified index method must loop through until it get to an index to insert. I want to insert directly without using loop as my Add or PushFront methods work.

I also added some more method like IndexOf and Contain methods for the list

CustDoublyLinkedList<int> myList = new();

myList.Add(12);
myList.Add(13);
myList.Add(14);
myList.Add(45);
myList.Add(28);
myList.Add(120);

myList.PushFront(32);
myList.Insert(3,1500);

for (int i = 0; i < myList.Count; i++)
{
    Console.WriteLine(myList[i]);
}

class CustDoublyLinkedList<T>
{
    private class Node
    {
        public T Element { get; set; }
        public Node NextNode { get; set; }
        public Node PrevNode { get; set; }

        public Node(T data)
        {
            this.Element = data;
            this.PrevNode = null;
            this.NextNode = null;
        }

        public Node(T data, Node prevNode): this(data)
        {
            prevNode.NextNode = this;
        }

        public Node(T data, Node prevNode, Node nextNode) : this(data, prevNode)
        {
            nextNode.PrevNode = this;
        }
    }

    private Node head;
    private Node tail;
    private int counter;

    public CustDoublyLinkedList()
    {
        this.head = null;
        this.tail = null;
        this.counter = 0;
    }

    public void Insert(int index, T item)
    {
        if (index == 0)
        {
            throw new ArgumentOutOfRangeException("You Can Push with PushFront Method at Index: " + index);
        }

        if (index < 0 || index >= this.counter)
        {
            throw new ArgumentOutOfRangeException("invalid Index: " + index);
        }

        Node newNode = new(item);
        Node currentNode = this.head;

        for (int i = 0; i < index - 1; i++)
        {
            currentNode = currentNode.NextNode;
        }

        newNode.NextNode = currentNode.NextNode;
        newNode.PrevNode = currentNode.PrevNode;
        currentNode.NextNode = newNode;

        this.counter++;
    }

    public void Add(T item)
    {
        if (this.head == null)
        {
            this.head = new(item);
            this.tail = this.head;
        }
        else
        {
            Node newNode = new(item, this.tail);
            this.tail = newNode;
        }

        this.counter++;
    }

    public void PushFront(T item)
    {
        Node newNode = new(item);
        newNode.NextNode = this.head;
        newNode.PrevNode = null;

        if(this.head != null)
        {
            this.head.PrevNode = newNode;
        }

        this.head = newNode;
        this.counter++;
    }

    public bool Contain(T item)
    {
        int index = IndexOf(item);
    
        if (index != -1)
        {
            return true;
        }

        return false;
    }

    public int IndexOf(T item)
    {
        Node currentNode = this.head;
        int index = 0;

        while(currentNode != null)
        {
            if (object.Equals(currentNode.Element, item))
            {
                return index;
            }

            currentNode = currentNode.NextNode;
            index++;
        }

        return -1;
    }

    public int Count
    {
        get { return this.counter; }
    }

    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= this.counter)
            {
                throw new IndexOutOfRangeException("Invalid Index: " + index);
            }

            Node currentNode = this.head;

            for (int i = 0; i < index; i++)
            {
                currentNode = currentNode.NextNode;
            }

            return currentNode.Element;
        }
        set
        {
            if (index < 0 || index >= this.counter)
            {
                throw new IndexOutOfRangeException("Invalid Index: " + index);
            }

            Node currentNode = this.head;

            for (int i = 0; i < index; i++)
            {
                currentNode = currentNode.NextNode;
            }

            currentNode.Element = value;
        }
    }
}

Answer 1

You are looking for a Skip List

With this you can drive your insert requirement to O(log N) on average while still maintaining a linked list structure