我正在實現一個具有通用LinkedList的撤銷/重做緩衝區。C＃ - LinkedList - 如何刪除指定節點後的所有節點？
在該狀態下：
[頂端]
state4（撤消）
STATE3（撤消）
STATE2 < - 當前狀態
STATE1
[底部]
當我做一個推，我想刪除當前之後的所有狀態，並推新的狀態。
我的電流旁路是做while (currentState != list.last), list.removeLast();但它吮吸
的LinkedList只是支持刪除，RemoveFirst & removeLast ...
我想是這樣RemoveAllNodesAfter（一個LinkedListNode ...）？
我怎樣才能很好地編寫代碼，而無需迭代所有節點？也許有擴展名？...
我看不到任何東西在標準LinkedList<T>，它可以讓你這樣做。如果需要，您可以查看PowerCollections和C5 collections - 或者只是推出自己的LinkedList類型。這是實現更簡單的集合之一，特別是如果您可以以「及時」方式添加功能。
鏈表（特別是單鏈表）是最基本的基本集合結構之一。我確信你可以很輕鬆地實現它（並且添加你需要的行爲）。
實際上，您實際上並不需要收集類來管理列表。您可以管理沒有集合類的節點。
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;
}
}
這消除了對集合類的需求共。
如果我自己實現這一點，我會選擇一種不同的方式來實現這一點。
而不是.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);
}
是彈簧想到的第一個想法是設置Node.Next.Previous = null（如果它是一個雙向鏈表），然後Node.Next = null。
不幸的是，因爲LinkedListNode<T>.Next和LinkedListNode<T>.Previous是鏈接列表的.NET實現中的只讀屬性，我認爲您可能必須實現自己的結構來實現此功能。
但正如其他人所說，這應該很容易。如果您只是Google的鏈接列表C＃，您可以使用大量資源作爲起點。
或者，你可以這樣做：
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方法在代碼中「切割」鏈接列表很好，很簡單。
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是一個指針指向你是在目前，我假設你要刪除一切，它的右側的節點。
不要製作你的結構的新副本，它是有史以來最糟糕的想法。這是一個完整的記憶豬，結構可能非常大。除非絕對必要，否則複製對象不是很好的編程習慣。嘗試做就地操作。
我做了兩個擴展方法，用於「在特定節點之前移除所有節點」和「在特定節點之後移除所有節點」。然而，這些擴展方法是一個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();
}
那麼它是不是最有效的方法，如果你發現自己在調用此方法在大列表上或經常，然後其他這裏描述的方法可能更適合（如編寫自己的鏈接列表類允許分裂，如其他答案中所述），但如果它只是偶爾「刪除節點在這裏和那裏」比這是簡單而直觀。
感謝您的回答，但Next和Previous是隻讀的。 – rockeye 2009-02-24 15:54:43