Связанный список Design

Question

На днях в локальной группе .NET я пришел к следующему вопросу: «Является ли вопрос правильного собеседования о Linked Lists при найме кого-то для позиции разработки .NET?»

Не имея степени в области информатики и будучи самообразованным разработчиком, мой ответ был таким, что я не чувствовал, что это уместно, поскольку я через 5 лет развивается с .NET, никогда не подвергался связанным спискам и не слышал никаких убедительных причина использования для одного.

Однако человек отметил, что это очень распространенный вопрос для интервью, поэтому я решил, что когда я уйду, я сделаю некоторое повторное исследование связанных списков и посмотрю, чего я могу потерять.

Я прочитал несколько сообщений о переполнении стека и различных поисковых запросах Google и решил, что лучший способ узнать о них - это написать мои собственные классы .NET, чтобы увидеть, как они работают изнутри.

Вот мой класс структура

один список

Конструктор

public SingleLinkedList(object value); 

// Public Properties 
public bool IsTail; 
public bool IsHead; 
public object Value; 
public int Index; 
public int Count; 

// private fields not exposed to a property 
private SingleNode firstNode; 
private SingleNode lastNode; 
private SingleNode currentNode; 

Методы

public void MoveToFirst(); 
public void MoveToLast(); 
public void Next(); 
public void MoveTo(int index); 
public void Add(object value); 
public void InsertAt(int index, object value); 
public void Remove(object value); 
public void RemoveAt(int index); 

Вопросы у меня есть:

Каковы типичные методы, которые вы ожидаете в связанном списке?

Что такое типичное поведение при добавлении новых записей? Например, если у меня есть 4 узла, и я сейчас размещен во втором узле и выполняю Add(), должен ли он быть добавлен после или до текущего узла? Или он должен быть добавлен в конец списка?

Некоторые из конструкций, которые я видел, объясняя вещи, кажется, выставляют за пределами класса LinkedList объект Node. В моем проекте вы просто добавляете, получаете, удаляете значения и ничего не знаете об объекте узла.

Должны ли Head and Tail быть объектами-заполнителями, которые используются только для определения головы/хвоста списка?

Мне требуется, чтобы мой связанный список создавался с помощью значения, которое создает первый узел списка, который по существу является головкой и хвостом списка. Вы бы это изменили?

Какими должны быть правила, когда дело касается удаления узлов. Должен ли кто-нибудь удалить все узлы?

Вот мой двойной Связанный список

Конструкторы

public DoubleLinkedList(object value); 

Свойства

public bool IsHead; 
public bool IsTail; 
public object Value; 
public int Index; 
public int Count; 

Частные поля не подвержены через свойство

private DoubleNode currentNode; 

Методы

public void AddFirst(object value); 
public void AddLast(object value); 
public void AddBefore(object existingValue, object value); 
public void AddAfter(object existingValue, object value); 
public void Add(int index, object value); 
public void Add(object value); 
public void Remove(int index); 
public void Next(); 
public void Previous(); 
public void MoveTo(int index); 

Answer 1

Я советую просто подражать разумно продуманной реализации с C++. Одной из таких реализаций является SG Linked List. Обратите внимание, что страница, на которую я ссылаюсь, не является кодом, это список подписей и определений, как и тот, который вы указали.

Связанные списки являются слишком низким уровнем для среднего программиста на C#, чтобы действительно думать о них в обычных условиях. Обычно, основное понимание того, как они работают, и сложность различных задействованных операций достаточно, например. объединение двух связанных списков может быть выполнено в O (1) раз.

Примечание: обратите внимание на раздел «Модель» на странице SGI, так как каждый аналитический список является «образцом», обеспечивает гарантии сложности.

Answer 2

Существует множество способов реализации Связанного списка, но в конечном итоге они сводятся к серии объектов, каждая из которых имеет указатель на следующий объект. Тогда возникает вопрос «Какие еще функции я требую для выполнения того, что мне нужно с структурой данных Linked List?»

В контексте вопроса о собеседовании я буду менее озабочен тем, «какие методы мне нужны?». и больше беспокоиться о том, как рассуждать о структуре связанного списка достаточно для реализации любого произвольного метода, который задавал бы интервьюер.

Однако, если вы ищете более реалистичные сценарии типа Link Link Lists, я бы предложил вам взглянуть на дизайн API Java Linked List и .Net Linked List.

Answer 3

Похоже, что ваш LinkedList помнит, где он находится, а затем может выполнять различные действия соответственно. Я предпочел бы более простую конструкцию, как показано ниже (это Java, хотя):

class LinkedList<T> { 
    private int size; 
    private Node<T> head; 

    public int size(); 
    public T get(int index); 
    public void add(T newObject); 
    public void remove(int index); 
    public void remove(Object object); 
} 

class Node<T> { 
    T value; 
    Node<T> next; 
    Node<T> prev; // only applicable for doubly linked list 
} 

Таким образом, интерфейс такой же, будь то отдельно или дважды связанный список. В некоторых проектах есть ссылка на конец списка, поэтому в конце можно быстрее добавить материал, но для простоты, давайте пропустим это. Это все еще (условно принятый) связанный список.

Основные структуры данных и алгоритмы очень полезны. Люди часто не верят/понимают, что вещи, которые они не знают, на самом деле полезны. Конечно, смысл обучения такой вещи заключается не в том, чтобы реализовать дерево, когда вы идете на работу. Это помогает вам обосновать стоимость (в пространстве и времени) того, что вы делаете, или убедить себя, правилен ли фрагмент кода или нет.

Если вам интересно, есть курс с видеоматериалами от MIT here, или вы можете посмотреть this course из Стэнфорда, что связано с меньшей математикой. Надеюсь, вы найдете это удовольствие, чтобы учиться.

Удачи :)

Answer 4

Каковы типичные методы, которые вы бы планирующим в связанном списке?

Add(), AddAt(), Удалить(), RemoveAt(), ElementAtTop(), ElementAtLast(), ElementAt(),

Что типичное поведение при добавлении новых записей? Например, если у меня есть узлы, и я в настоящее время находится в втором узле и выполняю Add() , должен ли он быть добавлен после или до текущего узла ? Или он должен быть добавлен к концу списка?

Add(): Функциональность этого метода зависит от того, как вы реализуете связанный список. Скажем, если вы используете STACK, используя связанный список, этот метод добавит новый элемент (узел) в TOP-положение. Если вы используете QUEUE, используя связанный список, тогда элемент будет добавлен в последнюю позицию.

Некоторые из конструкций, которые я видел объясняющие вещи, кажется, подвергать вне класса LinkedList объекта Node. В моем дизайне вы просто добавляете, получаете, удаляете значения и знаете ничего об объекте узла.

Если голова и хвост быть объекты заполнителей, которые используются только для определения головы/хвоста списка?

Я думаю, ДА. Они были бы полезны для перемещения или смены связанного списка.

Я требую мой Связанный список будет экземпляр со значением, которое создает первый узел списка , который, по существу, голова и хвост из списка. Вы бы это изменили?

Я не уверен, понял ли я вас. Но я бы тоже реализовал его таким же образом.

Какими должны быть правила, когда наступает для удаления узлов. Должен ли кто-то быть в состоянии удалить все узлы?

Удалить(): То же объяснение, что и в Add(). Сопоставьте ссылки в Add().