C# - 链表 - 如何删除指定节点后的所有节点？

Question

我正在使用通用LinkedList实现撤销/重做缓冲区。

在这种状态下: [顶部] state4 (已撤销) state3 (已撤销) state2 <-- 当前状态 state1 [底部]

当我执行Push操作时，我想删除当前状态之后的所有状态，并将新状态推入。

我的当前解决方法是执行while(currentState != list.last), list.removeLast();但它很糟糕。

LinkedList只支持Remove、RemoveFirst和removeLast...

我想要类似于RemoveAllNodesAfter(LinkedListNode...)的东西？

我该如何优雅地编写代码，而不必遍历所有节点？也许可以使用扩展？...

- rockeye

Answer 1

我没有在标准LinkedList<T>中找到任何可以做到这一点的东西。如果您想要，可以查看PowerCollections和C5 collections - 或者只需自己编写LinkedList类型。这是实现最简单的集合之一，特别是如果您可以以“即时”方式添加功能。

- Jon Skeet

Answer 2

如果我要自己实现这个功能，我会选择一种不同的方法来实现。

与其使用.RemoveAllNodesAfter(node)方法，我会选择创建一个.SplitAfter(node)方法，该方法返回一个以node后面的下一个节点为起点的新链表。这将比仅仅截断尾部更加方便。如果你需要RemoveAllNodesAfter方法，它只需要在内部调用SplitAfter方法并丢弃结果即可。

朴素的实现：

public LinkedList<T> SplitAfter(Node node)
{
    Node nextNode = node.Next;

    // break the chain
    node.Next = null;
    nextNode.Previous = null;

    return new LinkedList<T>(nextNode);
}

public void RemoveAllNodesAfter(Node node)
{
    SplitAfter(node);
}

- lassevk

---

谢谢您的回答，但是“下一个”和“上一个”是只读的。 - rockeye

这完全正确，我的意思是如果你创建自己的LinkedList实现，那就是我会做的方式。 - Lasse V. Karlsen

Answer 3

链表（特别是单向链表）是最基本的集合结构之一。我相信你可以很容易地实现它（并添加所需的行为）。

实际上，你并不需要一个集合类来管理列表。你可以在没有集合类的情况下管理节点。

public class SingleLinkedListNode<T>
{
    private readonly T value;
    private SingleLinkedListNode<T> next;

    public SingleLinkedListNode(T value, SingleLinkedListNode<T> next)
    {
        this.value = value;
    }

    public SingleLinkedListNode(T value, SingleLinkedListNode<T> next)
        : this(value)
    {
        this.next = next;
    }

    public SingleLinkedListNode<T> Next
    {
        get { return next; }
        set { next = value; }
    }

    public T Value
    {
        get { return value; }
    }
}

如果你对可能的实现感兴趣，这里有一个相对简单的单链表（SingleLinkedList）实现。

public class SingleLinkedList<T>
{
    private SingleLinkedListNode<T> head;
    private SingleLinkedListNode<T> tail;

    public SingleLinkedListNode<T> Head
    {
        get { return head; }
        set { head = value; }
    }

    public IEnumerable<SingleLinkedListNode<T>> Nodes
    {
        get
        {
            SingleLinkedListNode<T> current = head;
            while (current != null)
            {
                yield return current;
                current = current.Next;
            }
        }
    }

    public SingleLinkedListNode<T> AddToTail(T value)
    {
        if (head == null) return createNewHead(value);

        if (tail == null) tail = findTail();
        SingleLinkedListNode<T> newNode = new SingleLinkedListNode<T>(value, null);
        tail.Next = newNode;
        return newNode;
    }

    public SingleLinkedListNode<T> InsertAtHead(T value)
    {
        if (head == null) return createNewHead(value);

        SingleLinkedListNode<T> oldHead = Head;
        SingleLinkedListNode<T> newNode = new SingleLinkedListNode<T>(value, oldHead);
        head = newNode;
        return newNode;
    }

