C# Linked List, Tracks Head + Tail with APIs InsertAfter + Remove. See any flaws or optimizations?

Question

Another data structure I wrote under interview conditions. It is essentially a generic linked list that tracks the head and tail of the list (probably just for academic exercise, in RL life you'd just use List). Does anyone see any possible flaws or optimizations?

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

namespace SingleLinkedHeadAndTail
{

    class SingleListEntry<T>
    {
        public T Data { get; set; }
        public SingleListEntry<T> Next {get; set;}
        public SingleListEntry(T data)
        {
            Data = data;
        }
    }

    public class SingleListExample<T>
    {
        private SingleListEntry<T> head;
        private SingleListEntry<T> tail;
        public int length { get; set; }
        public T Head
        {
            get
            {
                if (head != null)
                {
                    return head.Data;
                }
                return default(T);               
            }
        }

        public T Tail
        {
            get
            {
                if (tail != null)
                {
                    return tail.Data;
                }
                return default(T);
            }
        }

        public void Insert(T data)
        {
            if (head==null)
            {
                head = new SingleListEntry<T>(data);
                tail = head;
                length++;
            }
            else
            {
                tail.Next = new SingleListEntry<T>(data);
                tail = tail.Next;
                length++;
            }
        }

        public void InsertAfter(T data, int position)
        {
            if (position < 0)
            {
                throw new Exception("no soup for you - position must be 0 or higher");
            }

            if (head == null)
            {
                throw new Exception("sorry, you cannot insert after nothing, the list is empty.");
            }

            if (position >= length) //we could allow this stuff and padd out the list etc, but for now...no soup.
            {
                throw new Exception("Position requested is > then the length of the list.");
            }

            if (position == length - 1) //just an inswer
            {
                Insert(data);
                return;
            }


            SingleListEntry<T> newElement = new SingleListEntry<T>(data);
            SingleListEntry<T> temp = GetElementAt(position);             
            newElement.Next = temp.Next;
            temp.Next = newElement;            
            length++;
        }

        public T GetElement(int position)
        {
            return GetElementAt(position).Data;
        }

        private SingleListEntry<T> GetElementAt(int position)
        {
            SingleListEntry<T> temp = head;

            //pop down N levels until position
            int counter = 0;
            while (counter < position)
            {
                temp = temp.Next;
                counter++;
                if (temp == null && counter < position) //should have been caught
                {
                    throw new Exception(String.Format("{0} elements do not exist", position));
                }
            }

            return temp;
        }

        public void Remove(int position)
        {
            if (position < 0)
            {
                throw new Exception("no soup for you - position must be 0 or higher");
            }

            if (head == null)
            {
                throw new Exception("sorry, you cannot remove from nothing, the list is empty.");
            }

            if (position >= length) //we could allow this stuff and padd out the list etc, but for now...no soup.
            {
                throw new Exception("Position requested is > then the length of the list.");
            }

            if (position == 0) //head
            {
                head = head.Next;
                length--;
                return;
            }

            SingleListEntry<T> temp;
            temp = GetElementAt(position - 1);            
            if (position == length-1)
            { 
                tail = temp;
                tail.Next = null;
                length--;
                return;
            }


            temp.Next = temp.Next.Next;
            length--;            

        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            Test1();
            Test2();
            Test3();

        }

        public static void Test1()
        {
            SingleListExample<string> myList = new SingleListExample<string>();
            myList.Insert("joe");
            myList.Insert("mike");
            myList.Insert("adam");
            if (myList.Head != "joe") throw new Exception("fail");
            if (myList.Tail != "adam") throw new Exception("fail");
            if (myList.GetElement(1) != "mike") throw new Exception("fail");

        }

        public static void Test2()
        {
            SingleListExample<string> myList = new SingleListExample<string>();
            myList.Insert("joe");
            myList.Insert("mike");
            myList.Insert("adam");
            myList.InsertAfter("paul", 1);
            myList.InsertAfter("john", 0);
            myList.InsertAfter("nichole", 4);
            if (myList.Tail != "nichole") throw new Exception("fail");
            if (myList.Head!= "joe") throw new Exception("fail");

            if (myList.GetElement(0) != "joe") throw new Exception("fail");
            if (myList.GetElement(1) != "john") throw new Exception("fail");
            if (myList.GetElement(2) != "mike") throw new Exception("fail");
            if (myList.GetElement(3) != "paul") throw new Exception("fail");
            if (myList.GetElement(4) != "adam") throw new Exception("fail");
            if (myList.GetElement(5) != "nichole") throw new Exception("fail");

        }


        public static void Test3()
        {
            SingleListExample<string> myList = new SingleListExample<string>();
            myList.Insert("joe");
            myList.Insert("mike");
            myList.Insert("adam");
            myList.InsertAfter("paul", 1);
            myList.InsertAfter("john", 0);
            myList.InsertAfter("nichole", 4);

            myList.Remove(0);
            if (myList.Head != "john") throw new Exception("fail");

            myList.Remove(myList.length-1);
            if (myList.Tail != "adam") throw new Exception("fail");

            myList.Remove(1);
            if (myList.Head != "john") throw new Exception("fail");
            if (myList.Tail != "adam") throw new Exception("fail");
            if (myList.GetElement(0) != "john") throw new Exception("fail");
            if (myList.GetElement(1) != "paul") throw new Exception("fail");
            if (myList.GetElement(2) != "adam") throw new Exception("fail");


        }
    }
}

Answer 1

Implement an iterator. Your GetElementAt method is begging people to walk the list using Schlemiel the Painter's Algorithm.

To clarify: For each element in the list, GetElementAt has to start from the beginning and count out entries to the index of the entry you want. So getting the entries from 1 to...say..a million would (internally) involve running through the list a million times. Walking the list becomes an O(N^2) operation, which defeats one of the purposes of a list -- fast sequential access. Contrast that with an iterator, which would keep track of its place in the list and just get the next entry each time, avoiding the 0..n loop and making traversal a whole lot faster.

Answer 2

It looks fundamentally sound code (ignoring the design considerations of using Collection interafces like enumeration, indexers, etc)

All the validity checks could be put into a 'CheckValid' method that is simply called from your other methods. The compiler should have no problem inlining it, so you shouldn't see a performance degradation as a result (and of course, if performance is key, you'd use asserts, not runtime checks)

GetElementAt checks if it should throw the exception on every iteration. It could just check that the position value is within the list length before starting to enumerate items. (It will also crash if the list is empty and a nonzero position is passed in). It should really validate that position >= 0 too.

The code for Remove and InsertAfter could use a common method which returns the items at position and position-1. THis would reduce the code needed and halve the amount of testing required, although it would add a tiny 'avoidable overhead' to InsertAfter.

I'd tend to name Insert "Add" or "Append" myself, because it's not inserting.

You might consider returning the data from the item you Remove - otherwise you have to search the whole list twice to read a value and then remove it.