链表增、删、改、查的例子：

增：Add（int index,E e）方法 （1）如果索引为零，那就把新节点作为新的头部节点，而新节点的引用指向就是原来的头部节点 （2）如果不为零，就遍历到索引-1，因为要把新节点的引用指向索引的结点，然后把新节点设成索引-1的引用指向 改：Set（int index,E e）方法 （1）直接 for 循环到索引的位置，然后把索引到的链表元素设成新的值 查：Containa（E e）方法 （1）直接 while 循环（把指向下一个引用的本身换成自己），然后判断在这过程中有没有引用是传进来的值 删：RemoveAt(int index) 通过索引来删除遍历到的值 （1）如果索引为零，那就把头部节点的引用指向设为头部节点 （2）如果不为零，把索引 - 1的结点，其引用指向就是要删掉的值，然后把要删掉的值的引用指向设为索引-1的引用结点 Remove（E e）通过输入的值，删除链表中的值 （1）判断输入的值是否是头部节点，是：将头部节点的引用指向设为头部节点，然后长度自减。 否：声明 两个 Node 变量（cur[存储下一个的引用]、pre[存储上一个的引用]），while 循环(只要下一个引用不是空) ，在这其中再判断 cur 是否为输入的值。while之外再次判断将上一个引用的结点的结点，其引用指向设为上一个引用的引用结点。

  1. class LinkedList1<E>
  2.     {
  3.         private class Node
  4.         {
  5.             public E e;
  6.             public Node next;
  8.             /// <summary>
  9.             /// 指向下一个节点的方法
  10.             /// </summary>
  11.             /// <param name="e"></param>
  12.             /// <param name="next"></param>
  13.             public Node(E e, Node next)
  14.             {
  15.                 this.e = e;
  16.                 this.next = next;
  17.             }
  19.             /// <summary>
  20.             /// 头部的节点
  21.             /// </summary>
  22.             /// <param name="e"></param>
  23.             public Node(E e)
  24.             {
  25.                 this.e = e;
  26.                 this.next = null;
  27.             }
  29.             public override string ToString()
  30.             {
  31.                 return e.ToString();
  32.             }
  33.         }
  35.         private Node head;
  36.         private int N;
  38.         public  LinkedList1() {
  39.             head = null;
  40.             N = 0;
  41.         }
  43.         public int Count
  44.         {
  45.             get { return N; }
  46.         }
  48.         public bool IsEmpty
  49.         {
  50.             get { return N == 0; }
  51.         }
  53.         public void Add(int index,E e)
  54.         {
  55.             if (index < 0 || index > N)
  56.                 throw new ArgumentException("非法索引");
  57.             if (index == 0)
  58.             {
  59.                 //如果index 等于零，那就说明我们将进行头部节点的添加
  60.                 //原来的头部节点就是新节点的引用指向
  61.                 //新节点就是新的头部结点
  62.                 //Node node = new Node(e);
  63.                 //node.next = head;
  64.                 //head = node;
  66.                 head = new Node(e, head);
  67.             }
  68.             else
  69.             {
  70.                 Node pro = head;
  71.                 for (int i = 0; i < index - 1; i++)
  72.                     pro = pro.next;
  73.                 //.next 意思是：结点的引用指向
  75.                 //将 for循环遍历后的头部结点指向的引用 变为 新节点的引用指向
  76.                 //Node node = new Node(e); //新的链表=>只有头部节点
  77.                 //node.next = pro.next;  //新链表的头部节点的引用指向 赋值成 旧链表的头部节点的引用指向
  78.                 //pro.next = node;    //然后旧链表的头部节点的引用指向 赋值成 新链表的头部节点
  80.                 pro.next = new Node(e, pro.next);
  81.             }
  82.             N++;
  83.         }
  85.         public void AddFrist(E e)
  86.         {
  87.             Add(0, e);
  88.         }
  90.         public void AddLast(E e)
  91.         {
  92.             Add(N, e);
  93.         }
  95.         public E Get(int index)
  96.         {
  97.             if (index < 0 || index > N)
  98.                 throw new ArgumentException("非法索引");
  100.             Node cur = head;
  101.             for (int i = 0; i < index; i++)
  102.                 cur = cur.next;
  104.             return cur.e;
  105.         }
  107.         public E GetFirst()
  108.         {
  109.             return Get(0);
  110.         }
  112.         public E GetLast()
  113.         {
  114.             return Get(N - 1);
  115.         }
  117.         public void Set(int index, E newE)
  118.         {
  119.             if (index < 0 || index > N)
  120.                 throw new ArgumentException("非法索引");
  122.             Node cur = head;
  123.             for (int i = 0; i < index; i++)
  124.                 cur = cur.next;
  126.             cur.e = newE;
  127.         }
  129.         public bool Containa(E e)
  130.         {
  131.             Node cur = head;
  132.             while (cur != null)
  133.             {
  134.                 if (cur.e.Equals(e))
  135.                     return true;
  137.                 cur = cur.next;
  138.             }
  139.             return false;
  140.         }
  141.         public void Remove(E e)
  142.         {
  143.             if (head == null)
  144.                 return;
  146.             if (head.e.Equals(e))
  147.             {
  148.                 head = head.next;
  149.                 N--;
  150.             }
  151.             else
  152.             {
  153.                 Node cur = head;
  154.                 Node pre = null;
  155.                 while (cur != null)
  156.                 {
  157.                     if (cur.e.Equals(e))
  158.                         break;
  160.                     pre = cur;
  161.                     cur = cur.next;
  162.                 }
  163.                 if (cur != null)
  164.                 {
  165.                     pre.next = pre.next.next;
  166.                     N--;
  167.                 }
  168.             }
  169.         }
  171.         public override string ToString()
  172.         {
  173.             StringBuilder res = new StringBuilder();
  174.             Node cur = head;
  175.             while (cur!=null)
  176.             {
  177.                 res.Append(cur + "->");
  178.                 cur = cur.next;
  179.             }
  180.             res.Append("null");
  181.             return res.ToString();
  182.         }
  183.     }
  185. class Program
  186.     {
  187.         private static void Main(string[] args)
  188.         {
  189.             LinkedList1<int> l = new LinkedList1<int>();
  190.             for (int i = 0; i < 5; i++)
  191.             {
  192.                 l.AddFrist(i);
  193.                 Console.WriteLine(l);
  194.             }
  196.             l.AddLast(666);
  197.             Console.WriteLine(l);
  199.             l.Add(2, 1000);
  200.             Console.WriteLine(l);
  202.             l.Set(2, 200);
  203.             Console.WriteLine(l);
  205.             //4->3->200->2->1->0->666->null
  207.             l.Remove(200);
  208.             Console.WriteLine(l);
  210.             l.RemoveLast();
  211.             Console.WriteLine(l);
  213.             l.RemoveFirst();
  214.             Console.WriteLine(l);
  216.             Console.ReadKey();
  217.         }
  218.     }