    public SingleLinkedListNode<T> InsertBefore(T value, SingleLinkedListNode<T> toInsertBefore)
    {
        if (head == null) throw new InvalidOperationException("you cannot insert on an empty list.");
        if (head == toInsertBefore) return InsertAtHead(value);

        SingleLinkedListNode<T> nodeBefore = findNodeBefore(toInsertBefore);
        SingleLinkedListNode<T> toInsert = new SingleLinkedListNode<T>(value, toInsertBefore);
        nodeBefore.Next = toInsert;
        return toInsert;
    }

    public SingleLinkedListNode<T> AppendAfter(T value, SingleLinkedListNode<T> toAppendAfter)
    {
        SingleLinkedListNode<T> newNode = new SingleLinkedListNode<T>(value, toAppendAfter.Next);
        toAppendAfter.Next = newNode;
        return newNode;
    }

    public void TruncateBefore(SingleLinkedListNode<T> toTruncateBefore)
    {
        if (head == toTruncateBefore)
        {
            head = null;
            tail = null;
            return;
        }

        SingleLinkedListNode<T> nodeBefore = findNodeBefore(toTruncateBefore);
        if (nodeBefore != null) nodeBefore.Next = null;
    }

    public void TruncateAfter(SingleLinkedListNode<T> toTruncateAfter)
    {
        toTruncateAfter.Next = null;
    }

    private SingleLinkedListNode<T> createNewHead(T value)
    {
        SingleLinkedListNode<T> newNode = new SingleLinkedListNode<T>(value, null);
        head = newNode;
        tail = newNode;
        return newNode;
    }

    private SingleLinkedListNode<T> findTail()
    {
        if (head == null) return null;
        SingleLinkedListNode<T> current = head;
        while (current.Next != null)
        {
            current = current.Next;
        }
        return current;
    }

    private SingleLinkedListNode<T> findNodeBefore(SingleLinkedListNode<T> nodeToFindNodeBefore)
    {
        SingleLinkedListNode<T> current = head;
        while (current != null)
        {
            if (current.Next != null && current.Next == nodeToFindNodeBefore) return current;
            current = current.Next;
        }
        return null;
    }
}

现在你可以做到这一点：

public static void Main(string[] args)
{
    SingleLinkedList<string> list = new SingleLinkedList<string>();
    list.InsertAtHead("state4");
    list.AddToTail("state3");
    list.AddToTail("state2");
    list.AddToTail("state1");

    SingleLinkedListNode<string> current = null;
    foreach (SingleLinkedListNode<string> node in list.Nodes)
    {
        if (node.Value != "state2") continue;

        current = node;
        break;
    }

    if (current != null) list.TruncateAfter(current);
}

事实上，根据你的情况，这并没有比这更好：

public static void Main(string[] args)
{
    SingleLinkedListNode<string> first =
        new SingleLinkedListNode<string>("state4");
    first.Next = new SingleLinkedListNode<string>("state3");
    SingleLinkedListNode<string> current = first.Next;
    current.Next = new SingleLinkedListNode<string>("state2");
    current = current.Next;
    current.Next = new SingleLinkedListNode<string>("state1");

    current = first;
    while (current != null)
    {
        if (current.Value != "state2") continue;
        current.Next = null;
        current = current.Next;
        break;
    }
}

这样就不需要使用集合类了。

- Michael Meadows

Answer 4

或者，你可以这样做：

while (currentNode.Next != null)
    list.Remove(currentNode.Next);

实际上，链表是一种相当简单的数据结构，特别是在托管代码中实现（即：没有内存管理问题）。

以下是我编写的一个支持足够函数（即：YAGNI）以支持您的撤销/重做操作的链表：

public class LinkedListNode<T>
{
    public LinkedList<T> Parent { get; set; }
    public T Value { get; set; }
    public LinkedListNode<T> Next { get; set; }
    public LinkedListNode<T> Previous { get; set; }
}

public class LinkedList<T> : IEnumerable<T>
{
    public LinkedListNode<T> Last { get; private set; }

