一：单链表实现原理
//链表类，包含链表定义及基本操作方法 public class MyLinkList<T> { private Node<T> head; //单链表的头结点 //头结点属性 public Node<T> Head { get { return head; } set { head = value; } } //构造器 public MyLinkList() { 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 || i > GetLength()) { Console.WriteLine("LinkList 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 || i > GetLength()) { Console.WriteLine("LinkList 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 || i > GetLength()) { Console.WriteLine("LinkList 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 " + i + "th node is not exist!"); return default(T); } } //获得单链表的第i个数据元素 public T GetElem(int i) { if (IsEmpty() || i < 0) { Console.WriteLine("LinkList is empty or position is error! "); 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 " + i + "th node is not exist!"); return default(T); } } //在单链表中查找值为value的结点 public int Locate(T value) { if (IsEmpty()) { Console.WriteLine("LinkList 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) { Console.Write(p.Data + " "); p = p.Next; } } } public class Program { static void Main(string[] args) { MyLinkList<string> myLinkList = new MyLinkList<string>(); //实例化一个单链表 Console.WriteLine(myLinkList.GetLength()); //获取长度 //添加元素 myLinkList.Append("good"); myLinkList.Append("monring"); myLinkList.Append("lwk"); myLinkList.Insert("!", 5); //在i结点前插元素，位置错误测试 myLinkList.InsertPost("!", 5); //在i结点后插元素，位置错误测试 myLinkList.InsertPost("!", 3); //后插元素 myLinkList.Insert(",", 3); //前插元素 myLinkList.Display(); //显示链表元素 Console.WriteLine(myLinkList.GetElem(4));//获取结点,并显示 myLinkList.Delete(1); //删除结点 myLinkList.Display(); Console.WriteLine(myLinkList.GetLength()); //显示链表长度 Console.Read(); } }
二：双向链表实现原理
using System; using System.Text; namespace 线性表 { public class DbLinkList<T> : IListDS<T> { private DbNode<T> head; public DbNode<T> Head { get { return head; } set { head = value; } } public DbLinkList() { head = null; } /// <summary> /// 类索引器 /// </summary> /// <param name="index"></param> /// <returns></returns> public T this[int index] { get { return this.GetItemAt(index); } } /// <summary> /// 返回单链表的长度 /// </summary> /// <returns></returns> public int Count() { DbNode<T> p = head; int len = 0; while (p != null) { len++; p = p.Next; } return len; } /// <summary> /// 清空 /// </summary> public void Clear() { head = null; } /// <summary> /// 是否为空 /// </summary> /// <returns></returns> public bool IsEmpty() { return head == null; } /// <summary> /// 在最后附加元素 /// </summary> /// <param name="item"></param> public void Append(T item) { DbNode<T> d = new DbNode<T>(item); DbNode<T> n = new DbNode<T>(); if (head == null) { head = d; return; } n = head; while (n.Next != null) { n = n.Next; } n.Next = d; d.Prev = n; } //前插 public void InsertBefore(T item, int i) { if (IsEmpty() || i < 0) { Console.WriteLine("List is empty or Position is error!"); return; } //在最开头插入 if (i == 0) { DbNode<T> q = new DbNode<T>(item); q.Next = head;//把"头"改成第二个元素 head.Prev = q; head = q;//把自己设置为"头" return; } DbNode<T> n = head; DbNode<T> d = new DbNode<T>(); int j = 0; //找到位置i的前一个元素d while (n.Next != null && j < i) { d = n; n = n.Next; j++; } if (n.Next == null) //说明是在最后节点插入(即追加) { DbNode<T> q = new DbNode<T>(item); n.Next = q; q.Prev = n; q.Next = null; } else { if (j == i) { DbNode<T> q = new DbNode<T>(item); d.Next = q; q.Prev = d; q.Next = n; n.Prev = q; } } } /// <summary> /// 在位置i后插入元素item /// </summary> /// <param name="item"></param> /// <param name="i"></param> public void InsertAfter(T item, int i) { if (IsEmpty() || i < 0) { Console.WriteLine("List is empty or Position is error!"); return; } if (i == 0) { DbNode<T> q = new DbNode<T>(item); q.Next = head.Next; head.Next.Prev = q; head.Next = q; q.Prev = head; return; } DbNode<T> p = head; int j = 0; while (p != null && j < i) { p = p.Next; j++; } if (j == i) { DbNode<T> q = new DbNode<T>(item); q.Next = p.Next; if (p.Next != null) { p.Next.Prev = q; } p.Next = q; q.Prev = p; } else { Console.WriteLine("Position is error!"); } } /// <summary> /// 删除位置i的元素 /// </summary> /// <param name="i"></param> /// <returns></returns> public T RemoveAt(int i) { if (IsEmpty() || i < 0) { Console.WriteLine("Link is empty or Position is error!"); return default(T); } DbNode<T> q = new DbNode<T>(); if (i == 0) { q = head; head = head.Next; head.Prev = null; return q.Data; } DbNode<T> p = head; int j = 0; while (p.Next != null && j < i) { j++; q = p; p = p.Next; } if (j == i) { p.Next.Prev = q; q.Next = p.Next; return p.Data; } else { Console.WriteLine("The node is not exist!"); return default(T); } } /// <summary> /// 获取指定位置的元素 /// </summary> /// <param name="i"></param> /// <returns></returns> public T GetItemAt(int i) { if (IsEmpty()) { Console.WriteLine("List is empty!"); return default(T); } DbNode<T> p = new DbNode<T>(); p = head; if (i == 0) { return p.Data; } int j = 0; while (p.Next != null && j < i) { j++; p = p.Next; } if (j == i) { return p.Data; } else { Console.WriteLine("The node is not exist!"); return default(T); } } //按元素值查找索引 public int IndexOf(T value) { if (IsEmpty()) { Console.WriteLine("List is Empty!"); return -1; } DbNode<T> p = new DbNode<T>(); p = head; int i = 0; while (!p.Data.Equals(value) && p.Next != null) { p = p.Next; i++; } return i; } /// <summary> /// 元素反转 /// </summary> public void Reverse() { DbLinkList<T> result = new DbLinkList<T>(); DbNode<T> t = this.head; result.Head = new DbNode<T>(t.Data); t = t.Next; //(把当前链接的元素从head开始遍历，逐个插入到另一个空链表中，这样得到的新链表正好元素顺序跟原链表是相反的) while (t!=null) { result.InsertBefore(t.Data, 0); t = t.Next; } this.head = result.head;//将原链表直接挂到"反转后的链表"上 result = null;//显式清空原链表的引用，以便让GC能直接回收 } //得到某个指定的节点(为了下面测试从后向前遍历) private DbNode<T> GetNodeAt(int i){ if (IsEmpty()) { Console.WriteLine("List is empty!"); return null; } DbNode<T> p = new DbNode<T>(); p = head; if (i == 0) { return p; } int j = 0; while (p.Next != null && j < i) { j++; p = p.Next; } if (j == i) { return p; } else { Console.WriteLine("The node is not exist!"); return null; } } /// <summary> /// 测试用prev属性从后面开始遍历 /// </summary> /// <returns></returns> public string TestPrevErgodic() { DbNode<T> tail = GetNodeAt(Count() - 1); StringBuilder sb = new StringBuilder(); sb.Append(tail.Data.ToString() + ","); while (tail.Prev != null) { sb.Append(tail.Prev.Data.ToString() + ","); tail = tail.Prev; } return sb.ToString().TrimEnd(','); } public override string ToString() { StringBuilder sb = new StringBuilder(); DbNode<T> n = this.head; sb.Append(n.Data.ToString() + ","); while (n.Next != null) { sb.Append(n.Next.Data.ToString() + ","); n = n.Next; } return sb.ToString().TrimEnd(','); } } }
Console.WriteLine("-------------------------------------"); Console.WriteLine("双链表测试开始..."); DbLinkList<string> dblink = new DbLinkList<string>(); dblink.Head = new DbNode<string>("x"); dblink.InsertBefore("w", 0); dblink.InsertBefore("v", 0); dblink.Append("y"); dblink.InsertBefore("z", dblink.Count()); Console.WriteLine(dblink.Count());//5 Console.WriteLine(dblink.ToString());//v,w,x,y,z Console.WriteLine(dblink[1]);//w Console.WriteLine(dblink[0]);//v Console.WriteLine(dblink[4]);//z Console.WriteLine(dblink.IndexOf("z"));//4 Console.WriteLine(dblink.RemoveAt(2));//x Console.WriteLine(dblink.ToString());//v,w,y,z dblink.InsertBefore("x", 2); Console.WriteLine(dblink.ToString());//v,w,x,y,z Console.WriteLine(dblink.GetItemAt(2));//x dblink.Reverse(); Console.WriteLine(dblink.ToString());//z,y,x,w,v dblink.InsertAfter("1", 0); dblink.InsertAfter("2", 1); dblink.InsertAfter("6", 5); dblink.InsertAfter("8", 7); dblink.InsertAfter("A", 10);//Position is error! Console.WriteLine(dblink.ToString()); //z,1,2,y,x,w,6,v,8 string _tail = dblink.GetItemAt(dblink.Count()-1); Console.WriteLine(_tail); Console.WriteLine(dblink.TestPrevErgodic());//8 Console.ReadKey(); //8,v,6,w,x,y,2,1,z
双链表的插入操作要稍微复杂一点，示意图如下：
同样对于删除操作，也要额外处理prev指向
二：循环双向链表实现原理
代码就不贴了
