这一弹，让我重新认识数据结构与算法的重要性，正是前面所说过，只有熟悉底层原理，才能很好的掌舵，让上层（灵活变通）写出高效的代码。也许很多时候开发起来，感觉不到这一点，那最重要还是自己练习少了，或者涉及这方面的算法几乎可以忽略，当然更多的还是活在“别人的开发中”。

好了，说正事，这次题说的数据结构中的链表，它是一种动态数据结构，在创建链表时无需指定链表的长度，插入数据时动态调整内存分配，因此没有闲置的内存，所以链表比数组空间效率高，但是链表无法保证内存存储数据是连续的，从链表中找数据，每次都要从头部节点开始循环找，所以相比数组的时间复杂度O（1）要大，所以它的时间复杂度与链表中的结点有关，因此链表的时间复杂度为O（n）！

问题描述：从尾到头打印链表

这题看上去很简单，实现方式各种各样，但是换个角度去思考这个问题，针对某一个点去解决，而不是为了强行去实现这个功能，否则就失去了题目本身的意义了！

在C#中List<T>泛型集合就是一个链表的存储结构，泛型集合也比较灵活，那就通过它为这题提供链表，要求反向打印链表中数据，这个特点正好符合栈（后进先出）的特性，那就可以用栈来实现这样的打印顺序了，遍历链表中数据一个个写入栈中，然后遍历栈一次打印输出，这种实现思路清晰简单，那就要看自己能不能把题目要求的特点分析出来，实现代码：

 /// <summary>
        /// 将list集合数据依次入栈
        /// </summary>
        /// <param name="list"></param>
        static void ListToStack(List<int> list)
        {
            Stack<int> s = null;
            if (list != null && list.Count > 0)
            {
                s = new Stack<int>();
                foreach (var item in list)
                {
                    s.Push(item);
                }
                foreach (var item in s)
                {
                    Console.WriteLine(item);
                }
            }
        }

对于“后进先出”这一特点，可以联想到递归，因为递归的本质也是一种栈结构，于是很自然的又想到用递归来实现此算法，那么可以在打印链表中结点的时候，可以先去递推打印它的下一结点，最后依次回归打印，就实现了反向打印链表，具体实现代码：

 /// <summary>
        /// 递归实现后进先出
        /// </summary>
        /// <param name="list"></param>
        /// <param name="i"></param>
        static void RevWriteList(List<int> list ,int i=0)
        {
            if(list!=null)
            {
                if(i<list.Count)
                {
                    if(++i<list.Count)
                    {
                        RevWriteList(list, i);
                    }
                    
                    Console.WriteLine(list[--i]);
                }
            }
        }

上面也说到重点不在于实现功能，其功能的实现都是相对于某个点来的，那么就上面两种解法，以时间效率这个点来说，到底谁强谁弱，不好直接妄下定论，那么就交给数据来定夺吧！

首先，往链表中提供6条数据，具体计算代码：

 List<int> list = new List<int>();
            list.Add(1);
            list.Add(2);
            list.Add(3);
            list.Add(4);
            list.Add(5);
            list.Add(6);
            sw.Start();
            ListToStack(list);
            sw.Stop();
            Console.WriteLine("\r\n直接用栈耗时：{0}", sw.Elapsed);
            sw.Restart();
            RevWriteList(list);
            sw.Stop();
            Console.WriteLine("\r\n用递归实现栈的特点耗时：{0}", sw.Elapsed);

代码中分别计算了直接通过栈实现和用递归来实现所需要的时间。具体运行结果：

       很明显的看到两者的差别，用递归来实现远远甩直接用栈好几条街，这是为什么呢，自己简单的分析了下原因，用栈实现时，需要 new Stack<int>()开辟空间，然后把数据取出来一个个入栈，我想就是这里相对耗时要多点，而对于递归，并没有开辟内存空间这些操作，所以这里递归乐胜一筹！

接下来，尝试把链表中数据添加足够多些（比如再加100条数据），在来执行如上代码，结果显示：

很清楚的发现，递归耗时慢慢会超越直接用栈的耗时。怎么一下子剧情又扭转了呢，这就是递归算法本身的原因了，虽然递归来实现，代码干净整洁（牛逼），但它也是有瓶颈的，如果链表的结点过多之后，会导致函数调用层级过深，从而可能导致函数调用栈溢出！所以具体是否用递归是环境所定，不过一般不提倡用递归算法设计程序，因为在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储！

总结，任何问题的存在，都是具有意义效应的，否则都是浮云！

发表吐槽