C＃中的链接列表_编程黑洞网

我正在寻找具有与本机List相同功能的链表的实现。

我希望功能更接近List。 System.Collections.Generic.LinkedList错过了一些我曾经使用过的方法，例如Add Sort或按索引访问mylist[0]

我找不到一个，所以我自己做了一个：

我添加了与List相同的构造函数

在这种情况下，我使用了合并排序方式，这应该是性能最高的
我添加了IEnumberable以便能够使用Linq的功能
我添加了List的所有本机方法

我正在寻找错误，性能改进或缺少功能。

注意：这不是关于循环或双向链表；这只是一个单链表。

public class Node<T>
{
    public T data;
    public Node<T> next;
}

public class MyLinkedList<T> : IEnumerable<T>, System.Collections.IEnumerable
{
    private Node<T> _headNode;
    private int _count;
    public int Count { get { { return _count; } } }

    private IEnumerable<Node<T>> Nodes
    {
        get
        {
            Node<T> node = _headNode;
            while (node != null)
            {
                yield return node;
                node = node.next;
            }
        }
    }

    private Node<T> Pop()
    {
        Node<T> tResult = null;
        if (_headNode != null)
        {
            tResult = _headNode;
            _headNode = _headNode.next;
            _count--;
        }
        return tResult;
    }

    private void Push(Node<T> item)
    {
        item.next = _headNode;
        _headNode = item;
        _count++;
    }

    private Node<T> NodeAt(int index)
    {
        if (index < 0 || index + 1 > _count)
        {
            throw new IndexOutOfRangeException("Index");
        }
        int counter = 0;
        foreach (Node<T> item in Nodes)
        {
            if (counter == index)
            {
                return item;
            }
            counter++;
        }
        return null;
    }

    public MyLinkedList()
    {
        _headNode = null;
        _count = 0;
    }

    public MyLinkedList(IEnumerable<T> Items)
    {
        foreach (T item in Items)
        {
            Add(item);
        }
    }

    public void ForEach(Action<T> action)
    {
        foreach (Node<T> item in Nodes)
        {
            action(item.data);
        }
    }

    public void AddRange(IEnumerable<T> Items)
    {
        foreach (T item in Items)
        {
            Add(item);
        }
    }

    public void AddRange(params T[] Items)
    {
        foreach (T item in Items)
        {
            Add(item);
        }
    }

