深度解析C#中LinkedList<T>的存储结构

合集 - C#数据结构分析(4)

1.C#中Dictionary的存储结构分析2023-11-142.深度分析C#中Array的存储结构2023-11-213.深入解析C#中List的存储结构2023-11-30

4.深度解析C#中LinkedList的存储结构2023-12-05

收起

　　本文承接前面的3篇有关C#的数据结构分析的文章，对于C#有关数据结构分析还有一篇就要暂时结束了，这个系列主要从Array、List、Dictionary、LinkedList、 SortedSet等5中不同类型进行介绍和分析。废话不多说，接下来我们来最后看一下这个系列的最后一种数据类型"链表"。

　　提到链表这个数据结构可能大部分同学都不会感到陌生，但是在.NET中使用LinkedList  这个集合的同学可能就不会很多，因为绝大部分的场景中大部分同学会直接使用List、Dictionary数据结构，这次我们就来借助本文对.NET的LinkedList集合进行一个全面的了解。

　　本文将从链表的基础特性、C#中LinkedList的底层实现逻辑，.NET的不同版本对于Queue的不同实现方式的原因分析等几个视角进行简单的解读。

一、链表的基础特性

　　 数组需要一块连续的内存空间来存储，对内存的要求比较高。链表并不需要一块连续的内存空间，通过“指针”将一组零散的内存块串联起来使用。链表的节点可以动态分配内存，使得链表的大小可以根据需要动态变化，而不受固定的内存大小的限制。特别是在需要频繁的插入和删除操作时，链表相比于数组具有更好的性能。最常见的链表结构分别是：单链表、双向链表和循环链表。

　　　　1、链表的基本单元是节点，每个节点包含两个部分：

　　　　　　(1)、数据(Data)：存储节点所包含的信息。

　　　　　　(2)、引用(Next)：指向下一个节点的引用，在双向链表中，包含指向前一个节点的引用。

　　　　2、链表的基本类型，主要包含三种类型：

　　　　　　(1)、单链表（Singly Linked List）：每个节点只包含一个指向下一个节点的引用。

　　　　　　　　(a)、【时间复杂度】头部插入/删除：O(1)；尾部插入：O(n) ；中间插入/删除：O(n) 。

　　　　　　　　(b)、【时间复杂度】按值查找：O(n) （需要遍历整个链表）；按索引查找：O(n) 。

　　　　　　　　(c)、【空间复杂度】插入和删除：O(1)；查找：O(1)。

　　　　　　(2)、双链表（Doubly Linked List）：每个节点包含两个引用，一个指向下一个节点，一个指向前一个节点。

　　　　　　　　(a)、【时间复杂度】头部插入/删除：O(1)；尾部插入/删除：O(1)；中间插入/删除：O(n) 。

　　　　　　　　(b)、【时间复杂度】按值查找：O(n) ；按索引查找：O(n) 。

　　　　　　　　(c)、【空间复杂度】O(n)。

　　　　　　(3)、循环链表： 尾节点的引用指向头节点，形成一个闭环。

　　　　　　　　(a)、【时间复杂度】头部插入/删除：O(1)；尾部插入/删除：O(1)；中间插入/删除：O(n) 。

　　　　　　　　(b)、【时间复杂度】按值查找：O(n) ；按索引查找：O(n) 。

　　　　　　　　(c)、【空间复杂度】O(n)。

　　 以上简单的介绍了链表的基础特性、分类、对应的时间复杂度和空间复杂度，双链表虽然比较耗费内存，但是其在插入、删除、有序链表查询方面相对于单链表有明显的优先，这一点充分的体现了算法上的"用空间换时间"的设计思想。

二、LinkedList数据存储

　　 LinkedList 是 C# 中提供的一个双向链表（doubly linked list）实现，用于存储元素。双向链表的每个节点都包含对前一个节点和后一个节点的引用，这种结构使得在链表中的两个方向上进行遍历和操作更为方便。

　　　1、节点结构

    public sealed class LinkedListNode
    {
        internal LinkedList? list;
        internal LinkedListNode? next;
        internal LinkedListNode? prev;
        internal T item;
        ...
        public LinkedListNode(T value)
        {
            Value = value;
            Previous = null;
            Next = null;
        }
    }

