C#数据结构和算法学习系列十三----链表

链表是被称为节点的类对象的群集。每一个节点通过一个引用链接到列表内的后继节点上。节点包括存储数据的字段和节点引用的字段。到另外一个节点的引用被称为是链接。数组和链表之间的一个主要区别就是数组内的元素是通过位置（索引）进行引用的，而链表内的元素则是通过它们与数组其他元素的关系进行引用的。

1.面向对象链表的设计。链表的设计至少包含两个类。这里会创建一个Node 类，而且每次向链表添加节点的时候会实例化一个Node 对象。链表内的节点通过索引与其他节点相互连接在一起。而且把这些索引设置为使用创建在一个独立的LinkedList 类中的方法。节点是由两个数据成员组成的：存储着节点数据的Element，以及存储着指向表内下一节点引用的Link。这里会使用Object 作为Element 的数据类型，所以也就不用担心存储在表内的数据的类型了。Link 的数据类型是Node，这看似很奇怪，但实际上是很容易理解的。因为要把链接指向下一个节点，而且是用索引来作为这个链接，所以需要把成员Link 设置为Node 类型。如下：

public class Node
{
     public Object Element;
     public Node Link;
     public Node()
     {
          Element = null;
          Link = null;
     }
     public Node(Object theElement)
     {
          Element = theElement;
          Link = null;
     }
}

LinkedList 类用来创建链表中节点之间的链接。这个类包括几种方法，有把节点添加到链表的方法，有从链表中移除节点的方法，有遍历链表的方法，还有找到链表内节点的方法。此外，还需要一种构造器方法来实例化链表。此类中唯一的数据成员就是头节点。如下：

public class LinkedList
{
     protected Node header;
     public LinkedList()//构造方法实例化一个节点
     {
          header = new Node(" header");
     }
     private Node Find(Object item)//查找节点
     {
          Node current = new Node();
          current = header;
          while (current. Element != item)
               current = current.Link;
          return current;
     }
     public void Insert(Object newItem, Object after)//在查找的节点前面加入节点
     {
          Node current = new Node();
          Node newNode = new Node(newItem);
          current = Find(after);
          newNode.Link = current.Link;
          current.Link = newNode;
     }
     private Node FindPrevious(Object n)//查找前一个节点
     {
          Node current = header;
          while (!(current.Link == null) && (current.Link.Element != n))
               current = current.Link;
          return current;
     }
     public void Remove(Object n)//移除节点
     {
          Node p = FindPrevious(n);
          if (!(p.Link == null))
               p.Link = p.Link.Link;
     }
     public void PrintList()
     {
          Node current = new Node();
          current = header;
          while (!(current.Link == null))
          {
               Console.WriteLine(current.Link.Element);
               current = current.Link;
          }
     }
}

2.通用的Node类和LinkedList类。System.Collections.Generic 命名空间为构建链表提供了两种通用的类：LinkedList 类和LinkedListNode 类。Node 类为存储数值和链接提供了两个数据字段，而LinkedList 类则用在节点前以及在节点后的插入方法实现了双向链表。这个类还提供了其他方法，包括移除节点的方法，找到链表内首节点和尾节点的方法，当然还有其他有用的方法。

using System;
using System.Collections.Generic;
using System.Text;
class Program
{
     static void Main(string[] args)
     {
          LinkedListNode<string> node = new
          LinkedListNode<string>("Mike");
          LinkedList<string> names = new LinkedList<string>();
          names.AddFirst(node);
          LinkedListNode<string> node1 = new LinkedListNode<string>("David");
          names.AddAfter(node, node1);
          LinkedListNode<string> node2 = new LinkedListNode<string>("Raymond");
          names.AddAfter(node1, node2);
          LinkedListNode<string> node3 = new LinkedListNode<string>(null);
          LinkedListNode<string> aNode = names.First;
          while (aNode != null)
          {
               Console.WriteLine(aNode.Value);
               aNode = aNode.Next;
          }
          aNode = names.Find(" David");
          if (aNode != null) aNode = names.First;
          while (aNode != null)
          {
               Console.WriteLine(aNode.Value);
               aNode = aNode.Next;
          }
          Console.Read();
     }
}