原文链接： http://blog.csdn.net/shanyongxu/article/details/47024865

链表

LinkedList<T>集合类没有非泛型类的版本,它是一个双向链表,他的元素指向元素的前一个与后一个元素.

链表的有点事:如果要插入一个元素到链表的中间位置,效率很高,因为如果插入一个元素,只需要修改上一个元素的Next与下一个元素的Previous的引用即可.

链表的缺点是,链表只能是一个接着一个访问,这样就要用更长的时间来查找定位位于链表中间的元素.

LinkedListNode<T>被LinkedList<T>类包含,用LinkedListNode<T>类,可以获得元素的上一个与下一个元素的引用.

LinkedList<T>的属性

LinkedList<T>的方法

案例:使用一个链表LinkedList<T>和一个列表List<T>,链表包含文档,与我们上一个队列的但文档有一个优先级,文档按优先级来排序,如查多个文档优先级相同.则按插入时间决定优先排序.

链表添加文档对象时,它们应放在优先级相同的最后一个文档后面,例如:要加一个文档,优先级数是3,那么,我们应放在3级文档组的最后一个,因为此时它是最晚插入的.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace 链表

{

    class Program

    {

        static void Main(string[] args)

        {

            PriorityDocumentManager man = new PriorityDocumentManager();

            man.AddDocument(new Document("一", "nihao", 8));

            man.AddDocument(new Document("二", "nihao", 3));

            man.AddDocument(new Document("三", "nihao", 4));

            man.AddDocument(new Document("四", "nihao", 8));

            man.AddDocument(new Document("五", "nihao", 1));

            man.AddDocument(new Document("六", "nihao", 9));

            man.AddDocument(new Document("七", "nihao", 1));

            man.AddDocument(new Document("八", "nihao", 1));

            man.DispalyAllNodes();

            Console.Read();

        }

    }

    public class Document

    {

        private string title;

        public string Title

        {

            get { return title; }

            set { title = value; }

        }

        private string content;

        public string Content

        {

            get { return content; }

            set { content = value; }

        }

        private int priority;

        public int Priority

        {

            get { return priority; }

            set { priority = value; }

        }

        public Document(string title, string content, byte priority)

        {

            this.title = title;

            this.content = content;

            this.priority = priority;

        }

    }

    public class PriorityDocumentManager

    {

        //documentList包含所有的文档

        private readonly LinkedList<Document> documentList;

        //priorityNodes包含最多10个元素的引用

        private readonly List<LinkedListNode<Document>> priorityNodes;

        public PriorityDocumentManager()

        {

            //初始化

            documentList = new LinkedList<Document>();

            priorityNodes = new List<LinkedListNode<Document>>(10);

            for (int i = 0; i < 10; i++)

            {

                priorityNodes.Add(new LinkedListNode<Document>(null));

            }

        }

        /// <summary>

        /// 添加文档

        /// </summary>

        /// <param name="d">要添加的文档对象</param>

        public void AddDocument(Document d)

        {

            if (d==null)

            {

                //如果文档为空,抛出异常

                throw new ArgumentNullException("d");

            }

            //调用添加方法

            AddDocumentToPriorityNode(d, d.Priority);

        }

        private void AddDocumentToPriorityNode(Document doc, int priority)

        {

            if (priority>9||priority<0)

            {

                throw new ArgumentException("优先级异常");

            }

            if (this.priorityNodes[priority].Value==null)

            {

                priority--;

                if (priority>=0)

                {

                    AddDocumentToPriorityNode(doc, priority);

                }

                else

                {

                    this.documentList.AddLast(doc);

                    this.priorityNodes[doc.Priority] = this.documentList.Last;

                }

                return;

            }

            else

            {

                LinkedListNode<Document> priorityNode=this.priorityNodes[priority];

                if (priority==doc.Priority)

                {

                    this.documentList.AddAfter(priorityNode, doc);

                    this.priorityNodes[doc.Priority] = priorityNode.Next;

                }

                else

                {

                    LinkedListNode<Document> firstPriorityNode = priorityNode;

                    while (firstPriorityNode.Previous != null && firstPriorityNode.Previous.Value.Priority == priorityNode.Value.Priority)

                    {

                        firstPriorityNode = priorityNode.Previous;

                    }

                    this.documentList.AddBefore(firstPriorityNode, doc);

                    priorityNodes[doc.Priority] = firstPriorityNode.Previous;

                }

            }

        }

        public void DispalyAllNodes()

        {

            foreach (Document doc in this.documentList)

            {

                Console.WriteLine("文档标题：{0} 文档内容:{1} 优先级：{2}", doc.Title, doc.Content, doc.Priority);

            }

        }

    }

}

