作者：乌龙哈里
时间：2015-11-04
平台：Window7 64bit,Visual Studio Community 2015
参考：
章节：
- 单向链表元素
- 定义单向链表操作接口
- 逐步实现单向链表
正文：
前面学习了 IEnumerable<T>、IComparable<T>、ICollection<T> 三个接口，就是为了学习数据结构编程使用。
一、单向链表元素
根据单向链表（Single Linked List）的定义，我们知道链表中的元素 Node 由 数据 和 下一个元素 NextNode 两部分组成。构建如下：
//=====单向链表元素=====
class Node<T>
{
public T Value;
public Node<T> NextNode;
}
该元素的创立应该有不带参数（）和带参数（T value） 两种形式，我们继续补全代码如下：
//=====单向链表元素=====
class Node<T>
{
public T Value;
public Node<T> NextNode;
public Node():this(default(T)){ }
public Node(T value)
{
Value = value;
NextNode = null;
}
}
不带参数的创立里面有 default(T)，参见 MSDN 泛型代码中的默认关键字（C# 编程指南）。
二、定义单向链表操作接口
有了元素 Node<T>后，我们要操作它，设想中的操作有 增加、删除、修改、清空、遍历、索引器等，我们看看接口 IColloction<T> 和 IList<T> 的约定，就知道我们要实现 IList<T>。
//======参考 IList<T>===
public interface IList<T> : ICollection<T>
{
T this[int index] {get;set;}
int IndexOf(T item);
void Insert(int index, T item);
void RemoveAt(int index);
}
//======参考 ICollection<T>===
public interface ICollection<T> : IEnumerable<T>
{
int Count { get; }
bool IsReadOnly { get; }
void Add(T item);
void Clear();
bool Contains(T item);
void CopyTo(T[] array, int arrayIndex);
bool Remove(T item);
}
三、逐步实现单向链表
定义一个单向链表类：
//=====单向链表=====
public class SinglyLinkedList<T> : IList<T>
{
}
接下来在VS2015 IDE 的小黄灯泡提示内选实现，让 IDE 帮我们出填空题吧。好长一大串^_^!，共14个方法或属性需要填（以我小菜鸟的经历来看，绝对是我填过最长的一个类）。下来我们只好逐步来实现这个类。
1、加入头元素。先要引入 元素类 Node<T>,把它命名为 head（书本上是这样起名的，本来我想起名叫 root的），按 C# 6.0 的新写法，我们可以直接把它缺省值 =null。刚开始创建链表里面是空的，所以头元素为 null。
//=====单向链表=====
public class SinglyLinkedList<T> : IList<T>
{
private Node<T> head = null;
2、填写 Add(T item) 方法和 int Count{get;} 属性。由于这是个链表，元素只能直线流动，所以要添加元素只能一个一个遍历到链表最尾端，我们这里加一个计数字段 int _count 。
//=====单向链表=====
public class SinglyLinkedList<T> : IList<T>
{
private Node<T> head = null;
private int _count = 0;
//---添加元素并计数
public void Add(T item)
{
if (head == null)
{
head = new Node<T>(item);
_count++;
}
else
{
Node<T> node = head;
while (node.NextNode != null)
{
node = node.NextNode;
_count++;
}
node.NextNode = new Node<T>(item);
}
}
//---计数---
public int Count
{
get { return _count; }
}
好了，终于可以添加元素并开始计数了，实验调用一下，看看是否正确：
static void Main(string[] args)
{
SinglyLinkedList<int> slist = new SinglyLinkedList<int>();
Console.WriteLine($"count: {slist.Count}");
slist.Add(1);
slist.Add(2);
slist.Add(3);
slist.Add(4);
Console.WriteLine($"count: {slist.Count}");
//输出结果：
//count: 0
//count: 4
3、实现枚举器，使得可以遍历。能够 Add(T item)后，虽然能加入元素，但我们无法显示出来里面元素的值是多少，这时就要实现 IEnumerable<T> 接口，让它能够遍历显示里面的元素值。
//---实现可枚举
public IEnumerator<T> GetEnumerator()
{
Node<T> node = head;
Node<T> result = new Node<T>();
while (node != null)
{
result = node;
node = node.NextNode;
yield return result.Value;
}
}
//---不用填写，只调用上面的
IEnumerator IEnumerable.GetEnumerator()
{
throw new NotImplementedException();
}
接下来调用看看：
Console.Write("elements: ");
foreach (var s in slist) { Console.Write($"{s} "); }
//输出：
//elements: 1 2 3 4
4、实现清空。只要把 head 设置成null ，并把 计数器归零即可。这里我这个小菜鸟不禁想到没有垃圾收集器的语言，那剩下的元素所占内存怎么释放，难道要先遍历逐个释放？或者数据不放在堆上？算了，我水平太次，不思考超出能力范围的事。
//---清空---
public void Clear()
{
head = null;
_count = 0;
}
5、实现规定的 Insert(int index,T item)。意思是在 index 位置上插入一个元素。由于是链表，插入一个新值会破坏掉整个链的连接，我们需要在插入新值前保护现场，即把上个元素和当前元素保存起来，然后把在前个元素的 NextNode 里填写新元素，在新元素的 NextNode 里填写当前元素，这样整个链表又完整了。
//---插入值---
public void Insert(int index, T item)
{
if (index >= 0 && index < _count)
{
Node<T> node = head;
Node<T> prev = null;
Node<T> next = null;
//头元素永远是head，所以要专门弄个index=0的特殊
if (index == 0)
{
next = head;
head = new Node<T>(item);
head.NextNode = next;
}
else
{
for (int i = 0; i < index; i++)
{
prev = node;
node = node.NextNode;
}
next = node;
node = new Node<T>(item);
node.NextNode = next;
prev.NextNode = node;
}
_count++;
}
else throw new Exception("Out of Range !");
}
调用检查正确否：
SinglyLinkedList<int> slist = new SinglyLinkedList<int>();
Console.WriteLine($"count: {slist.Count}");
slist.Add(1);
slist.Add(2);
slist.Add(3);
slist.Add(4);
Console.WriteLine($"count: {slist.Count}");
Console.Write("elements: ");
foreach (var s in slist) { Console.Write($"{s} "); }
Console.WriteLine();
slist.Insert(0, 5);
Console.Write("elements: ");
foreach (var s in slist) { Console.Write($"{s} "); }
Console.WriteLine();
Console.WriteLine($"count: {slist.Count}");
Console.ReadKey();
//输出：
count: 0
count: 4
elements: 1 2 3 4
elements: 5 1 2 3 4
count: 5
如果连 index=0 都能插入值，那我们之前的 Add(T item) 可以视作是 Insert(0,T item)，但是在 Insert 里面有个index 越界的检查，当链表为空的时候， Count=0，会抛出错误。针对这个，我们在 Add(T item) 前先把 Count +1，Insert 后再 Count -1 回去。Add 改造如下：
//---添加元素并计数
public void Add(T item)
{
_count++;
Insert(_count - 1, item);
_count--;
}
6、填写 int IndexOf(T item) 方法。后面的方法有 int IndexOf(T item)、bool Remove(T item)、void RemoveAt(int index) 、bool Contains(T item) 和一个索引器，这些都和查找元素有关，而 int IndexOf(T item) 无疑就是一个查找元素位置的方法，所以我们先要实现它。
还有一个问题就是，要查找 T item ，T 必须是可比较类型，所以我们在 SinglyLinkedList 类上加个 T 的约束是符合 IComparable<T> 接口的。
//=====单向链表=====
public class SinglyLinkedList<T> : IList<T> where T : IComparable<T>
//---查找---
public int IndexOf(T item)
{
int result = -1;
Node<T> node = head;
for(int i = 0; i < _count; i++)
{
if (node.Value.Equals(item))
{
result = i;
break;
}
node = node.NextNode;
}
return result;
}
有了 int IndexOf(T item) 这个利器，下来的一些方法填空就简单了。
//---包含---
public bool Contains(T item)
{
return IndexOf(item) > -1 ? true : false;
}
//---删除---
public void RemoveAt(int index)
{
if (index >= 0 && index < _count)
{
Node<T> prev = null;
Node<T> node = head;
if (index == 0)
{
head = head.NextNode;
}
else
{
for (int i = 0; i < index; i++)
{
prev = node;
node = node.NextNode;
}
prev.NextNode = node.NextNode;
}
_count--;
}
else throw new Exception("Out of Range !");
}
//---删除---
public bool Remove(T item)
{
int n = IndexOf(item);
if (n < 0) { return false; }
RemoveAt(n);
return true;
}
7、完成索引器。索引器见参考。下来具体实现：
//---索引器
public T this[int index]
{
get
{
if (index >= 0 && index < _count)
{
Node<T> node = head;
for(int i = 0; i < index;i++)
{
node = node.NextNode;
}
return node.Value;
}
else throw new Exception("Out of Range !");
}
set
{
Insert(index,value);
}
}
8、实现拷贝功能:
//---拷贝
public void CopyTo(T[] array, int arrayIndex)
{
Node<T> node = head;
for(int i = 0; i < _count; i++)
{
array[arrayIndex + i] = node.Value;
node = node.NextNode;
}
}
至此，整个单向链表和 IList<T> 接口就学习好了。附完成源程序：
//=====单向链表=====
public class SinglyLinkedList<T> : IList<T> where T : IComparable<T>
{
private Node<T> head = null;
private int _count = 0;
//---添加元素并计数---
public void Add(T item)
{
_count++;
Insert(_count - 1, item);
_count--;
}
//---计数---
public int Count
{
get { return _count; }
}
//---实现可枚举
public IEnumerator<T> GetEnumerator()
{
Node<T> node = head;
Node<T> result = new Node<T>();
while (node != null)
{
result = node;
node = node.NextNode;
yield return result.Value;
}
}
//---不用填写，只调用上面的
IEnumerator IEnumerable.GetEnumerator()
{
throw new NotImplementedException();
}
//---清空---
public void Clear()
{
head = null;
_count = 0;
}
//---插入值---
public void Insert(int index, T item)
{
if (index >= 0 && index < _count)
{
Node<T> node = head;
Node<T> prev = null;
Node<T> next = null;
//头元素永远是head，所以要专门弄个index=0的特殊
if (index == 0)
{
next = head;
head = new Node<T>(item);
head.NextNode = next;
}
else
{
for (int i = 0; i < index; i++)
{
prev = node;
node = node.NextNode;
}
next = node;
node = new Node<T>(item);
node.NextNode = next;
prev.NextNode = node;
}
_count++;
}
else throw new Exception("Out of Range !");
}
//---查找---
public int IndexOf(T item)
{
int result = -1;
Node<T> node = head;
for (int i = 0; i < _count; i++)
{
if (node.Value.Equals(item))
{
result = i;
break;
}
node = node.NextNode;
}
return result;
}
//---包含---
public bool Contains(T item)
{
return IndexOf(item) > -1 ? true : false;
}
//---删除---
public void RemoveAt(int index)
{
if (index >= 0 && index < _count)
{
Node<T> prev = null;
Node<T> node = head;
if (index == 0)
{
head = head.NextNode;
}
else
{
for (int i = 0; i < index; i++)
{
prev = node;
node = node.NextNode;
}
prev.NextNode = node.NextNode;
}
_count--;
}
else throw new Exception("Out of Range !");
}
//---删除---
public bool Remove(T item)
{
int n = IndexOf(item);
if (n < 0) { return false; }
RemoveAt(n);
return true;
}
//---索引器---
public T this[int index]
{
get
{
if (index >= 0 && index < _count)
{
Node<T> node = head;
for (int i = 0; i < index; i++)
{
node = node.NextNode;
}
return node.Value;
}
else throw new Exception("Out of Range !");
}
set
{
Insert(index, value);
}
}
//---只读？---
public bool IsReadOnly
{
get { return false; }
}
//---拷贝---
public void CopyTo(T[] array, int arrayIndex)
{
Node<T> node = head;
for (int i = 0; i < _count; i++)
{
array[arrayIndex + i] = node.Value;
node = node.NextNode;
}
}
}
//=====单向链表元素=====
class Node<T>
{
public T Value;
public Node<T> NextNode;
public Node() : this(default(T)) { }
public Node(T value)
{
Value = value;
NextNode = null;
}
}