Связанный список C #, Tracks Head + Tail с APIs InsertAfter + Remove.Видите какие-либо недостатки или оптимизации?

Question

Другая структура данных, которую я написал в условиях интервью.По сути, это общий связанный список, который отслеживает начало и конец списка (вероятно, просто для академических упражнений, в жизни RL вы просто используете List).Кто-нибудь видит какие-либо возможные недостатки или оптимизации?

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

Это выглядит в основном звуковой код (игнорируя конструктивные соображения использования взаимодействий Collection, таких как перечисление, индексаторы и т. Д.)

Все проверки достоверности могут быть помещены в метод CheckValid, который просто вызывается из других ваших методов. У компилятора не должно быть проблем с его включением, поэтому вы не должны видеть снижение производительности в результате (и, конечно, если производительность является ключевой, вы должны использовать утверждения, а не проверки во время выполнения)

GetElementAt проверяет, должно ли генерироваться исключение на каждой итерации. Он может просто проверить, что значение позиции находится в пределах длины списка, прежде чем начинать перечислять элементы. (Это также приведет к сбою, если список пуст и передана ненулевая позиция). Это действительно должно проверить эту позицию> = 0 тоже.

Код для Remove и InsertAfter может использовать общий метод, который возвращает элементы в позиции и позиции-1. Это уменьшит необходимый код и уменьшит вдвое объем необходимого тестирования, хотя добавит к «InsertAfter» крошечные «предотвратимые накладные расходы».

Я бы назвал «Добавить» или «Добавить» сам, потому что он не вставляется.

Возможно, вы захотите вернуть данные из удаляемого элемента - в противном случае вам придется дважды просмотреть весь список, чтобы прочитать значение, а затем удалить его.

Answer 2

Реализация итератора.Ваш метод GetElementAt просит людей пройтись по списку, используя Алгоритм художника Шлемеля .

Чтобы уточнить: для каждого элемента в списке GetElementAt должен начинаться с начала иотсчитать записи в индексе записи, которую вы хотите.Таким образом, получение записей от 1 до ... скажем ... миллион будет (внутренне) включать просмотр списка миллион раз.Прогулка по списку становится операцией O (N ^ 2), которая побеждает одну из целей списка - быстрый последовательный доступ.Сравните это с итератором, который отслеживал бы его место в списке и просто каждый раз получал следующую запись, избегая цикла 0..n и делая обход намного быстрее.