　　以上的代码展示了在C#的 LinkedList的节点的存储结构，表示双向链表中的一个节点。 LinkedList 中的每个节点都是一个包含元素值和两个引用的对象。list是一个对包含该节点的 LinkedList 的引用。这个引用使得节点能够访问链表的一些信息，例如头节点、尾节点等。next是一个对下一个节点的引用。prev是一个对前一个节点的引用。item存储节点的值。

　　其实看到这个地方，可能有部分同学会产生疑问，为什么这个节点的数据结构不设计为"结构体"，而是设计为一个类，结构体在内存占用方面更有优势。在这里为什么设计为，可能有以下几种综合考虑。

　　　　1、引用语义：类型的实例具有引用语义，当传递或赋值对象时，传递或赋值的是对象的引用，同一对象的修改在所有引用该对象都是可见的。

　　　　2、复杂性和生命周期：如果类型具有较复杂的生命周期或包含对其他资源（如其他对象、文件句柄等）的引用，通常会选择类而不是结构体。结构体适用于轻量级、简单的值类型，而类则更适合处理更复杂、具有引用语义的情况。

　　　　3、可空性：类可以使用 null 表示空引用，结构体不能。

　　　　4、性能和拷贝开销：结构体通常会被复制，类则是通过引用传递。

　　对于以上的结构设计复杂度并不高，我们从整体的设计视角考虑这个结构设计为"结构体"和"类"，哪一种更加有优势，我们在以后的系统开发过程中，也需要综合去思考，没有一种结构是完美的，每一种结构都有其针对性的优势。

　　2、链表头和尾

public class LinkedList : ICollection, ...
{
    public LinkedListNode First { get; }
    public LinkedListNode Last { get; }
    ...
}

　　LinkedList 本身维护了对链表头和尾的引用，分别指向第一个节点（头节点）和最后一个节点（尾节点）。通过将链表的节点（LinkedListNode）作为LinkedList 类的私有成员，可以隐藏链表节点的实现细节，提供更好的封装性。外部用户只需关注链表的公共接口而不需要了解节点的具体结构。并且可以更容易地扩展和维护链表的功能、可以控制对节点的访问权限、对链表的操作会影响到同一个链表的所有引用、可以表示空链表等优势。

三、LinkedList数据读写

　　上文中我看分析了链表的存储结构LinkedListNode和LinkedList。接下来，我们再来看一下链表LinkedList元素的维护和查询等基础操作的实现逻辑。首先我们来看一下元素的添加操作，Add()方法用于将一个元素添加到集合中，其内部的核心实现方法为AddLast()，我们接下来具体看一下这个方法的内部实现。【源码进行了部分删减】。

        public LinkedListNode AddLast(T value)
        {
            LinkedListNode result = new LinkedListNode(this, value);
            
            //区分链表为空和非空的场景
            if (head == null)
            {
                InternalInsertNodeToEmptyList(result);
            }
            else
            {
                InternalInsertNodeBefore(head, result);
            }
            return result;
        }

　　以上代码展示了AddLast()的实现代码，这个方法是在双向链表的末尾添加一个新节点的操作，并根据链表是否为空采取不同的插入策略，确保插入操作的有效性，并返回了对新插入节点的引用。这里做为空和非空的场景区分是因为在双向链表中，头节点 head 的前一个节点是尾节点，而尾节点的下一个节点是头节点。因此，在链表为空的情况下，头节点即是尾节点，直接插入新节点即可。而在链表不为空的情况下，需要在头节点之前插入新节点，以保持链表的首尾相连。接下来我们分别来看一下InternalInsertNodeToEmptyList()和InternalInsertNodeBefore()方法。

        private void InternalInsertNodeToEmptyList(LinkedListNode newNode)
        {
            //用于确保在调用此方法时链表必须为空。
            Debug.Assert(head == null && count == 0, "LinkedList must be empty when this method is called!");
            
            //将新节点的 next 指向自身
            newNode.next = newNode;  
            
            //将新节点的 prev 指向自身
            newNode.prev = newNode; 
             
            //将链表的头节点指向新节点
            head = newNode; 
              
            //增加链表的版本号       
            version++;
                  
            //增加链表中节点的数量         
            count++;                 
        }

