C＃ – LinkedList – 如何删除指定节点后的所有节点？
我正在实现一个带有通用LinkedList的undo / redo缓冲区。
在这种状态下：
[最佳]
state4（撤消）
state3（撤消）
state2 < – 当前状态
状态1
[底部]
当我执行Push时，我想删除当前状态之后的所有状态，然后推送新状态。
我当前的旁路是while (currentState != list.last), list.removeLast(); 但它很糟糕
LinkedList只支持Remove，RemoveFirst和removeLast ……
我想要像RemoveAllNodesAfter（LinkedListNode …）这样的东西？
如何在不迭代所有节点的情况下很好地编码？ 也许有扩展？…
我在标准LinkedList中看不到任何可以让你这样做的东西。 如果需要，您可以查看PowerCollections和C5集合 – 或者只是滚动您自己的LinkedList类型。 它是要实现的更简单的集合之一，特别是如果您可以“及时”方式添加function。
如果我自己实现这个，我会选择一种不同的方式来实现它。
而不是.RemoveAllNodesAfter(node)方法，我会选择创建一个.SplitAfter(node)方法，该方法从节点后的下一个节点开始返回一个新的链表。 这将成为一种更方便的工具，而不仅仅是能够切断尾部。 如果你想要你的RemoveAllNodesAfter方法，它只需要在内部调用SplitAfter方法并丢弃结果。
天真的实施：
public LinkedList SplitAfter(Node node) { Node nextNode = node.Next; // break the chain node.Next = null; nextNode.Previous = null; return new LinkedList (nextNode); } public void RemoveAllNodesAfter(Node node) { SplitAfter(node); }
链表（特别是单链表）是最基本的基本收集结构之一。 我确信您可以轻松实现它（并添加您需要的行为）。
实际上，您实际上并不需要集合类来管理列表。 您可以在没有集合类的情况下管理节点。
public class SingleLinkedListNode { private readonly T value; private SingleLinkedListNode next; public SingleLinkedListNode(T value, SingleLinkedListNode next) { this.value = value; } public SingleLinkedListNode(T value, SingleLinkedListNode next) : this(value) { this.next = next; } public SingleLinkedListNode Next { get { return next; } set { next = value; } } public T Value { get { return value; } } }
但是，如果您对可能的实现感兴趣，这里有一个简单的SingleLinkedList实现。
public class SingleLinkedList { private SingleLinkedListNode head; private SingleLinkedListNode tail; public SingleLinkedListNode Head { get { return head; } set { head = value; } } public IEnumerable> Nodes { get { SingleLinkedListNode current = head; while (current != null) { yield return current; current = current.Next; } } } public SingleLinkedListNode AddToTail(T value) { if (head == null) return createNewHead(value); if (tail == null) tail = findTail(); SingleLinkedListNode newNode = new SingleLinkedListNode (value, null); tail.Next = newNode; return newNode; } public SingleLinkedListNode InsertAtHead(T value) { if (head == null) return createNewHead(value); SingleLinkedListNode oldHead = Head; SingleLinkedListNode newNode = new SingleLinkedListNode (value, oldHead); head = newNode; return newNode; } public SingleLinkedListNode InsertBefore(T value, SingleLinkedListNode toInsertBefore) { if (head == null) throw new InvalidOperationException("you cannot insert on an empty list."); if (head == toInsertBefore) return InsertAtHead(value); SingleLinkedListNode nodeBefore = findNodeBefore(toInsertBefore); SingleLinkedListNode toInsert = new SingleLinkedListNode (value, toInsertBefore); nodeBefore.Next = toInsert; return toInsert; } public SingleLinkedListNode AppendAfter(T value, SingleLinkedListNode toAppendAfter) { SingleLinkedListNode newNode = new SingleLinkedListNode (value, toAppendAfter.Next); toAppendAfter.Next = newNode; return newNode; } public void TruncateBefore(SingleLinkedListNode toTruncateBefore) { if (head == toTruncateBefore) { head = null; tail = null; return; } SingleLinkedListNode nodeBefore = findNodeBefore(toTruncateBefore); if (nodeBefore != null) nodeBefore.Next = null; } public void TruncateAfter(SingleLinkedListNode toTruncateAfter) { toTruncateAfter.Next = null; } private SingleLinkedListNode createNewHead(T value) { SingleLinkedListNode newNode = new SingleLinkedListNode (value, null); head = newNode; tail = newNode; return newNode; } private SingleLinkedListNode findTail() { if (head == null) return null; SingleLinkedListNode current = head; while (current.Next != null) { current = current.Next; } return current; } private SingleLinkedListNode findNodeBefore(SingleLinkedListNode nodeToFindNodeBefore) { SingleLinkedListNode 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 list = new SingleLinkedList (); list.InsertAtHead("state4"); list.AddToTail("state3"); list.AddToTail("state2"); list.AddToTail("state1"); SingleLinkedListNode current = null; foreach (SingleLinkedListNode 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 first = new SingleLinkedListNode ("state4"); first.Next = new SingleLinkedListNode ("state3"); SingleLinkedListNode current = first.Next; current.Next = new SingleLinkedListNode ("state2"); current = current.Next; current.Next = new SingleLinkedListNode ("state1"); current = first; while (current != null) { if (current.Value != "state2") continue; current.Next = null; current = current.Next; break; } }
这完全消除了对集合类的需要。
或者，您可以这样做：
while (currentNode.Next != null) list.Remove(currentNode.Next);
实际上，链表是一个相当简单的数据结构，特别是在托管代码中实现（读：没有内存管理麻烦）。
这是我支持的一个支持足够的function（读取： YAGNI ）来支持你的撤销/重做操作：
public class LinkedListNode { public LinkedList Parent { get; set; } public T Value { get; set; } public LinkedListNode Next { get; set; } public LinkedListNode Previous { get; set; } } public class LinkedList : IEnumerable { public LinkedListNode Last { get; private set; } public LinkedListNode AddLast(T value) { Last = (Last == null) ? new LinkedListNode { Previous = null } : Last.Next = new LinkedListNode { Previous = Last }; Last.Parent = this; Last.Value = value; Last.Next = null; return Last; } public void SevereAt(LinkedListNode 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 )this).GetEnumerator(); } public IEnumerator GetEnumerator() { var walk = Last; while (walk != null) { yield return walk.Value; walk = walk.Previous; } } }
然后，您可以在代码中使用SevereAt方法来“剪切”链接列表，简单明了。
想到的第一个想法是设置Node.Next.Previous = null （如果它是一个双向链表），然后Node.Next = null 。
不幸的是，因为LinkedListNode和LinkedListNode是Linked List的.NET实现中的只读属性，我认为您可能必须实现自己的结构才能实现此function。
但正如其他人所说，这应该很容易。 如果您只是谷歌的链接列表C＃ ，您可以使用大量资源作为起点。
if(this.ptr != null && this.ObjectName != null) { LinkedListNode it = ObjectName.Last; for (; it != this.ptr; it = it.Previous) { this.m_ObjectName.Remove(it); } }
this.ptr的类型为LinkedListNode只是fyi
this.ptr是指向您当前所在节点的指针，我假设您要删除它右侧的所有内容。
不要制作你的结构的新副本，这是有史以来最糟糕的想法。 这是一个完整的记忆猪，结构可能非常大。 除非绝对必要，否则复制Object并不是一种好的编程习惯。 尝试进行就地操作。
我已经为“删除特定节点之前的所有节点”和“删除特定节点之后的所有节点”制作了两种扩展方法。 但是，这些扩展方法是LinkedListNode的扩展，而不是LinkedList本身，只是为了方便起见：
public static class Extensions { public static void RemoveAllBefore(this LinkedListNode node) { while (node.Previous != null) node.List.Remove(node.Previous); } public static void RemoveAllAfter (this LinkedListNode node) { while (node.Next != null) node.List.Remove(node.Previous); } }
使用示例：
void Main() { //create linked list and fill it up with some values LinkedList list = new LinkedList (); for(int i=0;i<10;i++) list.AddLast(i); //pick some node from the list (here it is node with value 3) LinkedListNode node = list.First.Next.Next.Next; //now for the trick node.RemoveAllBefore(); //or node.RemoveAllAfter(); }
嗯，这不是最有效的方法，如果你发现自己在大型列表上或经常调用此方法，那么这里描述的其他方法可能更合适（比如编写自己的链表类，允许按照其他答案中的描述进行拆分）但是如果它只是偶尔“在这里和那里删除节点”比这简单而且非常直观。