    public LinkedListNode<T> AddLast(T value)
    {
        Last = (Last == null)
            ? new LinkedListNode<T> { Previous = null }
            : Last.Next = new LinkedListNode<T> { Previous = Last };

        Last.Parent = this;
        Last.Value = value;
        Last.Next = null;

        return Last;
    }

    public void SevereAt(LinkedListNode<T> node)
    {
        if (node.Parent != this)
            throw new ArgumentException("Can't severe node that isn't from the same parent list.");

        node.Next.Previous = null;
        node.Next = null;
        Last = node;
    }

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

    public IEnumerator<T> GetEnumerator()
    {
        var walk = Last;

        while (walk != null) {
            yield return walk.Value;
            walk = walk.Previous;
        }
    }

}

然后您可以在代码中使用SevereAt方法，来“剪切”链表，非常简单易懂。

- chakrit

Answer 5

if(this.ptr != null && this.ObjectName != null)
{
    LinkedListNode<ObjectType> it = ObjectName.Last;
                for (; it != this.ptr; it = it.Previous) 
                {
                    this.m_ObjectName.Remove(it);
                }
}

this.ptr 的类型是 LinkedListNode<ObjectType>，只是提供一下信息。

this.ptr 是一个指向当前节点的指针，我假设你想删除它右边的所有内容。

不要制作一个结构的新副本，这是最糟糕的想法。它会占用大量内存，并且结构可能非常大。除非绝对必要，否则复制对象不是良好的编程习惯。尽量使用原地操作。

- user1043000

Answer 6

我已经编写了两个扩展方法，用于“删除特定节点之前的所有节点”和“删除特定节点之后的所有节点”。但是，这些扩展方法是 LinkedListNode 的扩展，而不是 LinkedList 本身的扩展，只是为了方便：

public static class Extensions
{
    public static void RemoveAllBefore<T>(this LinkedListNode<T> node)
    {
        while (node.Previous != null) node.List.Remove(node.Previous);
    }

    public static void RemoveAllAfter<T>(this LinkedListNode<T> node)
    {
        while (node.Next != null) node.List.Remove(node.Previous);
    }
}

使用示例：

void Main()
{
    //create linked list and fill it up with some values

    LinkedList<int> list = new LinkedList<int>();
    for(int i=0;i<10;i++) list.AddLast(i);

    //pick some node from the list (here it is node with value 3)

    LinkedListNode<int> node = list.First.Next.Next.Next;

    //now for the trick

    node.RemoveAllBefore();

    //or

    node.RemoveAllAfter();
}

嗯，这不是最有效的方法，如果你发现自己在大型列表上或经常调用此方法，则其他描述在此处的方法可能更适合（例如编写自己的链接列表类，允许按其他答案中所述进行拆分），但如果只是偶尔需要“在这里和那里删除节点”，那么这很简单且相当直观。

- Juraj Maciak

Answer 7

第一个想法是将Node.Next.Previous = null设置为null（如果它是双向链表），然后将Node.Next = null。

不幸的是，在.NET实现的Linked List中，LinkedListNode<T>.Next和LinkedListNode<T>.Previous是只读属性，因此我认为您可能需要自己实现结构来实现此功能。

但正如其他人所说，这应该很容易。如果您只是搜索“linked lists C#”，就可以找到很多可以用作起点的资源。

- El Cristoir

Answer 8

在我的游戏程序中，我正在使用一个链表来跟踪所有回合的棋盘位置。为了在列表中插入新的位置并删除其后的所有节点，我使用了以下代码...

    //  ################
//
//  ADD HISTORY NODE
//
//  ################
//
//  IF REPLAY NODE NOT LAST NODE 
//
//      REMOVE ALL NODES AFTER REPLAY NODE
//      
//  ADD HISTORY NODE TO END
//
public void addHistoryNode()
{
    while (replay_node != positions.Last)
    {
        positions.RemoveLast();
    }

    positions.AddLast(getLivePosition());

    replay_node = positions.Last;
}

- Mark Steere