美文网首页
《数据结构与算法之美》04——链表

《数据结构与算法之美》04——链表

作者: 大杂草 | 来源:发表于2020-07-21 17:28 被阅读0次

链表：通过“指针”将一组零散的内存块串联起来使用。

数组vs链表

数组vs链表

三种常见的链表：单链表、双向链表、循环链表。

单链表：

单链表

时间复杂度：

  • 插入和删除：O(1)
  • 随机访问：O(n)

循环链表：

循环链表

一种特殊的单链表，跟单链表唯一的区别在尾结点：单链表尾结点是Null、循环链表尾结点指向头结点。

和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表。

时间复杂度：

  • 插入和删除：O(1)
  • 随机访问：O(n)

双向链表：

双向链表

通过额外空间来存储后继结点和前驱结点的地址。正是这种特点，使得双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。这里有个更加重要的知识点：用空间换时间。

双向循环链表：

双向循环链表

链表VS数组性能大比拼

链表VS数组性能大比拼
数据结构 优点 缺点
数组 简单易用；
可借助CPU的缓存机制；
访问效率更高；		 大小固定；
链表 大小没限制，支持动态扩容 对CPU缓存不好友，无法预读取；

如何实现LRU缓存淘汰算法

维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中，又可以分为两种情况：
  • 如果此时缓存未满，则将此结点直接插入到链表的头部；
  • 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

课后思考

如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？时间、空间复杂度是多少？

namespace PalindromeApp
{
    class Program
    {
        static void Main(string[] args)
        {
            string textA = "abcdcba";
            Console.WriteLine("{0}是否回文:{1}", textA, IsPalindrome(Init(textA)));
 
            string textB = "abcddcba";
            Console.WriteLine("{0}是否回文:{1}", textB, IsPalindrome(Init(textB)));
 
            string textC = "abedcba";
            Console.WriteLine("{0}是否回文:{1}", textC, IsPalindrome(Init(textC)));
 
            Console.Read();
        }
 
        static MyLinkedNode Init(string text)
        {
            MyLinkedNode head = new MyLinkedNode('&');
 
            MyLinkedNode curr = head;
 
            foreach (char c in text)
            {
                curr.Next = new MyLinkedNode(c);
                curr = curr.Next;
            }
 
            return head;
        }
 
        static MyLinkedNode Reverse(MyLinkedNode head)
        {
            MyLinkedNode reversed = null;
 
            MyLinkedNode curr = head.Next;
 
            while (curr != null)
            {
                MyLinkedNode node = new MyLinkedNode(curr.Data);
 
                node.Next = reversed;
                reversed = node;
 
                curr = curr.Next;
            }
 
            MyLinkedNode reversedHead = new MyLinkedNode('&');
            reversedHead.Next = reversed;
 
            return reversedHead;
        }
 
        static bool IsPalindrome(MyLinkedNode head)
        {
            MyLinkedNode reversed = Reverse(head);
 
            Show(head);
            Show(reversed);
 
            MyLinkedNode curr = head.Next;
            MyLinkedNode reversedCurr = reversed.Next;
 
            while (curr != null && reversedCurr != null)
            {
                if (curr.Data != reversedCurr.Data)
                {
                    return false;
                }
 
                curr = curr.Next;
                reversedCurr = reversedCurr.Next;
            }
 
            if (curr != null || reversedCurr != null)
            {
                return false;
            }
 
            return true;
        }
 
 
 
        static void Show(MyLinkedNode head)
        {
            MyLinkedNode curr = head.Next;
 
            string msg = "序列：";
 
            while (curr != null)
            {
                if (curr.Data == -1)
                {
                    break;
                }
 
                msg += curr.Data;
 
                curr = curr.Next;
            }
 
            Console.WriteLine(msg);
        }
    }
 
 
    public class MyLinkedNode
    {
        public MyLinkedNode(char data)
        {
            Data = data;
        }
 
        public char Data { get; set; }
 
        public MyLinkedNode Next { get; set; }
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

示例下载

写链表代码六个技巧

**技巧一：理解指针或引用的含义 **

指针：将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

技巧二：警惕指针丢失和内存泄漏

插入结点时，一定要注意操作的顺序；删除链表结点时，也一定要记得手动释放内存空间（对于有自动管理内存的编程语言来说，就不需要考虑这么多了）

技巧三：利用哨兵简化实现难度

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。

带头链表

技巧四：重点留意边界条件处理

检查点：