运行结果：

image.png

基于无序链表实现集合、映射

集合：集合（Set）作为存储数据的容器时： 特点：他不允许存储相同元素，只能保留一份 应用：能快速的帮助我们进行去重操作，过滤掉重复的元素

映射：指两个元素之间相互“对应”的关系 在C#中用字典（Dictionary）来表示，储存键值对的数据

//集合
//以下方法的调用，都只是调用Linked List1 封装好的方法而已
//具体实现的逻辑看 LinkedList1
  class LinkedLIstISet<E>:ISet<E>
    {
        LinkedList1<E> list;

        public LinkedLIstISet()
        {
            list = new LinkedList1<E>();
        }

        public int Count { get { return list.Count; } }

        public bool IsEmpty { get { return list.IsEmpty; } }

        public void Add(E e)
        {
            if (!Contains(e))
                list.AddFrist(e);
        }

        public bool Contains(E e)
        {
            return list.Containa(e);
        }

        public void Remove(E e)
        {
            list.Remove(e);
        }
    }
     class Program
    {
        static void Main(string[] args)
        {
            Stopwatch t = new Stopwatch();

            Console.WriteLine("双城记");

            List<string> words=TestHelper.ReadFile("测试文件1/双城记.txt");
            Console.WriteLine("总单词数： "+words.Count);

            LinkedList1Set<string> set = new LinkedList1Set<string>();

            t.Start();
            foreach (var word in words)
                set.Add(word); //添加的过程中会进行去重的操作，不允许添加重复元素
            t.Stop();

            Console.WriteLine("不同单词的总数： "+set.Count);
            Console.WriteLine("运行时间： "+t.ElapsedMilliseconds);

            Console.Read();
        }
    }
//集合

//映射
class LinkedList3Dictionary<Key,Value>:IDictionary<Key,Value>
    {
        private LinkedList3<Key,Value> List;

        public LinkedList3Dictionary()
        {
            List = new LinkedList3<Key, Value>();
        }

        /// <summary>
        /// 由于是直接返回《linked List3 的容量》,所以是O（1）
        /// </summary>
        public int Count { get { return List.Count; } }

        /// <summary>
        /// 同样直接返回《linked List的容量》
        /// </summary>
        public bool IsEmpty { get { return List.IsEmpty; } }

        /// <summary>
        ///  因为《linked List3 类中 Add 方法 是在头部进行添加数据的》
        ///  所以时间复杂度是O(1)
        /// </summary>
        public void Add(Key key, Value value)
        {
            List.Add(key, value);
        }

        /// <summary>
        /// 通过遍历《linkedList3.GetNode》数据，来查找链表中是否有 Key 值
        /// 所以时间复杂度是O（N）
        /// </summary>
        public bool ContainKey(Key key)
        {
            return List.Contains(key);
        }

        /// <summary>
        ///  同样是通过《linkedList3.GetNode》来获取键(key)，然后返回键相应的值
        ///  所以时间复杂度是O（N）
        /// </summary>
        public Value Get(Key key)
        {
            return List.Get(key);
        }

        /// <summary>
        /// 通过传进去的键（key），判断《LinkedList3》中对应的键
        /// 然后进行删除
        /// 所以还是从头开始遍历，时间复杂度O（N）
        /// </summary>
        public void Remove(Key key)
        {
            List.Remove(key);
        }

        /// <summary>
        /// 同样通过《linkedList3.GetNode》来找到对应的键(key)
        /// 然后将 key.value = NewValue
        /// 时间复杂度O(N)
        /// </summary>
        public void Set(Key key, Value NewValue)
        {
            List.Set(key, NewValue);
        }
    }
 class Program
    {
        private static void Main(string[] args)
        {

            Console.WriteLine("双城记");

            List<string> words = TestHelper.ReadFile("测试文件1/双城记.txt");
            Console.WriteLine("总单词数：" + words.Count);

            Stopwatch t = new Stopwatch();

            LinkedList3Dictionary<string, int> dic = new LinkedList3Dictionary<string, int>();
            t.Start();

            foreach (var word in words)
            {
                if (!dic.ContainKey(word))
                    dic.Add(word, 1);
                else
                    dic.Set(word, dic.Get(word) + 1);
            }
            t.Stop();

            Console.WriteLine("不同单词的总数：" + dic.Count);
            Console.WriteLine("City出现的频次："+dic.Get("city"));
            Console.WriteLine("运行时间" + t.ElapsedMilliseconds);

            Console.ReadKey();

        }
    }
//映射

集合运行结果：

image.png

映射运行结果：

image.png