C# 中的泛型单链表及基本和高级自定义操作

• 下载源代码 - 3.91 KB

引言

本文档介绍了 C# 中通用单链表的自定义实现，以及对该列表进行基础和高级操作，并附带了优化算法。

背景

作为 .NET 程序员，我们一直可以方便地使用现成的 .NET Framework 类库 (FCL) 中的数据结构，例如 LinkedList<T>、Queue<T>、SortedDictionary<T Key, T Value>、Stack<T> 等等。但在许多编程面试中，通常期望我们能够先实现某种数据结构及其所有基础操作，然后是高级操作，最后再优化其时间和空间复杂度。在此，我尝试实现了一个通用的 LinkedList ，包含基础和高级操作，揭示了这种非常流行且需求很高的数据结构底层的算法。基础操作包括在列表的头部和尾部添加元素，在列表的头部和尾部删除元素，在指定索引处添加和删除元素，搜索和更新元素，显示和清空列表内容等；高级操作则包括查找中间元素，判断列表是否包含循环/环等。

Using the Code

我为本次演示编写了三个类：

1. 类 TestLinkedList - 这是我的单链表实现的测试类。代码包含在 ZIP 文件中（它包含 Main 方法，通过一个简单的基于控制台的用户界面来测试列表的所有操作。没什么特别的！）。
2. 类 ListNode<T> - 通用列表节点类。请注意，通过实现一个通用节点类，我避免了装箱/拆箱的开销，并提高了实用性和可重用性。
   我们的 ListNode<T> 类是一个泛型类，这意味着它可以包含任何数据类型的节点。它有两个字段：一个 'item' 字段，类型为 T，用于存储节点的数据；另一个 'next' 字段，类型为 ListNode<T>，它只是一个指向列表中下一个节点的指针。然后，我们有一个构造函数，用于初始化带有数据的节点，该构造函数内部调用另一个构造函数，该构造函数使用数据和指向下一个节点的指针来初始化节点。如果列表为空，则节点将被初始化为第一个节点（通常称为 'first' 或 'head'），其数据和指向下一个节点的指针都为 null （标志着列表的结束）。我在这里重写了 ToString() 方法，以便于理解和调试，因为我们关心的是存储在节点中的数据。我重写的实现将简单地以字符串格式返回节点的值。请看下面的代码。

/// <summary>
/// Generic ListNode class - avoiding boxing unboxing here by using generic implementation
/// </summary>
/// <typeparam name="T"></typeparam>

public class ListNode<T>
{
	private ListNode<T> next;
	private T item;
	/// <summary>
	/// Property to hold pointer to next ListNode - Self containing object
	/// </summary>

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

	/// <summary>
	/// Property to hold value into the Node
	/// </summary>

	public T Item
	{
		get { return item; }
		set { item = value; }
	}

	/// <summary>
	/// Constructor with item init
	/// </summary>
	/// <param name="item"></param>

	public ListNode(T item)
	: this(item,null)
	{
	}

	/// <summary>
	/// Constructor with item and the next node specified
	/// </summary>
	/// <param name="item"></param>
	/// <param name="next"></param>

	public ListNode(T item, ListNode<T> next)
	{
		this.item = item;
		this.next = next;
	}

	/// <summary>
	/// Overriding ToString to return a string value for the item in the node
	/// </summary>
	/// <returns></returns>

	public override string ToString()
	{
		if (item == null)
			return string.Empty;
		return item.ToString();
	}
}

类 SinglyLinkedList<T>:ICollection<T>

首先，我们创建了一个实现了 ICollection 接口的通用 SinglyLinkedList<T> 类，以便我们可以遍历列表项，并提供一个实现支持操作的框架，如 remove、add、Contains、GetEnumerator、Sort 等。

让我们更深入地了解这个类。我们有一个类型为 String 的字段 'strListName'，用于指定列表的名称。出于测试目的，我将其硬编码为 'MyList'。这是个糟糕的做法，不是吗？不管怎样，有两个类型为 ListNode<T> 的字段 'firstNode' 和 'lastNode'，用于指向列表的起始节点和结束节点（显而易见的原因是便于进行各种操作的顺序遍历），还有一个变量 'count'，用于跟踪列表的长度，简而言之，就是列表中的元素数量。对于每一次 add 操作，count 会增加 1；对于每一次 remove 操作，count 会减少 1。有一个布尔属性 'IsEmpty'，如果列表不包含任何元素，则返回 true，否则返回 false。我还为 LinkedList 类添加了一个索引器，用于获取指定索引处的项。由于这是一个单链表，我们没有前一个节点的指针。我们有两个构造函数，可以根据提供的名称或默认名称来初始化我们的列表，并将第一个和最后一个节点设置为 null （初始化一个空列表）。请看下面的代码。