  • 如果链表为空时，代码是否能正常工作？
  • 如果链表只包含一个结点时，代码是否能正常工作？
  • 如果链表只包含两个结点时，代码是否能正常工作？
  • 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

技巧五：举例画图，辅助思考

技巧六：多写多练，没有捷径

5个常见的链表操作

1、单链表反转

解题思路：遍历结点，把当前结点插入到头结点，并对受影响的结点（前结点、原头部结点等）的Next重新设置。

public class ReversedLinkedList
    {
        public static void Run()
        { 
            // 空链表
            MyLinkedNode empty = Init(new int[] { });
            Console.WriteLine("初始链表：");
            Show(empty);
            Console.WriteLine("反转链表：");
            Show(Reversed(empty));
 
            // 单结点
            MyLinkedNode single = Init(new int[] { 1 });
            Console.WriteLine("初始链表：");
            Show(single);
            Console.WriteLine("反转链表：");
            Show(Reversed(single));
            
 
            // 正常链表
            MyLinkedNode normal = Init(new int[] { 1, 2, 3, 4, 5, 6, 7 });
            Console.WriteLine("初始链表：");
            Show(normal);
            Console.WriteLine("反转链表：");
            Show(Reversed(normal));
        }
 
        /// <summary>
        /// 初始化链表
        /// </summary>
        /// <param name="datas"></param>
        /// <returns></returns>
        public static MyLinkedNode Init(int[] datas)
        {
            MyLinkedNode head = new MyLinkedNode(-1);
            MyLinkedNode curr = head;
 
            for (int i = 0; i < datas.Length; i++)
            {
                var node = new MyLinkedNode(datas[i]);
 
                curr.Next = node;
                curr = node;
            }
 
            return head;
        }
 
        public static MyLinkedNode Reversed(MyLinkedNode head)
        {
            if (head == null || head.Next == null)
            {
                return head;
            }
 
            // 首结点不用操作，从第二个结点开始
            MyLinkedNode curr = head.Next.Next;
            MyLinkedNode prev = head.Next;
 
            while (curr != null)
            {
                MyLinkedNode node1 = head.Next;
                MyLinkedNode node2 = curr.Next;
 
                // 将当前结点插入到头结点
                head.Next = curr;
                // 将当前结点的Next设置为原来的头结点，插入头结点完成
                curr.Next = node1;
                // 前结点的Next设置为当前结点的原Next，把当前结点的后续结点链接起来
                prev.Next = node2;
 
                // 当前结点移动到下一结点
                curr = prev.Next;
            }
 
            return head;
        }
 
        public static void Show(MyLinkedNode head)
        {
            MyLinkedNode curr = head.Next;
 
            string msg = "序列：";
 
            while (curr != null)
            {
                msg += string.Format("{0} ", curr.Data);
                curr = curr.Next;
            }
 
            Console.WriteLine(msg);
        }
 
        public class MyLinkedNode
        {
            public MyLinkedNode(int data)
            {
                Data = data;
            }
 
            public int Data { get; set; }
 
            public MyLinkedNode Next { get; set; }
        }
    }
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

2、链表中环的检测

解题思路：设置两个步长，分别+1和+2，当出现结点相同时，表示有环。

类比，有两个跑步运动员A和B，分别以1m/s和2m/s的速度在同一个跑道上跑步，当B能追上A时，表示跑道是环，如果B不能追上A，表示非环。

public class CircleLinkedList
    {
        public static void Run()
        {
            // 空链表
            MyLinkedNode empty = Init(new int[] { }, false);
            Console.WriteLine("是否环：{0}", IsCircle(empty));
 
            // 单结点
            MyLinkedNode single = Init(new int[] { 1 }, false);
            Console.WriteLine("是否环：{0}", IsCircle(single));
 
            // 非环
            MyLinkedNode notcircle = Init(new int[] { 1, 2, 3, 4, 5 }, false);
            Console.WriteLine("是否环：{0}", IsCircle(notcircle));
 
            // 环
            MyLinkedNode circle = Init(new int[] { 1, 2, 3, 4, 5 }, true);
            Console.WriteLine("是否环：{0}", IsCircle(circle));
        }
 
        /// <summary>
        /// 初始化链表
        /// </summary>
        /// <param name="datas"></param>
        /// <returns></returns>
        public static MyLinkedNode Init(int[] datas, bool circle)
        {
            MyLinkedNode head = new MyLinkedNode(-1);
            MyLinkedNode curr = head;
 
            //int[] datas = new int[] { 1, 2, 3, 4, 5 };
            for (int i = 0; i < datas.Length; i++)
            {
                var node = new MyLinkedNode(datas[i]);
 
                curr.Next = node;
                curr = node;
            }
 
            if (circle)
            {
                curr.Next = head.Next;
            }
 
            return head;
        }
 