　　InternalInsertNodeToEmptyList()实现了在空链表中插入新节点的逻辑。在空链表中，新节点是唯一的节点，因此它的 next和prev都指向自身。新节点同时是头节点和尾节点。

        private void InternalInsertNodeBefore(LinkedListNode node, LinkedListNode newNode)
        {
            //新节点newNode的next引用指向目标节点node，
            //确保新节点newNode的next指向原来在链表中的位置。
            newNode.next = node;
            
            //新节点newNode的prev引用指向目标节点node的前一个节点，
            //在插入操作中保持链表的连接关系，确保newNode的前一个节点正确。
            newNode.prev = node.prev;
            
            //目标节点node前一个节点的next引用指向新节点newNode，新节点newNode插入完成
            node.prev!.next = newNode;
            
            //目标节点node的prev引用指向新节点newNode，
            //链表中目标节点node的前一个节点变成了新插入的节点newNode。
            node.prev = newNode;
            
            //用于追踪链表的结构变化，通过每次修改链表时增加 
            //version的值，可以在迭代过程中检测到对链表的并发修改。
            version++;
            count++;
        }

　　InternalInsertNodeBefore()用于实现链表中在指定节点前插入新节点,保证了插入操作的正确性和一致性，确保链表的连接关系和节点计数正确地维护。上面的代码已经做了逻辑说明。node.prev!.next = newNode;中的!确保在链表中插入新节点时，前一个节点不为 null，以防止潜在的空引用异常。版本号的增加是为了在并发操作中提供一种机制，使得在迭代过程中能够检测到链表的结构变化。这对于多线程环境下的链表操作是一种常见的实践，以避免潜在的并发问题。

　　上面我们介绍了LinkedList 的InternalInsertNodeToEmptyList()和InternalInsertNodeBefore()方法，用于向链表插入元素。接下来，我们再来具体看看链表的元素查询的实现逻辑，LinkedList 实现元素的方法是Find()。

        public LinkedListNode? Find(T value)
        {
            LinkedListNode? node = head;
            EqualityComparer c = EqualityComparer.Default;
            if (node != null)
            {
                if (value != null)
                {
                     // 查找非空值的节点
                    do
                    {
                        if (c.Equals(node!.item, value))
                        {
                            return node;
                        }
                        node = node.next;
                    } while (node != head);
                }
                else
                {
                    // 查找空值的节点
                    do
                    {
                        if (node!.item == null)
                        {
                            return node;
                        }
                        node = node.next;
                    } while (node != head);
                }
            }
            // 未找到节点
            return null;
        }

　　通过循环遍历链表中的每个节点，根据节点的值与目标值的比较，找到匹配的节点并返回。在链表中可能存在包含 null 值的节点，也可能存在包含非空值的节点，而这两种情况需要采用不同的比较方式。LinkedListNode? node = head; 初始化一个节点引用 node，开始时指向链表的头节点head。使用了do-while 循环确保至少执行一次，即使链表为空。为了防止潜在的空引用异常，使用了! 操作符来断言节点 node 不为 null。Find()方法对于链表中值的查询的时间复杂度是O(n)。

　　上面介绍了链表元素的查询实现逻辑，接下来我们看一下链表元素的移除操作，在InternalRemoveNode()方法中实现。

        internal void InternalRemoveNode(LinkedListNode node)
        {
            if (node.next == node)
            {
                //将链表头head 设为null，表示链表为空。
                head = null;
            }
            else
            {
                //将目标节点node后一个节点的prev引用指向目标节点node的前一个节点。
                node.next!.prev = node.prev;
                
                //将目标节点node前一个节点的next引用指向目标节点node的后一个节点。
                node.prev!.next = node.next;
                
                if (head == node)
                {
                    //如果目标节点node是链表头节点head，则将链表头head设为目标节点node的下一个节点。
                    head = node.next;
                }
            }
            node.Invalidate();
            count--;
            version++;
        }

　　在双向链表中删除指定节点node，首先判断链表中是否只有一个节点。如果链表只有一个节点，那么删除这个节点后链表就为空。调用 Invalidate 方法，用于清除节点的 list、prev 和 next 引用，使节点脱离链表。version++增加链表的版本号，用于在并发迭代过程中检测链表结构的变化。

