双向链表 C# 移除倒数两个元素

Question

我尝试修复一个代码问题，它涉及到一个链表（LinkedList）。任务是删除列表的最后 X 个元素。我试过使用 RemoveRange 方法，但是 VS 不接受我的解决方案，并提示 RemoveRange 方法不存在。

var list = new DoublyLinkedList<string>();
list.Add("A");
list.Add("B");
list.Add("C");
list.Add("D");
list.Add("E");
list.RemoveLast(2);

这是程序（Main）中的代码。 在第二个类中应该有一个RemoveLast方法，但我无法获得一个可用的代码。有人可以解释一下，我如何获得RemoveLast吗？

using System;
using System.Collections;
using System.Collections.Generic;

namespace Test
{
    public class DoublyLinkedList<T> : IEnumerable<T>
    {    
        public void RemoveLast(int v)
        {
            int remove = Math.Max(0, this.Count - v);

            this.RemoveRange(v, this.Count - v);              
        }
     }
}

RemoveRange 被标红

感谢您的帮助！

完整的双向链表：

`using System;
using System.Collections;
using System.Collections.Generic;

namespace Test
{
    public class DoublyLinkedList<T> : IEnumerable<T>
    {
        public void RemoveLast(int v)
        {
            int remove = Math.Max(0, this.Count - v);

            this.RemoveRange(v, this.Count - v);



        }

        private sealed class Node
        {
            public T Item { get; set; }
            public Node Previous { get; set; }
            public Node Next { get; set; }
        }

        private Node first, last;

        public int Count { get; private set; }

        public void Add(T item)
        {
            Node newItem = new Node() { Item = item, Next = null, Previous = null };

            if (first == null)
            {
                first = newItem;
                last = newItem;
            }
            else
            {
                last.Next = newItem;
                newItem.Previous = last;

                last = newItem;
            }
            Count++;
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            Node node = first;

            while (node != null)
            {
                yield return node.Item;
                node = node.Next;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<T>)this).GetEnumerator();
        }

        public override string ToString()
        {
            string s = "";

            Node node = first;

            while (node != null)
            {
                s += node.Item.ToString() + " -> ";
                node = node.Next;
            }
            s += "Count: " + Count.ToString();

            return s;
        }

        private Node find(T item)
        {
            Node node = first;

            while (node != null)
            {
                if (node.Item.Equals(item))
                    return node;

                node = node.Next;
            }
            return null;
        }

        private Node findPrevious(T item)
        {
            Node previousNode = null;
            Node node = first;

            while (node != null)
            {
                if (node.Item.Equals(item))
                    return previousNode;

                previousNode = node;
                node = node.Next;
            }
            return null;
        }
    }
}`

- Unlexs

---

我使用的是VS Community 2019，版本号为16.5.4 @viveknuna。 - Unlexs

然后我在方法本身中使用该方法，结果出现了System.StackOverflowException。我必须让public void RemoveLast(int v)正常工作。但是就像问题所说的那样：我找不到正确的方法。 - Unlexs

你可以从 List<T> 继承，然后使用 RemoveRange() 方法。 - Vivek Nuna

我检查了这个，Sajid，但我认为我已经实现了所有这些。而且@IliarTurdushev，我编辑了我的问题并填写了完整的DoublyLinkedList。 - Unlexs

IEnumerable<T> 没有 RemoveRange() 方法。IEnumerable 只是暴露了枚举函数。你应该从 List<T> 继承，这样你就可以访问列表操作函数。 - Captain Kenpachi

Answer 1

你是否知道已经有一个双向链表类了呢？它就是System.Collections.Generic.LinkedList。我的建议是使用这个类。

如果重构你的代码太过繁琐，例如因为你的DoublyLinkedList已被广泛使用，那么我的建议是将DoublyLinkedList作为LinkedList的适配器。

class DoublyLinkedList<T> : IEnumerable<T>, IEnumerable
{
    private readonly LinkedList<T> linkedList = new LinkedList<T>();

    public int Count => this.linkedList.Count;