        public static bool IsCircle(MyLinkedNode head)
        {
            // 当链表为空或者只有一个结点时，返回false
            if (head == null || head.Next == null || head.Next.Next == null)
            {
                return false;
            }
 
            MyLinkedNode stepA = head.Next;
            MyLinkedNode stepB = head.Next.Next;
 
            while (stepA != null && stepB != null)
            {
                if (stepA == stepB)
                {
                    return true;
                }
 
                // 设置步长+1
                stepA = stepA.Next;
 
                // 当下一下结点为Null，结束循环，跳出
                if (stepB.Next == null)
                {
                    break;
                }
                else
                {
                    // 设置步长+2
                    stepB = stepB.Next.Next;
                }
            }
 
            return false;
        }
 
        public static void Show(MyLinkedNode head)
        {
            MyLinkedNode curr = head.Next;
 
            string msg = "序列：";
 
            while (curr != null)
            {
                msg += string.Format("{0} ", curr.Data);
                curr = curr.Next;
            }
 
            Console.WriteLine(msg);
        }
 
        public class MyLinkedNode
        {
            public MyLinkedNode(int data)
            {
                Data = data;
            }
 
            public int Data { get; set; }
 
            public MyLinkedNode Next { get; set; }
        }
    }
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

3、两个有序的链表合并

解题思路：遍历两个链表，把结点往新链表尾部插入。当某个链表遍历完，把另一个链表直接插入到新链表的尾部。

/// <summary>
/// 两个有序的链表合并
/// </summary>
public class MergeLinkedList
{
 
    public static void Run()
    {
        // 两个为空链表
        MyLinkedNode emptyA = Init(new int[] { });
        MyLinkedNode emptyB = Init(new int[] { });
        Show(Merge(emptyA, emptyB));
 
        // 一个为空链表
        MyLinkedNode emptyC = Init(new int[] { });
        MyLinkedNode linkedD = Init(new int[] { 1, 2, 4, 5, 6 });
        Show(Merge(emptyC, linkedD));
 
        // 两个非空链表
        MyLinkedNode linkedE = Init(new int[] { 1, 3, 4, 5, 9, 10 });
        MyLinkedNode linkedF = Init(new int[] { 2, 3, 5, 6, 7, 8 });
        Show(Merge(linkedE, linkedF));
    }
 
    /// <summary>
    /// 初始化链表
    /// </summary>
    /// <param name="datas"></param>
    /// <returns></returns>
    private static MyLinkedNode Init(int[] datas)
    {
        MyLinkedNode head = new MyLinkedNode(-1);
        MyLinkedNode curr = head;
 
        foreach (var data in datas)
        {
            var node = new MyLinkedNode(data);
 
            curr.Next = node;
            curr = node;
        }
 
        return head;
    }
 
    private static MyLinkedNode Merge(MyLinkedNode headA, MyLinkedNode headB)
    {
        if (headA == null || headA.Next == null)
        {
            return headB;
        }
 
        if (headB == null || headB.Next == null)
        {
            return headA;
        }
 
        MyLinkedNode head = new MyLinkedNode(-1);
        MyLinkedNode curr = head;
 
        MyLinkedNode currA = headA.Next;
        MyLinkedNode currB = headB.Next;
 
        while (currA != null && currB != null)
        {
            if (currA.Data <= currB.Data)
            {
                curr.Next = currA;
                currA = currA.Next;
            }
            else
            {
                curr.Next = currB;
                currB = currB.Next;
            }
 
            curr = curr.Next;
            curr.Next = null;
        }
 
        curr.Next = currA ?? currB;
 
        return head;
    }
 
    private static void Show(MyLinkedNode head)
    {
        MyLinkedNode curr = head.Next;
 
        string msg = "序列：";
 
        while (curr != null)
        {
            msg += string.Format("{0} ", curr.Data);
            curr = curr.Next;
        }
 
        Console.WriteLine(msg);
    }
 
 
    public class MyLinkedNode
    {
        public MyLinkedNode(int data)
        {
            Data = data;
        }
 
        public int Data { get; set; }
 
