代码 单链表结点类的实现如下所示。 public class Node < T > { private T data; // 数据域 private Node < T > next; // 引用域 // 构造器 public Node(T val, Node < T > p) { data = val; next = p; } // 构造器 public Node(Node < T > p) { next = p; } // 构造器 public Node(T val) { data = val; next = null ; } // 构造器 public Node() { data = default (T); next = null ; } // 数据域属性 public T Data { get { return data; } set { data = value; } } // 引用域属性 public Node < T > Next { get { return next; } set { next = value; } } }链表操作实现类 public class LinkList < T > : IListDS < T > { private Node < T > head; // 单链表的头引用 // 头引用属性 public Node < T > Head { get { return head; } set { head = value; } } // 构造器 public LinkList() { head = null ; } // 求单链表的长度 public int GetLength() { Node < T > p = head; int len = 0 ; while (p != null ) { ++ len; p = p.Next; } return len; } // 清空单链表 public void Clear() { head = null ; } // 判断单链表是否为空 public bool IsEmpty() { if (head == null ) { return true ; } else { return false ; } } // 在单链表的末尾添加新元素 public void Append(T item) { Node < T > q = new Node < T > (item); Node < T > p = new Node < T > (); if (head == null ) { head = q; return ; } p = head; while (p.Next != null ) { p = p.Next; } p.Next = q; } // 在单链表的第i个结点的位置前插入一个值为item的结点 public void Insert(T item, int i) { if (IsEmpty() || i < 1 ) { Console.WriteLine( " List is empty or Position is error! " ); return ; } if (i == 1 ) { Node < T > q = new Node < T > (item); q.Next = head; head = q; return ; } Node < T > p = head; Node < T > r = new Node < T > (); int j = 1 ; while (p.Next != null && j < i) { r = p; p = p.Next; ++ j; } if (j == i) { Node < T > q = new Node < T > (item); q.Next = p; r.Next = q; } } // 在单链表的第i个结点的位置后插入一个值为item的结点 public void InsertPost(T item, int i) { if (IsEmpty() || i < 1 ) { Console.WriteLine( " List is empty or Position is error! " ); return ; } if (i == 1 ) { Node < T > q = new Node < T > (item); q.Next = head.Next; head.Next = q; return ; } Node < T > p = head; int j = 1 ; while (p != null && j < i) { p = p.Next; ++ j; } if (j == i) { Node < T > q = new Node < T > (item); q.Next = p.Next; p.Next = q; } } // 删除单链表的第i个结点 public T Delete( int i) { if (IsEmpty() || i < 0 ) { Console.WriteLine( " Link is empty or Position is error! " ); return default (T); } Node < T > q = new Node < T > (); if (i == 1 ) { q = head; head = head.Next; return q.Data; } Node < T > p = head; int j = 1 ; while (p.Next != null && j < i) { ++ j; q = p; p = p.Next; } if (j == i) { q.Next = p.Next; return p.Data; } else { Console.WriteLine( " The ith node is not exist! " ); return default (T); } } // 获得单链表的第i个数据元素 public T GetElem( int i) { if (IsEmpty()) { Console.WriteLine( " List is empty! " ); return default (T); } Node < T > p = new Node < T > (); p = head; int j = 1 ; while (p.Next != null && j < i) { ++ j; p = p.Next; } if (j == i) { return p.Data; } else { Console.WriteLine( " The ith node is not exist! " ); return default (T); } } // 在单链表中查找值为value的结点 public int Locate(T value) { if (IsEmpty()) { Console.WriteLine( " List is Empty! " ); return - 1 ; } Node < T > p = new Node < T > (); p = head; int i = 1 ; while ( ! p.Data.Equals(value) && p.Next != null ) { p = p.Next; ++ i; } return i; } public void Display() { Node < T > p = new Node < T > (); p = this .head; while (p != null ) { System.Console.WriteLine(p.Data); p = p.Next; } } }IListDs接口如下： public interface IListDS < T > { int GetLength(); // 求长度 void Clear(); // 清空操作 bool IsEmpty(); // 判断线性表是否为空 void Append(T item); // 附加操作 void Insert(T item, int i); // 插入操作 T Delete( int i); // 删除操作 T GetElem( int i); // 取表元 int Locate(T value); // 按值查找 // void Rervese(); }链表的应用 public class LinkListApplication { // 在头部插入结点建立单链表的算法如下： public static LinkList < int > CreateLListHead() { int d; LinkList < int > L = new LinkList < int > (); d = Int32.Parse(Console.ReadLine()); while (d != - 1 ) { Node < int > p = new Node < int > (d); p.Next = L.Head; L.Head = p; d = Int32.Parse(Console.ReadLine()); } return L; } // 在尾部插入结点建立单链表的算法如下： public static LinkList < int > CreateListTail() { Node < int > R = new Node < int > (); int d; LinkList < int > L = new LinkList < int > (); R = L.Head; d = Int32.Parse(Console.ReadLine()); while (d != - 1 ) { Node < int > p = new Node < int > (d); if (L.Head == null ) { L.Head = p; } else { R.Next = p; } R = p; d = Int32.Parse(Console.ReadLine()); } if (R != null ) { R.Next = null ; } return L; } // 将两表合并成一表的算法实现如下： public LinkList < int > Merge(LinkList < int > Ha, LinkList < int > Hb) { LinkList < int > Hc = new LinkList < int > (); Node < int > s = new Node < int > (); Node < int > p = Ha.Head.Next; Node < int > q = Hb.Head.Next; Hc = Ha; Hc.Head.Next = null ; while (p != null && q != null ) { if (p.Data < q.Data) { s = p; p = p.Next; } else { s = q; q = q.Next; } Hc.Append(s.Data); } if (p == null ) { p = q; } while (p != null ) { s = p; p = p.Next; Hc.Append(s.Data); } return Hc; } // 删除单链表中相同值的结点的算法实现如下： public LinkList < int > Purge(LinkList < int > Ha) { LinkList < int > Hb = new LinkList < int > (); Node < int > p = Ha.Head.Next; Node < int > q = new Node < int > (); Node < int > s = new Node < int > (); s = p; p = p.Next; s.Next = null ; Hb.Head.Next = s; while (p != null ) { s = p; p = p.Next; q = Hb.Head.Next; while (q != null && q.Data != s.Data) { q = q.Next; } if (q == null ) { s.Next = Hb.Head.Next; Hb.Head .Next = s; } } return Hb; } }