/// <summary>
/// SinglyLinkedList class for generic implementation of LinkedList. 
/// Again, avoiding boxing unboxing here and using ICollection interface members. 
/// Believe this can be useful when applying other 
/// operations such as sorting, searching etc. 
/// </summary>
/// <typeparam name="T"></typeparam>

public class SinglyLinkedList<T>:ICollection<T>
{
	#region private variables
	private string strListName;
	private ListNode<T> firstNode;
	private ListNode<T> lastNode;
	private int count;
	#endregion

	/// <summary>
	/// Property to hold first node in the list
	/// </summary>

	public ListNode<T> FirstNode
	{
		get { return firstNode; }
	}

	/// <summary>
	/// Property to hold last node in the list
	/// </summary>

	public ListNode<T> LastNode
	{
		get { return lastNode; }
	}

	/// <summary>
	/// Indexer to iterate through the list and fetch the item
	/// </summary>
	/// <param name="index"></param>
	/// <returns></returns>

	public T this[int index]
	{
		get 
		{
			if (index < 0)
				throw new ArgumentOutOfRangeException();
			ListNode<T> currentNode = firstNode;
			for (int i = 0; i < index; i++)
			{
				if (currentNode.Next == null)
					throw new ArgumentOutOfRangeException();
				currentNode = currentNode.Next;
			}
		return currentNode.Item;
		}
	}

	/// <summary>
	/// Property to hold count of items in the list
	/// </summary>

	public int Count
	{
		get { return count; }
	}

	/// <summary>
	/// Property to determine if the list is empty or contains any item
	/// </summary>

	public bool IsEmpty
	{
		get 
		{
			lock (this)
			{
				return firstNode == null;
			}
		}
	}

	/// <summary>
	/// Constructor initializing list with a provided list name
	/// </summary>
	/// <param name="strListName"></param>

	public SinglyLinkedList(string strListName)
	{
		this.strListName = strListName;
		count = 0;
		firstNode = lastNode = null;
	}

	/// <summary>
	/// default constructor initializing list with a default name 'MyList'
	/// </summary>

	public SinglyLinkedList() : this("MyList") { }
	/// <summary>
	/// Operation ToString overridden to get the contents from the list
	/// </summary>
	/// <returns></returns>