    public void Add(T item)
    {
        this.LinkedList.Add(item);
    }

    public IEnumerator<T> GetEnumerator()
    {
        return this.LinkedList.GetEnumerator();
    }

    ... // etc.
}

您需要添加一个方法来从您的列表中删除最后N个项目。例如，RemoveLast（10）应该从您的双向链接列表中删除最后10个元素。如果您的列表有10个或更少的元素，则会清除整个列表。

void Clear()
{
    this.LinkedList.Clear();
}

void RemoveLast()
{
    if (this.LinkedList.Count != 0)
        this.linkedList.RemoveLast();
}

void RemoveLast(int removeCount)
{
    if (this.Count <= removeCount)
    {
        this.linkedList.Clear();
    }
    else
    {
        for (int i=0; i<removeCount; ++i)
        {
            this.RemoveLast();
        }
    }
}

可能你的主管很固执，不遵循你的建议，重用经过充分测试的可信的.NET类。在这种情况下，您需要更改RemoveLast()方法。

void Clear()
{
    this.first = null;
    this.last = null;
    this.count = 0;
}

void RemoveLast()
{
    switch (this.Count)
    {
        case 0:
            // empty list; do nothing
            break;
        case 1:
            // removing the last element of the list
            this.Clear();
            break;

       default:
           var lastNode = this.last;

           // because more than one element I'm certain there is a previous node
           var previousNode = lastNode.Previous;
           var previousNode.Next = null;
           this.last = previousNode;
           --this.count;
           break;
    }
}

- Harald Coppoolse

---

在这种情况下，我不能使用 .net 类，但我明白您的意思！谢谢！ - Unlexs

Answer 2

如果RemoveRange不可用，您可以轻松地自行实现适用于任何可枚举对象而不需要使用Linq的方法（此代码仅作为想法，因为我无法访问您的所有代码）。

using System;
using System.Collections;
using System.Collections.Generic;

        public void RemoveRange(int count)
        {
            if (count > this.Count)
                throw new ArgumentOutOfRangeException(nameof(count));

            while (count > 0)
            {
                RemoveTail();
                count--;
            }
        }

        private void RemoveTail()
        {
            if (this.Count == 0)
                return;

            var previous = last.Previous;
            if (previous != null)
            {
                previous.Next = null;
                last = previous;

                this.Count--;
            }
            else
            {
                // this implies count == 1
                last = null;
                first = null;

                this.Count = 0;
            }
        }

基本上，您可以公开您的RemoveRange方法，然后逐个执行对最后一个节点（尾部）的不可知删除。

此答案已编辑以反映代码更改。

- Yennefer

---

非常感谢您的想法和代码，但是这段代码在我的代码上不起作用。我已经编辑了双向链表的其余部分。例如，我没有实现RemoveAt。唯一的方法是使用RemoveLast方法。但我找不到正确的方法。我已经花了一个星期在网上搜索、尝试和修复代码，但到目前为止，我还没有找到使用该方法删除最后x个元素的正确方法。 - Unlexs

它不起作用是因为我写错了一些代码行。让我来修复它。 - Yennefer

我发布了相关部分。试试看，然后告诉我 :) - Yennefer

Answer 3

以下是如何在您的DoublyLinkedList中实现RemoveLast(int n)的方法：

// Removes last "n" elements.
public void RemoveLast(int n)
{
    for (int i = 0; i < n; i++)
        RemoveLast();
}

// Removes the last element.
public void RemoveLast()
{
    // List is empty. No need to remove elements.
    if (first == null)
    {
        return;
    }
    // List contains only one element. Remove it.
    else if (first == last)
    {
        first = null;
        last = null;
    }
    // List contains more than one element. Remove the last.
    else
    {
        // The next two lines make "last" to point to the element before the last.
        last = last.Previous;
        last.Next = null;
    }

    Count--;
}

这里是完整的示例。

- Iliar Turdushev

---

非常感谢您的帮助。这正是我尝试过但无法实现的！谢谢！ - Unlexs