    public T this[int index]
    {
        get { return NodeAt(index).data; }
        set { NodeAt(index).data = value; }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    public IEnumerator<T> GetEnumerator()
    {
        foreach (Node<T> item in Nodes)
        {
            yield return item.data;
        }
    }

    public bool Exists(T value)
    {
        foreach (Node<T> item in Nodes)
        {
            if (Comparer<T>.Default.Compare(value, item.data) == 0)
            {
                return true;
            }
        }
        return false;
    }

    public void Clear()
    {
        _headNode = null;
        _count = 0;
    }

    public void Shuffle()
    {
        if (_headNode != null)
        {
            Random rRand = new Random();
            T[] aResult = new T[_count];
            int i = 0;

            foreach (Node<T> nItem in Nodes)
            {
                int j = rRand.Next(i + 1);
                if (i != j)
                {
                    aResult[i] = aResult[j];
                }
                aResult[j] = nItem.data;
                i++;
            }
            this.Clear();
            this.AddRange(aResult);
        }
    }

    public void Sort()
    {
        _headNode = MergeSortSub(_headNode);
    }

    private Node<T> MergeSortSub(Node<T> nHead)
    {
        if (nHead == null || nHead.next == null) { return nHead; }
        Node<T> nSeeker = nHead;
        Node<T> nMiddle = nSeeker;
        while (nSeeker.next != null && nSeeker.next.next != null)
        {
            nMiddle = nMiddle.next;
            nSeeker = nSeeker.next.next;
        }
        Node<T> sHalf = nMiddle.next;
        nMiddle.next = null;
        Node<T> nFirst = MergeSortSub(nHead);
        Node<T> nSecond = MergeSortSub(sHalf);
        Node<T> nResult = new Node<T>();
        Node<T> nCurrent = nResult;
        while (nFirst != null && nSecond != null)
        {
            IComparer<T> comparer = Comparer<T>.Default;
            if (comparer.Compare(nFirst.data, nSecond.data) < 1)
            {
                nCurrent.next = nFirst;
                nFirst = nFirst.next;
            }
            else
            {
                nCurrent.next = nSecond;
                nSecond = nSecond.next;
            }
            nCurrent = nCurrent.next;
        }
        nCurrent.next = (nFirst == null) ? nSecond : nFirst;
        return nResult.next;
    }

    public void Add(T item)
    {
        Node<T> NewNode = new Node<T>() { data = item, next = _headNode };
        _headNode = NewNode;
        _count++;
    }

    public IEnumerable<int> AllIndexesOf(T Value)
    {
        int IndexCount = 0;
        foreach (Node<T> item in Nodes)
        {
            if (Comparer<T>.Default.Compare(item.data, Value) == 0)
            {
                yield return IndexCount;
            }
            IndexCount++;
        }
    }

    public int IndexOf(T Value)
    {
        IEnumerator<int> eN = AllIndexesOf(Value).GetEnumerator();
        if (eN.MoveNext())
        {
            return eN.Current;
        }
        return -1;
    }

    public int LastIndexOf(T Value)
    {
        IEnumerator<int> eN = AllIndexesOf(Value).GetEnumerator();
        int Result = -1;
        while (eN.MoveNext())
        {
            Result = eN.Current;
        }
        return Result;
    }

    public void RemoveAll(Func<T, bool> match)
    {
        while (_headNode != null && match(_headNode.data)) //  head node
        {
            _headNode = _headNode.next;
            _count--;
        }
        if (_headNode != null)
        {
            Node<T> nTemp = _headNode;
            while (nTemp.next != null)// other nodes
            {
                if (match(nTemp.next.data))
                {
                    nTemp.next = nTemp.next.next;
                    _count--;
                }
                else
                {
                    nTemp = nTemp.next;
                }
            }
        }
    }

    public IEnumerable<T> Find(Predicate<T> match)
    {
        foreach (Node<T> item in Nodes)
        {
            if (match(item.data))
            {
                yield return item.data;
            }
        }
    }

    public void Distinct()
    {
        HashSet<T> uniques = new HashSet<T>();
        Node<T> nTemp = _headNode;
        if (nTemp != null)
        {
            uniques.Add(_headNode.data);
            while (nTemp.next != null)
            {
                if (!uniques.Add(nTemp.next.data))
                {
                    nTemp.next = nTemp.next.next;
                    _count--;
                }
                else
                {
                    nTemp = nTemp.next;
                }
            }
        }
    }

    public void Reverse()
    {
        Node<T> nCurrent = _headNode;
        Node<T> nBack = null;
        while (nCurrent != null)
        {
            Node<T> nTemp = nCurrent.next;
            nCurrent.next = nBack;
            nBack = nCurrent;
            nCurrent = nTemp;
        }
        _headNode = nBack;
    }

    public void RemoveFirst()
    {

        if (_headNode != null)
        {
            _headNode = _headNode.next;
            _count--;
        }
    }

    public void RemoveLast()
    {
        if (_headNode != null)
        {
            if (_headNode.next == null)
            {
                _headNode = null;
            }
            else
            {
                NodeAt(Count - 2).next = null;
            }
            _count--;
        }
    }

    public void AddLast(T item)
    {
        Node<T> NewNode = new Node<T>() { data = item, next = null };
        if (_headNode == null)
        {
            _headNode = NewNode;
        }
        else
        {
            NodeAt(Count - 1).next = NewNode;
        }
        _count++;
    }

    public void Insert(T item, int index)
    {
        if (index < 0 || index + 1 > _count)
        {
            throw new IndexOutOfRangeException("Index");
        }

        Node<T> NewNode = new Node<T>() { data = item, next = null };
        if (index == 0)
        {
            NewNode.next = _headNode;
            _headNode = NewNode;
        }
        else
        {
            NewNode.next = NodeAt(index - 1).next;
            NodeAt(index - 1).next = NewNode;
        }
        _count++;
    }

    public void RemoveAt(int index)
    {
        if (index < 0 || index + 1 > _count)
        {
            throw new IndexOutOfRangeException("Index");
        }

        if (index == 0)
        {
            _headNode = _headNode.next;
        }
        else
        {
            Node<T> temp = NodeAt(index - 1);
            temp.next = temp.next.next;
        }
        _count--;
    }

    public void RemoveRange(int index, int count)
    {
        if (index < 0 || index + count > _count)
        {
            throw new IndexOutOfRangeException("Index");
        }
        if (index == 0)
        {
            for (int i = 0; i < count; i++)
            {
                _headNode = _headNode.next;
            }
        }
        else
        {
            Node<T> nStart = NodeAt(index - 1);
            for (int i = 0; i < count; i++)
            {
                nStart.next = nStart.next == null ? null : nStart.next.next;
            }
        }
        _count -= count;
    }
}

您可能可以为某些所需方法添加扩展功能。通常，开发人员避免重新实现内置的.net功能，除非有正当的理由（我不想断定），但是您可以避免在您的情况下重新实现。

出于兴趣，List会比内置的LinkedList和您正在创建的List都快。由于缓存和内存位置问题，在现代计算机中，链表自然较慢。而且双向链表仍然是链表，您所说的是单链表，许多人都将“链表”称为双链表，因为它们更常见也更有用。 br />

Tolani Jaiye-Tikolo的回答使我感到奇怪：为什么在不利用链接列表的好处的情况下将其视为“正常”列表？难道这两个世界都不对吗？索引性能差和插入性能差？

@PieterWitvoet我认为没有理由使用有效的链表。在几乎每种情况下，性能都较差-我做了很多工作，并且是唯一一种比List更快的方法：总是在第一个位置插入项目：)

