基本概念
LinkedList 是一种链式存储结构，它由一系列节点（Node）组成，每个节点包含数据和指向下一个节点的指针。链表中的节点不需要连续存储，每个节点通过指针（引用）连接在一起。
用途
LinkedList 常用于以下情况：
动态数据管理：适用于数据量不固定，经常需要插入和删除操作的情况。
队列和栈：可以用链表实现队列（FIFO）和栈（LIFO）结构。
图和树：链表可以用于实现图和树的邻接表等。
在游戏开发中的用途
在游戏开发中，LinkedList 也有很多实际应用：
管理游戏对象：如敌人列表、任务列表，方便动态增加和删除对象。
事件队列：处理游戏中的事件队列，按顺序处理事件。
路径存储：存储路径点（如寻路算法中的路径），方便动态调整路径。
语法规则及声明
在 C# 中，LinkedList 位于 System.Collections.Generic 命名空间下。我们可以使用 LinkedList<T> 来声明一个链表，其中 T 表示链表中存储的元素类型。
using System.Collections.Generic;
LinkedList<int> numbers = new LinkedList<int>();
LinkedList<string> names = new LinkedList<string>();
常用方法
AddFirst(T value)：在链表开头添加一个元素。AddLast(T value)：在链表末尾添加一个元素。Remove(T value)：移除链表中的指定元素。RemoveFirst()：移除链表中的第一个元素。RemoveLast()：移除链表中的最后一个元素。Find(T value)：查找链表中指定值的节点。Count：获取链表中元素的数量。Clear()：清空链表中的所有元素。
示例代码及解释
示例1：基本操作
using System;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
LinkedList<int> numbers = new LinkedList<int>();
// 在链表末尾添加元素
numbers.AddLast(1);
numbers.AddLast(2);
numbers.AddLast(3);
// 在链表开头添加元素
numbers.AddFirst(0);
// 输出链表中的所有元素
foreach (int number in numbers)
{
Console.WriteLine(number);
}
// 查找并移除元素
LinkedListNode<int> node = numbers.Find(2);
if (node != null)
{
numbers.Remove(node);
}
Console.WriteLine("After removing 2:");
// 再次输出链表中的所有元素
foreach (int number in numbers)
{
Console.WriteLine(number);
}
}
}
using System;
using System.Text;
using System.Collections.Generic;
public class Example
{
public static void Main()
{
// Create the link list.
string[] words =
{ "the", "fox", "jumps", "over", "the", "dog" };
LinkedList<string> sentence = new LinkedList<string>(words);
Display(sentence, "The linked list values:");
// Add the word 'today' to the beginning of the linked list.
sentence.AddFirst("today");
Display(sentence, "Test 1: Add 'today' to beginning of the list:");
// Move the first node to be the last node.
LinkedListNode<string> mark1 = sentence.First;
sentence.RemoveFirst();
sentence.AddLast(mark1);
Display(sentence, "Test 2: Move first node to be last node:");
// Change the last node to 'yesterday'.
sentence.RemoveLast();
sentence.AddLast("yesterday");
Display(sentence, "Test 3: Change the last node to 'yesterday':");
// Move the last node to be the first node.
mark1 = sentence.Last;
sentence.RemoveLast();
sentence.AddFirst(mark1);
Display(sentence, "Test 4: Move last node to be first node:");
// Indicate the last occurence of 'the'.
sentence.RemoveFirst();
LinkedListNode<string> current = sentence.FindLast("the");
IndicateNode(current, "Test 5: Indicate last occurence of 'the':");
// Add 'lazy' and 'old' after 'the' (the LinkedListNode named current).
sentence.AddAfter(current, "old");
sentence.AddAfter(current, "lazy");
IndicateNode(current, "Test 6: Add 'lazy' and 'old' after 'the':");
// Indicate 'fox' node.
current = sentence.Find("fox");
IndicateNode(current, "Test 7: Indicate the 'fox' node:");
// Add 'quick' and 'brown' before 'fox':
sentence.AddBefore(current, "quick");
sentence.AddBefore(current, "brown");
IndicateNode(current, "Test 8: Add 'quick' and 'brown' before 'fox':");
// Keep a reference to the current node, 'fox',
// and to the previous node in the list. Indicate the 'dog' node.
mark1 = current;
LinkedListNode<string> mark2 = current.Previous;
current = sentence.Find("dog");
IndicateNode(current, "Test 9: Indicate the 'dog' node:");
// The AddBefore method throws an InvalidOperationException
// if you try to add a node that already belongs to a list.
Console.WriteLine("Test 10: Throw exception by adding node (fox) already in the list:");
try
{
sentence.AddBefore(current, mark1);
}
catch (InvalidOperationException ex)
{
Console.WriteLine("Exception message: {0}", ex.Message);
}
Console.WriteLine();
// Remove the node referred to by mark1, and then add it
// before the node referred to by current.
// Indicate the node referred to by current.
sentence.Remove(mark1);
sentence.AddBefore(current, mark1);
IndicateNode(current, "Test 11: Move a referenced node (fox) before the current node (dog):");
// Remove the node referred to by current.
sentence.Remove(current);
IndicateNode(current, "Test 12: Remove current node (dog) and attempt to indicate it:");
// Add the node after the node referred to by mark2.
sentence.AddAfter(mark2, current);
IndicateNode(current, "Test 13: Add node removed in test 11 after a referenced node (brown):");
// The Remove method finds and removes the
// first node that that has the specified value.
sentence.Remove("old");
Display(sentence, "Test 14: Remove node that has the value 'old':");
// When the linked list is cast to ICollection(Of String),
// the Add method adds a node to the end of the list.
sentence.RemoveLast();
ICollection<string> icoll = sentence;
icoll.Add("rhinoceros");
Display(sentence, "Test 15: Remove last node, cast to ICollection, and add 'rhinoceros':");
Console.WriteLine("Test 16: Copy the list to an array:");
// Create an array with the same number of
// elements as the linked list.
string[] sArray = new string[sentence.Count];
sentence.CopyTo(sArray, 0);
foreach (string s in sArray)
{
Console.WriteLine(s);
}
Console.WriteLine("Test 17: linked list Contains 'jumps' = {0}",
sentence.Contains("jumps"));
// Release all the nodes.
sentence.Clear();
Console.WriteLine();
Console.WriteLine("Test 18: Cleared linked list Contains 'jumps' = {0}",
sentence.Contains("jumps"));
Console.ReadLine();
}
private static void Display(LinkedList<string> words, string test)
{
Console.WriteLine(test);
foreach (string word in words)
{
Console.Write(word + " ");
}
Console.WriteLine();
Console.WriteLine();
}
private static void IndicateNode(LinkedListNode<string> node, string test)
{
Console.WriteLine(test);
if (node.List == null)
{
Console.WriteLine("Node '{0}' is not in the list.\n",
node.Value);
return;
}
StringBuilder result = new StringBuilder("(" + node.Value + ")");
LinkedListNode<string> nodeP = node.Previous;
while (nodeP != null)
{
result.Insert(0, nodeP.Value + " ");
nodeP = nodeP.Previous;
}
node = node.Next;
while (node != null)
{
result.Append(" " + node.Value);
node = node.Next;
}
Console.WriteLine(result);
Console.WriteLine();
}
}
//This code example produces the following output:
//
//The linked list values:
//the fox jumps over the dog
//Test 1: Add 'today' to beginning of the list:
//today the fox jumps over the dog
//Test 2: Move first node to be last node:
//the fox jumps over the dog today
//Test 3: Change the last node to 'yesterday':
//the fox jumps over the dog yesterday
//Test 4: Move last node to be first node:
//yesterday the fox jumps over the dog
//Test 5: Indicate last occurence of 'the':
//the fox jumps over (the) dog
//Test 6: Add 'lazy' and 'old' after 'the':
//the fox jumps over (the) lazy old dog
//Test 7: Indicate the 'fox' node:
//the (fox) jumps over the lazy old dog
//Test 8: Add 'quick' and 'brown' before 'fox':
//the quick brown (fox) jumps over the lazy old dog
//Test 9: Indicate the 'dog' node:
//the quick brown fox jumps over the lazy old (dog)
//Test 10: Throw exception by adding node (fox) already in the list:
//Exception message: The LinkedList node belongs a LinkedList.
//Test 11: Move a referenced node (fox) before the current node (dog):
//the quick brown jumps over the lazy old fox (dog)
//Test 12: Remove current node (dog) and attempt to indicate it:
//Node 'dog' is not in the list.
//Test 13: Add node removed in test 11 after a referenced node (brown):
//the quick brown (dog) jumps over the lazy old fox
//Test 14: Remove node that has the value 'old':
//the quick brown dog jumps over the lazy fox
//Test 15: Remove last node, cast to ICollection, and add 'rhinoceros':
//the quick brown dog jumps over the lazy rhinoceros
//Test 16: Copy the list to an array:
//the
//quick
//brown
//dog
//jumps
//over
//the
//lazy
//rhinoceros
//Test 17: linked list Contains 'jumps'= True
//Test 18: Cleared linked list Contains 'jumps' = False
//示例2：在游戏开发中的应用
using System;
using System.Collections.Generic;
public class Enemy
{
public string Name { get; set; }
public int Health { get; set; }
public Enemy(string name, int health)
{
Name = name;
Health = health;
}
public void TakeDamage(int damage)
{
Health -= damage;
Console.WriteLine($"{Name} took {damage} damage, remaining health: {Health}");
}
}
public class Game
{
private LinkedList<Enemy> enemies;
public Game()
{
enemies = new LinkedList<Enemy>();
}
public void AddEnemy(Enemy enemy)
{
enemies.AddLast(enemy);
}
public void RemoveEnemy(Enemy enemy)
{
enemies.Remove(enemy);
}
public void UpdateEnemies()
{
foreach (var enemy in enemies)
{
enemy.TakeDamage(10);
}
}
}
public class Program
{
public static void Main()
{
Game game = new Game();
// 添加敌人
game.AddEnemy(new Enemy("Goblin", 100));
game.AddEnemy(new Enemy("Orc", 150));
// 更新敌人状态
game.UpdateEnemies();
// 移除一个敌人
Enemy orc = new Enemy("Orc", 150);
game.RemoveEnemy(orc);
}
}
优点和缺点
优点：
动态大小：链表可以根据需要动态调整大小。
高效插入/删除：插入和删除操作不需要移动大量元素，只需修改指针，时间复杂度为 O(1)。
内存利用率高：不需要连续的内存空间。
缺点：
访问效率低：不能通过索引快速访问元素，时间复杂度为 O(n)。
额外内存开销：每个节点需要存储额外的指针，增加内存开销。
复杂性：链表的实现和管理比数组更复杂。
基础题目和进阶题目
基础题目
创建一个
LinkedList<int>，添加 5 个整数，并输出所有元素。创建一个
LinkedList<string>，添加一些名字，然后输出所有名字。创建一个
LinkedList<int>，实现一个方法，计算并输出链表中所有元素的和。
进阶题目
创建一个
LinkedList<int>，实现一个方法，反转链表中的元素顺序。创建一个
LinkedList<int>，实现一个方法，从链表中删除所有偶数元素。实现一个双链表（
DoublyLinkedList），并实现插入、删除、查找等操作。实现一个循环链表（
CircularLinkedList），并实现插入、删除、查找等操作。