转：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();  

     }  

} 

转载于:https://www.cnblogs.com/mechase/archive/2011/11/07/2239371.html

总结

以上是生活随笔为你收集整理的转：C#数据结构和算法学习系列十三----链表的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。