#1 楼

请注意以下几点：

以相反的顺序从另一个可枚举的商店创建链接列表。这可能不是大多数人所期望的。请注意，System.Collections.Generic.LinkedList确实保留了原始顺序。
Add的情况与此类似：它会将商品添加到前面。熟悉List<T>的人们可能希望它会在末尾添加。请注意，LinkedList明确使用AddFirst和AddLast，很可能避免这种混淆。当然，并不是所有的收藏品都是有序的，但是如果您确实想遵守这种行为，那么至少要记录在案。
在执行时执行ICollection(<T>)和IList(<T>)。无论如何，您已经实现了它们的大多数功能（有时使用不同的方法名称或方法使用不同的参数顺序）。
跟踪尾节点可让您提高在末尾添加项目的性能（以使得删除和插入节点更加复杂）。
确实不需要几种方法作为成员方法，例如Find，Distinct和Reverse。 Linq已经为它们提供了扩展方法（除了Find被称为Where以外，使用了几乎相同的名称）。
ForEach也可以说相同：可以轻松地将其实现为扩展方法，从而使其可用于实现IEnumerable(<T>)的所有内容。或者您可以只使用foreach。
某些方法似乎未使用，例如Pop和Push。

\ $ \ begingroup \ $
Find和Distinct的行为将类似于Linq版本，但是“ Reverse（）”实际上是在反转列表本身，并且避免了常规的“ Reverse（）”方法在IEnumerable上需要的临时存储< >
\ $ \ endgroup \ $
–布莱斯·瓦格纳（Bryce Wagner）
16年8月10日在13:35

#2 楼

我想快速指出当前实施中的一个大问题。

您的链表广泛使用O（n）的NodeAt方法。但是，原始实现中的AddLast为O（1）。这可能是一个真正的瓶颈。