　　本节中主要介绍了链表的元素插入、元素的查询、元素的移除等操作，在不同的场景中，其实现的方式都存在着不同，在C#内部维护的链表结构相对简化，没有对其内部进行很强的优化，因此我们在实际的项目中对于链表的应用时，需要充分的分析使用的场景诉求进行调整优化。

四、Queue中链表与数组的实现对比

　　在整个.NET Core的数据结构体系中，数组占据了绝大部分的应用场景，对于链表的应用场景相对较少，但是链表也有其独特的结构，适用于对应的场景中。其实在 .NET Framework版本中，Queue 的底层实现确实使用了链表，而 Stack 的实现通常使用了动态数组。在当前.NET Core版本中，Queue 底层实现已经修改为基于Array数组来实现。对于Queue选择链表还是数组的底层实现方案，各有优劣势。我们借助一下.NET在对Queue的实现方式上的不同，来对比一下链表与数组的选择上的优劣势分析。

　　1、Queue使用链表的优劣势

　　　　1、使用链表的好处：

　　　　　　(1)、高效的插入和删除操作：在队尾和队头进行插入和删除操作更为高效，符合队列的典型操作。

　　　　　　(2)、不需要连续内存：链表不要求元素在内存中是连续存储的，这使得队列可以更灵活地分配和释放内存。

　　　　　　(3)、适用于频繁的入队和出队操作：链表在动态增长和缩减时的性能表现更好，适用于队列中频繁进行入队和出队操作的场景。

　　　　2、使用链表的劣势：

　　　　　　(1)、内存开销较大：每个节点需要额外的内存空间存储指向下一个节点的引用，可能会导致相对较大的内存开销。

　　　　　　(2)、随机访问性能差：链表不支持直接通过索引进行随机访问。

　　2、Queue使用数组的优劣势

　　　　1、使用数组的优势：

　　　　　　(1)、随机访问性能：数组提供了O(1)时间复杂度的随机访问，链表需要按顺序遍历到目标位置。

　　　　　　(2)、缓存友好性：数组在内存中是连续存储的，链表节点的存储是分散的。

　　　　　　(3)、空间效率：数组不需要额外的指向下一个节点的引用，具有更小的内存开销。

　　　　　　(4)、适用于特定访问模式：对于随机访问而非插入/删除操作，选择数组作为底层实现可能更合适。

　　　　2、使用数组的劣势：

　　　　　　(1)、插入和删除性能较差：数组在中间插入或删除元素的性能较差，因为需要移动元素以保持数组的顺序。

　　　　　　(2)、动态扩展的开销：如果队列的大小会动态变化，数组在动态扩展时可能会涉及到重新分配内存、复制元素的开销影响性能。

　　　　　　(3)、大队列的管理：对于大的队列，如果需要频繁进行动态扩展，可能会面临内存管理的挑战。

　　　　　　(4)、不适用于特定插入模式：如果主要操作是频繁的插入和删除而不是随机访问，选择数组作为底层实现可能不是最佳选择。

五、场景应用

　　文章开头介绍了链表的基础特性，基于链表的基础特性来展开分析C#的LinkedList结构，重点说明了LinkedList的元素插入、查询、移除和存储对象。链表在实际的应用中比较广泛，尤其是在缓存的处理方面。缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，FirstOut）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（LeastRecently Used）。

　　这里我们以简单实现方式说明一下LRU缓存的实现逻辑。

　　　　1、 如果此数据之前已经被缓存在链表中了，则遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。

　　　　2.、如果此数据没有在缓存链表中，则分为两种情况：

　　　　　　(1)、如果此时缓存未满，则将此结点直接插入到链表的头部；

　　　　　　(2)、如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

　　对于链表的基础应用场景中如：单链表反转；链表中环的检测；有序的链表合并等较为常用的算法。

 　   以上内容是对C#中LinkedList的存储结构的简单介绍，如错漏的地方，还望指正。

 

---

感谢您的阅读，如果您觉得阅读本文对您有帮助，请点一下“推荐”按钮。本文欢迎各位转载，但是转载文章之后必须在文章页面中给出作者和原文连接。如果需要获取最新的优秀.NET博文，请关注微信公众号“DotNet技术分享”。