从上可以看出,

链表不仅能在列表中存储元素,还可以给每个元素存储下一个元素和上一个元素的信息.这就是LinkedList<T>包含LinkedListNode<T>类型的元素而定原因.使用LinkedListNode<T>类,可以获得列表中的下一个元素和上一个元素.

案例:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace 链表测试

{

    public struct test

    {

        public string name;

        public string num;

    }

    public struct test1

    {

        public test st;

        public string name;

    }

    class Program

    {

        static void Main(string[] args)

        {

            LinkedList<test> t = new LinkedList<test>();

            test t1, t2;

            test1 tt1, tt2;

            t1.name = "t1";

            t2.name = "t2";

            t1.num = "1";

            t2.num = "2";

            t.AddFirst(t1);

            t.AddFirst(t2);

            tt1.st = t1;

            tt2.st = t2;

            tt1.name = "tt1";

            tt2.name = "tt2";

            LinkedList<test1> tt = new LinkedList<test1>();

            tt.AddFirst(tt1);

            tt.AddFirst(tt2);

            LinkedListNode<test1> current11 = tt.FindLast(tt1);

            test1 tr1 = current11.Value;

            LinkedListNode<test> current1 = t.FindLast(t1);

            test tr = current1.Value;

            string[] words = { "the", "fox", "jumped", "over", "the", "dog" };

            LinkedList<string> sentence = new LinkedList<string>(words);

            Display(sentence);

            Console.WriteLine("sentence.Contain(\"jumped\")={0}", sentence.Contains("jumped"));

            sentence.AddFirst("today");

            Display(sentence);

            LinkedListNode<string> mark1 = sentence.First;

            sentence.RemoveFirst();

            sentence.AddLast(mark1);

            Display(sentence);

            sentence.RemoveLast();

            sentence.AddLast("yesterday");

            Display(sentence);

            mark1 = sentence.Last;

            sentence.RemoveLast();

            sentence.AddFirst(mark1);

            Display(sentence);

            sentence.RemoveFirst();

            LinkedListNode<string> current = sentence.FindLast("the");

            Display(sentence);

            sentence.AddAfter(current, "old");

            sentence.AddAfter(current, "lazy");

            DIsplayNode(current);

            current = sentence.Find("fox");

            DIsplayNode(current);

            sentence.AddBefore(current, "quick");

            sentence.AddBefore(current, "brown");

            DIsplayNode(current);

            mark1 = current;

            LinkedListNode<string> mark2 = current.Previous;

            current = sentence.Find("dog");

            DIsplayNode(current);

            try

            {

                sentence.AddBefore(current, mark1);

            }

            catch (InvalidOperationException ex)

            {

                Console.WriteLine("Exception message: {0}", ex.Message);

            }

            sentence.Remove(mark1);

            sentence.AddBefore(current, mark1);

            DIsplayNode(current);

            sentence.Remove(current);

            DIsplayNode(current);

            sentence.AddAfter(mark2, current);

            DIsplayNode(current);

            sentence.Remove("old");

            Display(sentence);

            sentence.RemoveLast();

            ICollection<string> icoll = sentence;

            icoll.Add("rhinoceros");

            Display(sentence);

            Console.WriteLine("\nCopy the list to an array.");

            string[] sArray = new string[sentence.Count];

            sentence.CopyTo(sArray, 0);

            foreach (var item in sArray)

            {

                Console.WriteLine(item);

            }

            sentence.Clear();

        }

        private static void Display(LinkedList<string> words)

        {

            foreach (var item in words)

            {

                Console.WriteLine(item + " ");

            }

            Console.WriteLine();

        }

        private static void DIsplayNode(LinkedListNode<string> node)

        {

            if (node.List == null)

            {

                Console.WriteLine("Node \"{0}\" is not in a list.", node.Value);

                return;

            }

            StringBuilder result = new StringBuilder("(" + node.Value + ")");

            LinkedListNode<string> nodeP = node.Previous;

            while (nodeP != null)

            {

                result.Insert(0, nodeP.Value + " ");

                nodeP = nodeP.Previous;

            }

            node = node.Next;

            while (node != null)

            {

                result.Append(" " + node.Value);

                node = node.Next;

            }

            Console.WriteLine(result);

        }

    }

}