在评论中，您说：

System.Collections.Generic.LinkedList缺少一些我习惯的方法
使用，例如添加排序或按索引访问mylist [0]

LinkeList的Add方法是AddLast

您可以对项目进行排序使用OrderBy

您可以使用ElementAt通过索引访问元素（这与实现的速度一样快，也可能像它一样慢）

例如：

var foo = new LinkedList<string>(new[] { "z", "b", "a", "c" });
var fooSorted = new LinkedList<string>(foo.OrderBy(x => x));
var nthFoo = foo.ElementAt(2);

排序和返回新的链表也可能是扩展。

\ $ \ begingroup \ $
O（1）不能用于链表。我故意决定不实施循环或杜比链表。
\ $ \ endgroup \ $
– fubo
16年8月8日在11:42

\ $ \ begingroup \ $
@fubo LinkedList .AddLast方法（T）此方法是O（1）操作。像其他一些使链表如此有用和快速的方法。
\ $ \ endgroup \ $
–t3chb0t
16年8月8日在11:44

\ $ \ begingroup \ $
@fubo为什么？ LinkedList 被实现为循环双向链接列表，该列表允许最后一个节点上的操作为O（1）。
\ $ \ endgroup \ $
–Random832
16年8月8日在13:44

\ $ \ begingroup \ $
@ Random832，因为这与实现基本链接列表有关。我知道与列表相比的性能问题，而且我知道链表几乎在每种情况下都比较慢。
\ $ \ endgroup \ $
– fubo
16年8月8日在13:49

#3 楼

命名：局部变量应使用camelCase命名。 NewNode => newNode。

使用LINQ可以缩短某些方法。例如：

public bool Exists(T value)
{
    return Nodes.Any(node => Comparer<T>.Default.Compare(value, node.data) == 0);
}

此外，如果您的目标是模仿IList<T> API，则也可以使用相同的方法名称：Contains而不是Exists。

如果要创建默认LinkedList的替代品，我希望它至少实现相同的接口：

  LinkedList<T> : ICollection<T>, IEnumerable<T>, 
  IEnumerable, ICollection, IReadOnlyCollection<T>, ISerializable, 
  IDeserializationCallback

您可能还希望实现IList<T>。您的链表也缺少一些最基本的功能，例如在背面添加新元素。

考虑所有事情，我认为您的课程不是很有用。如果需要经常按索引访问项目，则应使用常规的List<T>，即period。常规列表在添加项目时并没有那么慢，但是在通过索引访问项目时却要快得多。如果您偶尔需要按索引获取项目，则应该为常规链表创建扩展方法：

public static T ElementAt<T>(this LinkedList<T> list, int index)
{
    //throw "index out of range" exceptions, if needed
    return list.Skip(index).FirstOrDefault();
}

并完成它。
编辑：哦，先生。 t3chb0t是正确的。我完全忘记了，LINQ已经具有ElementAt方法。因此，您甚至不必自己实现它。更好。

#4 楼

除了其他评论者已经确定的内容。

修改构造函数：仅当集合不为null时，才应尝试从集合中添加项目。例如，执行以下操作会抛出NullReferenceException

     MyLinkedList<string> myLinkedList = new MyLinkedList<string>(null);
    Console.WriteLine(myLinkedList.Count);

你应该扔ArgumentNullException。例如

 public MyLinkedList(IEnumerable<T> Items)
        {
            if (Items == null)
            {
                throw new ArgumentNullException(nameof(Items));
            }
            foreach (T item in Items)
            {
                Add(item);
            }
        }

您的实现中有太多混乱，例如Find。从我的角度来看，Find应该返回一个Node而不是IEnumerable<T>，因此应在NodeAt方法中使用它。通常，Find的C＃定义基于称为value的参数进行标识，该参数是data类中的Node，例如

  public LinkedListNode<T> Find(T value)
        {
            // finds node and returns node
            return null;
        }

