c# - 链表设计

Question

前几天，在我参加的一个本地 .NET 小组中，出现了以下问题:“在雇用某人担任 .NET 开发职位时，询问链表是否是一个有效的面试问题？”

我没有计算机科学学位并且是一名自学成才的开发人员，我的回答是我觉得这不合适，因为我在 5 年的 .NET 开发中从未接触过链表，也没有听到任何令人信服的理由供一个人使用。

但是那个人评论说这是一个非常常见的面试问题，所以我决定在离开时对链表进行一些研究，看看我可能遗漏了什么。

我已经阅读了很多关于堆栈溢出和各种谷歌搜索的帖子，并决定了解它们的最佳方式是编写我自己的 .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 和 Tail 是否应该是仅用于定义列表头/尾的占位符对象？

我需要用一个值来实例化我的链接列表，该值创建列表的第一个节点，该节点本质上是列表的头部和尾部。你会改变它吗？

删除节点的规则应该是什么。有人应该能够删除所有节点吗？

这是我的双链表

构造函数

public DoubleLinkedList(object value);

属性

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

不通过属性公开的私有(private)字段

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

看起来您的 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
}

所以不管是单链表还是双向链表，接口(interface)都是一样的。有些设计有对列表末尾的引用，因此在末尾添加内容会更快，但为了简单起见，让我们跳过它。它仍然是一个(通常接受的)链表。

基本的数据结构和算法非常有用。人们通常不相信/不理解他们不知道的东西实际上是有用的。当然，学习这种东西的目的不是在你上类的时候实现一棵树。它可以帮助您推断您所做事情的成本(空间和时间)，或者说服自己一段代码是否正确。

如果您有兴趣，这里有一个包含 MIT 视频的类(class) here ，或者您可以查看 this course来自斯坦福大学，涉及较少的数学。我希望您能从中找到学习的乐趣。

祝你好运:)