	public override string ToString()
	{
		if (IsEmpty)
			return string.Empty;
		StringBuilder returnString = new StringBuilder();
		foreach (T item in this)
		{
			if (returnString.Length > 0)
				returnString.Append("->");
			returnString.Append(item);
		}
		return returnString.ToString();
	}

接下来，我们来看一下可以在单链表上执行的基础操作，例如在列表头部添加一个项，在列表尾部添加一个项，从列表头部删除一个项，从列表尾部删除一个项，搜索和更新一个项，获取列表的长度，在特定索引处插入，从特定索引处删除等等。基本上，顺序遍历列表涉及将指针设置为第一个节点，并遍历列表直到指针指向 null 节点（标志着列表的结束）。向列表中添加一个节点涉及创建一个带有值的节点，并将其插入到列表的头部、尾部或指定索引处，然后调整新添加节点（如果不是列表的第一个节点）的 'next' 指针，并相应地递增计数器。删除操作更简单。通过将前一个节点的指针设置为下一个节点的指针来销毁要删除的节点，并将计数器减 1。如果要删除的节点是第一个节点，则将指针重置为下一个元素；如果要删除的是最后一个节点，则遍历列表并将最后一个节点重置为前一个节点，并将下一个指针设置为 null。清空列表非常简单。只需将起始节点和结束节点设置为 null ，并将计数器重置为 0。Find 和 Update 操作涉及遍历列表，将输入项与当前确定节点中包含的项进行匹配，然后执行操作。

以下代码示例说明了这些操作的实现：

/// <summary>
/// Operation inserts item at the front of the list
/// </summary>
/// <param name="item"></param>

public void InsertAtFront(T item)
{
	lock (this)
	{
		if (IsEmpty)
			firstNode = lastNode = new ListNode<T>(item);
		else
			firstNode = new ListNode<T>(item, firstNode);
		count++;
	}
}

/// <summary>
/// Operation inserts item at the back of the list
/// </summary>
/// <param name="item"></param>

public void InsertAtBack(T item)
{
	lock (this)
	{
		if (IsEmpty)
			firstNode = lastNode = new ListNode<T>(item);
		else
			lastNode = lastNode.Next = new ListNode<T>(item);
		count++;
	}
}

/// <summary>
/// Operation removes item from the front of the list
/// </summary>
/// <returns></returns>

public object RemoveFromFront()
{
	lock (this)
	{
		if (IsEmpty)
			throw new ApplicationException("list is empty");
		object removedData = firstNode.Item;
		if (firstNode == lastNode)
			firstNode = lastNode = null;
		else
			firstNode = firstNode.Next;
		count--;
		return removedData;
	}
}

/// <summary>
/// Operation removes item from the back of the list
/// </summary>
/// <returns></returns>

public object RemoveFromBack()
{
	lock (this)
	{
		if (IsEmpty)
			throw new ApplicationException("list is empty");
		object removedData = lastNode.Item;
		if (firstNode == lastNode)
			firstNode = lastNode = null;
		else
		{
			ListNode<T> currentNode = firstNode;
			while (currentNode.Next != lastNode)
				currentNode = currentNode.Next;
			lastNode = currentNode;
			currentNode.Next = null;
		}
		count--;
		return removedData;
	}
}

/// <summary>
/// Operation inserts item at the specified index in the list
/// </summary>
/// <param name="index"></param>
/// <param name="item"></param>

public void InsertAt(int index, T item)
{
	lock (this)
	{
		if (index > count || index < 0)
			throw new ArgumentOutOfRangeException();
		if (index == 0)
			InsertAtFront(item);
		else if (index == (count - 1))
			InsertAtBack(item);
		else
		{
			ListNode<T> currentNode = firstNode;
			for (int i = 0; i < index - 1; i++)
			{
				currentNode = currentNode.Next;
			}
			ListNode<T> newNode = new ListNode<T>(item, currentNode.Next);
			currentNode.Next = newNode;
			count++;
		}
	}
}

/// <summary>
/// Operation removes item from the specified index in the list
/// </summary>
/// <param name="index"></param>
/// <returns></returns>

public object RemoveAt(int index)
{
	lock (this)
	{
		if (index > count || index < 0)
			throw new ArgumentOutOfRangeException();
		object removedData;
		if (index == 0)
			removedData = RemoveFromFront();
		else if (index == (count - 1))
			removedData = RemoveFromBack();
		else
		{
			ListNode<T> currentNode = firstNode;
			for (int i = 0; i < index; i++)
			{
				currentNode = currentNode.Next;
			}
			removedData = currentNode.Item;
			currentNode.Next = currentNode.Next.Next;
			count--;
		}
		return removedData;
	}
}

/// <summary>
/// Removes the input item if exists and returns true else false
/// </summary>
/// <param name="item"></param>
/// <returns></returns>

public bool Remove(T item)
{
	if (firstNode.Item.ToString().Equals(item.ToString()))
	{
		RemoveFromFront();
		return true;
	}
	else if (lastNode.Item.ToString().Equals(item.ToString()))
	{
		RemoveFromBack();
		return true;
	}
	else
	{
		ListNode<T> currentNode = firstNode;
		while (currentNode.Next != null)
		{
			if (currentNode.Next.Item.ToString().Equals(item.ToString()))
			{
				currentNode.Next = currentNode.Next.Next;
				count--;
				if (currentNode.Next == null)
					lastNode = currentNode;
				return true;
			}
			currentNode = currentNode.Next;
		}
	}
	return false;
}


/// <summary>
/// Operation updates an item provided as an input with a new item 
/// (also provided as an input)
/// </summary>
/// <param name="oldItem"></param>
/// <param name="newItem"></param>
/// <returns></returns>

public bool Update(T oldItem, T newItem)
{
	lock (this)
	{
		ListNode<T> currentNode = firstNode;
		while (currentNode != null)
		{
			if (currentNode.ToString().Equals(oldItem.ToString()))
			{
				currentNode.Item = newItem;
				return true;
			}
			currentNode = currentNode.Next;
		}
		return false;
	}
}

/// <summary>
/// Returns true if list contains the input item else false
/// </summary>
/// <param name="item"></param>
/// <returns></returns>

public bool Contains(T item)
{
	lock (this)
	{
		ListNode<T> currentNode = firstNode;
		while (currentNode != null)
		{
			if (currentNode.Item.ToString().Equals(item.ToString()))
			{
				return true;
			}
			currentNode = currentNode.Next;
		}
		return false;
	}
}

/// <summary>
/// Operation resets the list and clears all its contents
/// </summary>

public void Clear()
{
	firstNode = lastNode = null;
	count = 0;
}

现在，链表中最重要的操作来了，你的代码可以在此真正区分一个开发者和一个优秀的开发者，后者可以通过彻底优化算法来进一步提升代码性能。下面，下面的代码说明了如何反转一个 linkedlist，如何查找列表的中间元素，以及如何判断列表是否包含循环，请注意，我们需要在实现这些操作时牢记时间和空间效率（还记得大 O 符号吗？？）。

反转列表涉及简单的交换算法，我们将 lastnode 初始设置为 firstnode。我们还有一个额外的 ListNode<T> 元素，它有效地充当 previousNode 指针（用于交换），以及一个 currentNode 指针，它逐个遍历列表，与 previousNode 进行交换。最后，我们将 firstNode 设置为 currentNode ，从而以 O(n) 的时间复杂度完成反转操作。

查找循环可能很棘手，因为一旦你的列表中存在一个循环，并尝试通过蛮力方法来查找它，即遍历列表直到结束，这将永远无法成功，因为循环会无限进行。这里的关键是使用一个慢指针和一个快指针。快指针的移动速度是慢指针的两倍，如果在任何阶段，快指针与慢指针重叠，则表明存在一个循环。

查找列表的中间点使用相同的原理。快指针到达列表末尾所需的时间是慢指针的一半，因此当快指针到达末尾时，慢指针将指向列表的中间。如果列表存在循环，则返回 null ，因为在循环中不存在中间点。

/// <summary>
/// Operation to reverse the contents of the linked list 
/// by resetting the pointers and swapping the contents
/// </summary>

public void Reverse()
{
	if (firstNode == null || firstNode.Next == null)
		return;
	lastNode = firstNode;
	ListNode<T> prevNode = null;
	ListNode<T> currentNode = firstNode;
	ListNode<T> nextNode = firstNode.Next;

	while (currentNode != null)
	{
		currentNode.Next = prevNode;
		if (nextNode == null)
			break;
		prevNode = currentNode;
		currentNode = nextNode;
		nextNode = nextNode.Next;
	}
	firstNode = currentNode;
}

/// <summary>
/// Operation to find if the linked list contains a circular loop
/// </summary>
/// <returns></returns>

public bool HasCycle()
{
	ListNode<T> currentNode = firstNode;
	ListNode<T> iteratorNode = firstNode;
	for (; iteratorNode != null && iteratorNode.Next != null; 
		iteratorNode = iteratorNode.Next )
	{
		if (currentNode.Next == null || 
			currentNode.Next.Next == null) return false;
		if (currentNode.Next == iteratorNode || 
			currentNode.Next.Next == iteratorNode) return true;
		currentNode = currentNode.Next.Next;
	}
	return false;
}

/// <summary>
/// Operation to find the midpoint of a list 
/// </summary>
/// <returns></returns>

public ListNode<T> GetMiddleItem()
{
	ListNode<T> currentNode = firstNode;
	ListNode<T> iteratorNode = firstNode;
	for (; iteratorNode != null && iteratorNode.Next != null; 
		iteratorNode = iteratorNode.Next)
	{
		if (currentNode.Next == null || 
			currentNode.Next.Next == null) return iteratorNode;
		if (currentNode.Next == iteratorNode || 
			currentNode.Next.Next == iteratorNode) return null;
		currentNode = currentNode.Next.Next;
	}
	return firstNode;
}

接口 IEnumerable<T> 成员

#region IEnumerable<T> Members
/// <summary>
/// Custom GetEnumerator method to traverse through the list and 
/// yield the current value
/// </summary>
/// <returns></returns>

 public IEnumerator<T> GetEnumerator()
 {
	ListNode<T> currentNode = firstNode;
	while (currentNode != null)
	{
		yield return currentNode.Item;
		currentNode = currentNode.Next;
	}
}

#endregion

#region IEnumerable Members
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
	return GetEnumerator();
}

#endregion

万一你想知道如何在程序中创建我们 linkedlist 的循环，这里有个技巧！

/// <summary>
/// Operation creates a circular loop in the linked list for testing purpose. 
/// Once this loop is created, other operations would probably fail.
/// </summary>

public void CreateCycleInListToTest()
{
	ListNode<T> currentNode = firstNode;
	ListNode<T> midNode = GetMiddleItem();
	lastNode.Next = midNode;
}

感谢您的阅读。希望它对您关于数据结构操作和 C# 编程的现有知识有所帮助和增值！