        public MyLinkedNode Next { get; set; }
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

4、删除链表倒数第n个结点

解题思路：反转链表，遍历到第n-1个结点，链接到第n+1个结点（即删除第n个结点），再反转链表。

public class RemoveLinkedList
{
    public static void Run()
    {
        // 删除第4个结点，即下标是3的结点
        int index = 3;
 
        // 空链表
        MyLinkedNode empty = Init(new int[] { });
        Console.Write("初始链表");
        Show(empty);
        Console.WriteLine("删除倒数第{0}个结点：{1}", index + 1, RemoveAt(empty, index));
        Show(empty);
 
        // 单结点
        MyLinkedNode single = Init(new int[] { 1 });
        Console.Write("初始链表");
        Show(single);
        Console.WriteLine("删除倒数第{0}个结点：{1}", index + 1, RemoveAt(single, index)); 
        Show(single);
 
 
        // 正常链表
        MyLinkedNode normal = Init(new int[] { 1, 2, 3, 4, 5, 6, 7 });
        Console.Write("初始链表");
        Show(normal);
        Console.WriteLine("删除倒数第{0}个结点：{1}", index + 1, RemoveAt(normal, index)); 
        Show(normal);
    }
 
    /// <summary>
    /// 初始化链表
    /// </summary>
    /// <param name="datas"></param>
    /// <returns></returns>
    private static MyLinkedNode Init(int[] datas)
    {
        MyLinkedNode head = new MyLinkedNode(-1);
        MyLinkedNode curr = head;
 
        for (int i = 0; i < datas.Length; i++)
        {
            var node = new MyLinkedNode(datas[i]);
 
            curr.Next = node;
            curr = node;
        }
 
        return head;
    }
 
    private static bool RemoveAt(MyLinkedNode head, int index)
    {
        var reversed = Reversed(head);
 
        int count = 0;
 
        MyLinkedNode curr = reversed.Next;
 
        while (curr != null)
        {
            count++;
 
            if (count == index)
            {
                curr.Next = curr.Next.Next;
                break;
            }
 
            curr = curr.Next;
        }
 
        head = Reversed(reversed);
 
        return count >= index;
    }
 
    private static MyLinkedNode Reversed(MyLinkedNode head)
    {
        if (head == null || head.Next == null)
        {
            return head;
        }
 
        // 首结点不用操作，从第二个结点开始
        MyLinkedNode curr = head.Next.Next;
        MyLinkedNode prev = head.Next;
 
        while (curr != null)
        {
            MyLinkedNode node1 = head.Next;
            MyLinkedNode node2 = curr.Next;
 
            // 将当前结点插入到头结点
            head.Next = curr;
            // 将当前结点的Next设置为原来的头结点，插入头结点完成
            curr.Next = node1;
            // 前结点的Next设置为当前结点的原Next，把当前结点的后续结点链接起来
            prev.Next = node2;
 
            // 当前结点移动到下一结点
            curr = prev.Next;
        }
 
        return head;
    }
 
    private static void Show(MyLinkedNode head)
    {
        MyLinkedNode curr = head.Next;
 
        string msg = "序列：";
 
        while (curr != null)
        {
            msg += string.Format("{0} ", curr.Data);
            curr = curr.Next;
        }
 
        Console.WriteLine(msg);
    }
 
    public class MyLinkedNode
    {
        public MyLinkedNode(int data)
        {
            Data = data;
        }
 
        public int Data { get; set; }
 
        public MyLinkedNode Next { get; set; }
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

5、求链表的中间结点

解题思路：遍历一次，计算链表元素个数，然后算出中间结点的下标，转为获取第N个结点。

public class MiddleLinkedList
{
    public static void Run()
    {
        MyLinkedNode middleNode = null;
 
        // 空链表
        MyLinkedNode empty = Init(new int[] { });
        Console.Write("初始链表");
        Show(empty);
        middleNode = GetMiddleNode(empty);
        Console.WriteLine("中间结点：{0}", middleNode == null ? "null" : middleNode.Data.ToString());
 
        // 单结点
        MyLinkedNode single = Init(new int[] { 1 });
        Console.Write("初始链表");
        Show(single);
        middleNode = GetMiddleNode(single);
        Console.WriteLine("中间结点：{0}", middleNode == null ? "null" : middleNode.Data.ToString());
 
 
        // 单数链表
        MyLinkedNode odd = Init(new int[] { 1, 2, 3, 4, 5, 6, 7 });
        Console.Write("初始链表");
        Show(odd);
        middleNode = GetMiddleNode(odd);
        Console.WriteLine("中间结点：{0}", middleNode == null ? "null" : middleNode.Data.ToString());
 
        // 双数链表
        MyLinkedNode even = Init(new int[] { 1, 2, 3, 4, 5, 6, 7, 8 });
        Console.Write("初始链表");
        Show(even);
        middleNode = GetMiddleNode(even);
        Console.WriteLine("中间结点：{0}", middleNode == null ? "null" : middleNode.Data.ToString());
    }
 
