36.List是链表还是数组

面试题 > 编程语言面试题 > CSharp面试题面试题编程语言面试题 CSharp面试题

发布时间 : 1801-01-01 00:03

字数:475 阅读 :

评论:

36.List是链表还是数组

36.List是链表还是数组

36.1 题目

List是链表还是数组？

36.2 深入解析

List<T> 在 C# 中由动态数组（内部 T[]）实现，并非 LinkedList<T> 那样的链表。容量不足时会扩容并复制元素；随机访问为 O(1)，但在中间位置插入/删除需移动后续元素，一般为 **O(n)**，与链表在头尾指针已知时的插入代价不同，不宜说“和链表一样高效”。

虽然List的内部实现是数组，但其提供了一系列的方法和属性，使得其用起来更像是一个动态数组而非传统的链表。因此，虽然名称上可能会让人误以为List是链表，但实际上它是基于数组实现的动态容器。

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        // 创建一个List<int>对象
        List<int> myList = new List<int>();

        // 向List中添加元素
        myList.Add(1);
        myList.Add(2);
        myList.Add(3);

        // 遍历List并打印元素
        foreach (int num in myList)
        {
            Console.WriteLine(num);
        }
    }
}

上述示例演示了如何使用List，并在注释中添加了对代码的说明。

36.3 答题示例

“C# 中的 List<T> 并不是链表，而是基于数组实现的动态容器。它在内部维护一个数组，当容量不足时会自动扩容（通常翻倍），以支持动态添加元素。这样，List<T> 既能像数组一样提供 O(1) 随机访问，又能通过扩容机制实现动态增长，但插入或删除中间元素依然需要移动后续元素，开销为 O(n)。”

36.4 关键词联想

动态数组
底层 T[] _items
自动扩容（Capacity Doubling）
O(1) 随机访问
O(n) 插入/删除（移位）
Count vs Capacity
EnsureCapacity
不同于 LinkedList

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com