自定义链表:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace 自定义链表

{

    class Program

    {

        static void Main(string[] args)

        {

        }

    }

    public class Node<T>

    {

        public T data;

        public Node()

        { }

        public Node(T data)

        {

            this.data = data;

        }

        public Node<T> next = null;

    }

    public class Link<T>

    {

        //定义链表的头节点

        private Node<T> head;

        //链表初始化

        public Link()

        {

            head = null;

        }

        /// <summary>

        /// 链表的长度,遍历整个链表,知道链表结尾

        /// </summary>

        /// <returns></returns>

        public int Count()

        {

            //定义一个节点

            Node<T> p = head;

            int count = 0;//链表计数器

            //遍历链表

            while (p!=null)

            {

                count++;

                p = p.next;//移到下一个节点

            }

            return count;

        }

        /// <summary>

        /// 取链表的第i个节点的值

        /// </summary>

        /// <param name="i">第i个节点</param>

        /// <returns></returns>

        public T GetElem(int i)

        {

            //定义一个节点

            Node<T> p = head;

            int k = 0;//计数器

            //如果i大于链表的长度或i小于0,则报出异常

            if (i>=Count()||i<0)

            {

                throw new Exception("error");

            }

            //如果i大于0且小于链表长度,则遍历链表知道第i个节点为止

            while (k<i)

            {

                k++;

                p = p.next;

            }

            return p.data;

        }

        /// <summary>

        /// 在链表的第i个位置上插入新的节点

        /// </summary>

        /// <param name="e">要插入节点的值</param>

        /// <param name="i">链表的第i个节点</param>

        public void Insert(T e, int i)

        {

            Node<T> p = new Node<T>(e);//要插入的节点

            Node<T> q = head;

            int k = 0;//计数器

            //如果i大于链表的长度或i小于0,则抛出异常

            if (i>=Count()||i<0)

            {

                Console.WriteLine("Error");

                return;

            }

            //如果再链表头插入,移动头指针

            if (i==0)

            {

                p.next = head;

                head = p;

                return;

            }

            //遍历链表直到i-1个节点为止

            while (k<i-1)

            {

                k++;

                q = q.next;

            }

            //把新节点插入在第i以个点的位置

            p.next = q.next;

            q.next = p;

        }

        /// <summary>

        /// 删除第i个节点

        /// </summary>

        /// <param name="i">链表的第i个节点</param>

        public void RemoveAt(int i)

        {

            Node<T> p = head;

            int k = 0;//计数器

            // //如果i大于链表的长度或i小于0,则抛出异常

            if (i >= Count() || i < 0)

            {

                Console.WriteLine("Error");

                return;

            }

            //如果删除链表头,移动头指针

            if (i==0)

            {

                head.next = head.next.next;

                return;

            }

            //遍历链表直到第i-1个节点为止

            while (k<i-1)

            {

                k++;

                p = p.next;

            }

            //删除第i个节点

            p.next = p.next.next;

        }

        /// <summary>

        /// 在链表尾加入一个新的节点

        /// </summary>

        /// <param name="e">新的节点的值</param>

        public void Add(T e)

        {

            Node<T> p = new Node<T>(e);//创建一个新的节点

            Node<T> q = new Node<T>();

            //如果链表为空,则将新的节点作为头

            if (head==null)

            {

                head = p;

                return;

            }

            //如果链表不为空,则在链表尾加入新的节点

            //从头指针开始遍历,直至链表尾

            q = head;

            while (q.next!=null)

            {

                q = q.next;

            }

            //在链表尾插入新节点

            q.next = q;

        }

        /// <summary>

        /// 查找某个元素在立案表中第一次出现的位置

        /// </summary>

        /// <param name="e">要查找的元素</param>

        /// <returns></returns>

        public int IndexOf(T e)

        {

            Node<T> p = head;

            int k = 0;//计数器

            /*

             * 遍历整个链表,知道找到第一个节点的值

             * 与钙元素相等退出,并返回相应的位置索引.

             * 如果没有找到,则返回-1

             */

            //从头指针开始遍历,找到退出,并返回相应的位置索引

            while (p.next!=null)

            {

                if (p.data.Equals(e))

                {

                    return k;

                }

                k++;

                p = p.next;

            }

            if (!p.data.Equals(e))

            {

                k++;

            }

            //如果没有找到,则返回-1

            return k >= Count() ? -1 : k;

        }

        /// <summary>

        /// 查找某个元素在链表中最后一次出现的位置

        /// </summary>

        /// <param name="e">要查找的元素</param>

        /// <returns>这个元素在链表中最后一次出现的位置的索引</returns>

        public int LastIndexOf(T e)

        {

            Node<T> p = head;

            int index = -1;//最后一次出现的位置索引

            int k = 0;//计数器

            /*

             * 遍历整个链表,每发现相应节点的值与该元素相等

             * 则将该节点的位置所以赋给index,

             * 这样index的值就是最后一次的值.如果没有,则返回-1

             * 

             */

            while (p.next!=null)

            {

                if (p.data.Equals(e))

                {

                    index = k;

                }

                k++;

                p = p.next;

            }

            if (p.data.Equals(e))

            {

                index = k;

            }

            return index;

        }

        /// <summary>

        /// 判断链表是否为空

        /// </summary>

        /// <returns></returns>

        public bool Empty()

        {

            return head == null ? true : false;

        }

        /// <summary>

        /// 清空链表

        /// </summary>

        public void Clear()

        {

            head = null;

        }

        /// <summary>

        /// 将链表转成数组

        /// </summary>

        /// <returns>转换后的数组</returns>

        public T[] ToArray()

        {

            T[] array = new T[Count()];//定义一个与链表长度相同的数组

            /*

             * 遍历链表,将链表的每个节点的值放到相应的数组里

             * 

             */

            Node<T> p = head;

            int i = 0;//数组下标计数器

            while (p.next!=null)

            {

                array[i++] = p.data;

                p = p.next;

            }

            array[Count() - 1] = p.data;

            return array;

        }

        /// <summary>

        /// 将一个数组加到链表中

        /// </summary>

        /// <param name="a">要加入链表的数组</param>

        public void AddRange(T[] a)

        {

            //遍历整个数组,将数组中的每个元素作为一个新的节点加入到链表中

            for (int i = 0; i < a.Length; i++)

            {

                Add(a[i]);

            }

        }

        /// <summary>

        /// 删除链表中值为某个元素的所有节点

        /// </summary>

        /// <param name="e">要删除节点的值</param>

        public void Remove(T e)

        {

            //如果头指针的值等于这个元素,则删除这个元素,并将头指针后移

            while (head.data.Equals(e))

            {

                head = head.next;

            }

            //如果不是头指针,则删除该节点

            Node<T> p = head;

            while (p.next.next!=null)

            {

                if (p.next.data.Equals(e))

                {

                    p.next = p.next.next;

                    continue;

                }

                p = p.next;

            }

            if (p.next.data.Equals(e))

            {

                p.next = null;

            }

        }

        /// <summary>

        ///将链表中所有为某个值的节点替换为另一个值

        /// </summary>

        /// <param name="first"></param>

        /// <param name="second"></param>

        public void Replace(T first, T second)

        {

            Node<T> p = head;

            while (p.next!=null)

            {

                if (p.data.Equals(first))

                {

                    p.data = second;

                }

                p = p.next;

            }

            if (p.data.Equals(first))

            {

                p.data = second;

            }

        }

        /// <summary>

        /// 链表反转

        /// </summary>

        public void Reverse()

        {

            Node<T> p = head;

            Node<T> newhead = head;

            Node<T> q = p;

            p = p.next;

            newhead.next = null;

            while (p.next!=null)

            {

                q = p;

                p = p.next;

                q.next = newhead;

                newhead = q;

            }

            q = p;

            q.next = newhead;

            newhead = p;

            head = newhead;

        }

    }

}