    /// <summary>
    /// 初始化链表
    /// </summary>
    /// <param name="datas"></param>
    /// <returns></returns>
    private static MyLinkedNode Init(int[] datas)
    {
        MyLinkedNode head = new MyLinkedNode(-1);
        MyLinkedNode curr = head;
 
        for (int i = 0; i < datas.Length; i++)
        {
            var node = new MyLinkedNode(datas[i]);
 
            curr.Next = node;
            curr = node;
        }
 
        return head;
    }
 
    private static MyLinkedNode GetMiddleNode(MyLinkedNode head)
    {
        if (head == null || head.Next == null)
        {
            return null;
        }
 
        int count = 0;
 
        MyLinkedNode curr = head.Next;
 
        while (curr != null)
        {
            count++;
 
            curr = curr.Next;
        }
 
        curr = head;
 
        int middleIndex = count == 1 ? 0 : (count - 1) / 2;
 
        while (middleIndex >= 0)
        {
            middleIndex--;
            curr = curr.Next;
        }
 
        //for (int i = 0; i <= middleIndex; i++)
        //{
        //    curr = curr.Next;
        //}
 
        return curr;
    }
 
    private static void Show(MyLinkedNode head)
    {
        MyLinkedNode curr = head.Next;
 
        string msg = "序列：";
 
        while (curr != null)
        {
            msg += string.Format("{0} ", curr.Data);
            curr = curr.Next;
        }
 
        Console.WriteLine(msg);
    }
 
    public class MyLinkedNode
    {
        public MyLinkedNode(int data)
        {
            Data = data;
        }
 
        public int Data { get; set; }
 
        public MyLinkedNode Next { get; set; }
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

课后思考

今天我们讲到用哨兵来简化编码实现，你是否还能够想到其他场景，利用哨兵可以大大地简化编码难度？

哨兵有点像中间件的味道，在两个系统或模块之间的调用时，有时候通过中间件能够简化两边的技术实现差异。

相关文章

  • 数据结构与算法

    数据结构与算法之美 数据结构与算法之美1--如何学数据结构与算法之美2--复杂度分析（上）数据结构与算法之美3--...

  • 算法的复杂度分析

    本文是对极客时间《数据结构与算法之美》03-04 节课关于算法复杂度分析的小结。 前面：为什么要学习数据结构与算法...

  • 02.数据结构之链表篇

    文章为极客时间《数据结构与算法之美》的学习笔记。学习要点：空间换时间的设计思想。 什么是链表？ 链表通过指针将一组...

  • 《数据结构与算法之美》04——链表

    链表：通过“指针”将一组零散的内存块串联起来使用。 数组vs链表 三种常见的链表：单链表、双向链表、循环链表。 单...

  • 重温：数据结构与算法 - 03数组

    数据结构与算法之美 - 数组 数据结构与算法之美-学习大纲 什么数组？ 数组是一种 线性表 数据结构。它用一组 连...

  • 20181111_ARTS_W6

    第六周arts Algorithm 看专栏《数据结构与算法之美》遇到的一道算法题：题目描述：给定一个单链表连接的字...

  • 数据结构和算法（三）双向链表与双向循环链表的实现

    数据结构和算法（一）线性表实现 数据结构和算法（二）单向循环链表的创建插入删除实现 数据结构和算法（三）双向链表与...

  • 数据结构和算法（五）栈的操作和实现

    数据结构和算法（一）线性表实现 数据结构和算法（二）单向循环链表的创建插入删除实现 数据结构和算法（三）双向链表与...

  • 数据结构和算法（四）链表相关面试题

    数据结构和算法（一）线性表实现 数据结构和算法（二）单向循环链表的创建插入删除实现 数据结构和算法（三）双向链表与...

  • 数据结构和算法（6）队列的操作和实现

    数据结构和算法（1）线性表实现 数据结构和算法（2）单向循环链表的创建插入删除实现 数据结构和算法（3）双向链表与...

网友评论

      本文标题：《数据结构与算法之美》04——链表

      本文链接：https://www.haomeiwen.com/subject/hikwkktx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|《数据结构与算法之美》04——链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！