简单LinkedList

Question

我想这已经做了几次了，但我想抓住机会在c#中创建一个简单的通用链接列表。你觉得呢？

这是主修课。

public class LinkedList: IEnumerator
{
    private Node head;
    private Node tail;


    public T Current
    {
        get { return myCurrentNode.GetValue(); }
    }

    object IEnumerator.Current => Current;

    private Node myCurrentNode;

    public LinkedList()
    {
        head = null;
        tail = null;
    }


    public void Add(T value)
    {
        if (head == null && tail == null)
        {
            head = new Node(value);
            tail = head;
            Reset();
            return;
        }

        tail.SetNextNode(new Node(value));
        tail = tail.GetNextNode();
    }

    public void RemoveCurrentNode()
    {
        var node = new Node();
        node.SetNextNode(head);

        while (node.GetNextNode() != myCurrentNode)
        {
            node = node.GetNextNode();
        }

        var nextNode = myCurrentNode.GetNextNode();
        node.SetNextNode(nextNode);

        if (head == myCurrentNode)
        {
            head = nextNode;
        }

        if (tail == myCurrentNode)
        {
            tail = node;
        }

        myCurrentNode = nextNode;
    }

    public bool MoveNext()
    {
        var nextNode = myCurrentNode.GetNextNode();
        if (nextNode != null)
        {
            myCurrentNode = nextNode;
            return true;
        }

        return false;
    }

    public void Reset()
    {
        myCurrentNode = new Node();
        myCurrentNode.SetNextNode(head);
    }

    public void Dispose()
    {
        myCurrentNode = null;
        head = null;
        tail = null;
    }
}

节点类

public class Node
{
    private T _value;
    private Node _nextNode;

    public Node()
    {

    }

    public T GetValue()
    {
        return _value;
    }

    public Node(T Value)
    {
        _value = Value;
    }

    public Node GetNextNode()
    {
        return _nextNode;
    }

    public void SetNextNode(Node nextNode)
    {
        _nextNode = nextNode;
    }
}

以及三个单元测试来检查我的实现。

public class LinkedListTest
{
    private LinkedList.LinkedList linkedList;
    private List initialList;

    [Fact]
    public void LinkedListCanBeEnumerated()
    {
        //arange
        InitializeLinkedList(100);

        //act
        int[] array = new int[100];
        int index = 0;
        while (linkedList.MoveNext())
        {
            array[index++] = (linkedList.Current);
        }

        //assert
        array.ToList().ForEach(i => initialList.Contains(i).ShouldBe(true));
    }

    private void InitializeLinkedList(int howMany)
    {
        linkedList = new LinkedList.LinkedList();
        initialList = Enumerable.Range(1, howMany).ToList();
        initialList.ForEach(i => linkedList.Add(i));
    }

    [Fact]
    public void RemovingCurrentNodeShouldAlterTheList()
    {
        //arange
        InitializeLinkedList(100);

        //act
        linkedList.MoveNext();
        linkedList.RemoveCurrentNode();
        linkedList.Reset();

        int[] array = new int[100];
        int index = 0;
        while (linkedList.MoveNext())
        {
            array[index++] = (linkedList.Current);
        }

        //assert
        array.ToList().ForEach(i => i.ShouldNotBe(1));

    }

    [Fact]
    public void RemovingTailNodeShouldResultInADifferentTailNode()
    {
        //arange
        InitializeLinkedList(3);

        //act
        linkedList.MoveNext();
        linkedList.MoveNext();
        linkedList.MoveNext();

        linkedList.RemoveCurrentNode();
        linkedList.Reset();

        int[] array = new int[3];
        int index = 0;
        while (linkedList.MoveNext())
        {
            array[index++] = (linkedList.Current);
        }

        //assert
        array.ToList().ForEach(i => i.ShouldNotBe(3));
    }
}

Answer 1

Collection !=枚举器

我在这里看到的主要问题是LinkedList实现了IEnumerator而不是IEnumerable。这是一个错误的接口，这使得这个类很难使用:您现在必须手动调用MoveNext()和Current，而不是能够使用foreach。这也阻止了您使用Linq方法，并且不能同时执行枚举。

IEnumerable表示可以枚举的一系列项，例如数组、(链接)列表或生成器方法(yield)的结果。

IEnumerator表示枚举集合的行为。枚举数很少直接使用--它们通常隐藏在foreach语句后面(在给定枚举中调用GetEnumerator以获得枚举数)。

上面的意思是myCurrentNode不属于这个类-它应该是枚举器的一部分。Current、MoveNext、Reset和Dispose也是如此。

关于RemoveCurrentNode，它既繁琐又低效。烦琐，因为您不能只是将要删除的值(或节点)作为参数传递--您必须通过枚举列表来查找它。效率低下，因为一旦找到了正确的节点，RemoveCurrentNode还必须执行线性搜索才能找到前面的节点。

看一看System.Collections.Generic.LinkedList，得到一些灵感。这是一个双链接列表，所以并不是所有的方法都适用于您的情况，但它应该让您了解如何发挥链接列表的优势。

其他笔记

• 从本质上说，IEnumerator.Reset是不可取的。再次枚举集合是通过获取新的枚举器来完成的。现代枚举数通常会在Reset中抛出异常。
• 请注意，IEnumerable.GetEnumerator很容易用yield实现。
• 没有必要将head和tail初始化为null --这是它们的默认值。
• 这里也没有处置的必要--这里没有需要处置的非管理资源。
• 为什么Node使用Java风格的get和set方法而不是属性？我希望看到public T Value { get; }和public Node NextNode { get; set; }。
• 就我个人而言，我将在不创建额外节点的情况下处理head == myCurrentNode边缘情况。无论是否有代码复杂性，都不会有太大的差别，所以我会选择更有效的方法(没有额外分配的方法)。
• LinkedList(IEnumerable collection)构造函数将是有用的。