由于不依赖于Find方法，因此可以将其扩展为基于indexing查找节点。下面是一个代码片段

   private Node<T> NodeAt(int index)
        {
            if (index < 0 || index + 1 > _count)
            {
                throw new IndexOutOfRangeException("Index");
            }
           Node<T> foundNode = Nodes.Find(index);
           // return foundNode

            return null;
        }

  public Node<T> Find(T item)
        {
            Node<T> node = _headNode;
            while (node != _headNode)
            {
                // iteratively  assign node to the next item and compare the data
            }
            return null;
        }

当您有两种方法做相同的事情时，您应该担心-DRY。这是两种AddRange方法发生的。默认情况下，Array具有固定大小，params允许您动态添加可变数量的项目。这等于在C＃中使用ArrayList。如果我再次提醒您，ArrayList实现了IEnumerable接口，这使第二种方法变得非常多余。

\ $ \ begingroup \ $
Find不应返回一个节点-节点是内部的实现细节，返回一个节点将允许调用者对其进行处理。采取谓词并返回值与其他Find方法一致。唯一的问题是它叫做Find而不是FindAll。
\ $ \ endgroup \ $
– Pieter Witvoet
16年8月9日在7:05

\ $ \ begingroup \ $
你可能是正确的。在LinkedList实现的上下文中，Find确实返回一个Node。采取谓语也是解决此问题的好方法。如果OP使用良好的命名约定FindAll而不是Find，也会有所帮助。
\ $ \ endgroup \ $
– Siobhan
16年8月9日在8:05

\ $ \ begingroup \ $
是的，LinkedList .Find返回一个节点（我只在查看List .Find和Array.Find）。但是LinkedList 还提供了接受节点作为参数的方法，因此它们是公共“接口”的一部分，而OP的代码则不是这种情况。公开和使用类似的节点看起来是一个更好的设计-迫使您考虑链接列表的特征（例如，廉价的随机访问）。
\ $ \ endgroup \ $
– Pieter Witvoet
16年8月9日在8:40

#5 楼

在添加其他要点之前，我想强调其他人提出的一些观点。特别是对索引链表进行索引从来都不是一个好主意，所有局部变量和参数都应使用驼峰式大小写而不是帕斯卡大小写。

要在IndexOf和
LastIndexOf中使用裸枚举器，应改用foreach。例如，

public int IndexOf(T Value)
{
    foreach (var n in AllIndexesOf(Value).GetEnumerator())
    {
        return n;
    }
    return -1;
}

Node应该拥有自己的构造函数，而不仅仅是默认构造函数。同样，它的
字段不应公开，因为这意味着使用您班级的人可以通过分配给
节点的字段来摆弄列表的内部结构。相反，您应该将它们隐藏到您的所有内容之外，并为LinkedList提供一些Node<T> -only属性。
从外部代码中隐藏字段的最佳方法可能是
使它们成为public属于get。
通常，internal应该是方法而不是属性
，因为属性并不是真的要那样使用。
在这里人们可能会不同意我的观点，但首选在技术环境（例如计算机科学）中，索引的复数
是索引。
public应该是Nodes，即使这样，由于有很大的暗示性，AllIndexesOf的一部分也值得商bat。如果我要
某些东西的索引，如果有些东西被遗漏了，我会很生气
，除非我指定了将它们排除在外的理由。
很多方法看起来像它们应该是AllIndicesOf和All之类的扩展方法。 Linq中的Enumerable Shuffle，除了它被称为
Find(Predicate<T> match)。
给定
基于谓词的性质，理想情况下应将Find方法称为Where。。同样，它使用RemoveAll
而不是RemoveWhere查找的事实也是一个问题。说到
Func<T, bool>和Predicate<T>应该理想地选择一个并
坚持下去。
我不确定自己的随机播放算法有多好，但我敢打赌它不如它可能是。我建议使用Fisher-Yates的实现
Shuffle来确保良好的随机性。
最后，可以将Predicate<T>重新路由为使用
Func<T, bool>演员表。