欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构之Array、ArrayList、List、LinkedList对比分析

程序员文章站 2022-07-02 12:45:59
在c#数据结构中,集合的应用非常广泛,无论是做BS架构还是CS架构开发,都离不开集合的使用,比如我们常见的集合包括:Array、ArrayList、List、LinkedList等。这一些数据集合,在功能上都能够实现集合的存取,但是他们内部有什么区别,在使用时需要注意一些什么呢?下面根据个人的经验,... ......

一、前言:

  在c#数据结构中,集合的应用非常广泛,无论是做bs架构还是cs架构开发,都离不开集合的使用,比如我们常见的集合包括:array、arraylist、list、linkedlist等。这一些数据集合,在功能上都能够实现集合的存取,但是他们内部有什么区别,在使用时需要注意一些什么呢?下面根据个人的经验,对这一些集合数据的使用做一个简单的小结,如果说的不对的地方,欢迎指出,多多交流改进。

二、array集合简介

  array集合,也就是数组,是最简单的数据结构,其存储的数据在内存空间是连续的,数组有一下一些特点

  • 1.数据存储是连续的
  • 2.数组长度在定义时就必须制定
  • 3.数组存储的数据类型都是同一类型
  • 4.数组可以直接通过小标访问

  优缺点:
   优点:
  1、可以根据索引直接访问,访问速度快
   2、数据是安全的,由于数据类型一致性,在存储使用过程中不涉及
  缺点:
  1、由于数据是连续存储的,导致插入效率变慢
    2、由于数组长度大小固定,那么对预期非固定长度的数字不好处理

  练习实例代码:

 

    /// <summary>
    /// 数组练习操作 
    /// </summary>
    public class arraytest
    {
        /// 数组 array 对于大家来说一点都不陌生
        /// 数组是在内存连续分配的存储空间,这也导致数组有一下一些特点
        /// 1.数据存储是连续的
        /// 2.数组长度在定义时就必须制定
        /// 3.数组存储的数据类型都是同一类型
        /// 4.数组可以直接通过小标访问
        /// 
        /// 优缺点:
        /// 优点:
        ///     1、可以根据索引直接访问,访问速度快
        ///     2、数据是安全的,由于数据类型一致性,在存储使用过程中不涉及到装箱拆箱操作
        /// 缺点:
        ///     1、由于数据是连续存储的,导致插入效率变慢
        ///     2、由于数组长度大小固定,那么对预期非固定长度的数字不好处理

        /// int类型的数组操作 
        public static void intarraytest()
        {

            //// 定义一个秒表,执行获取执行时间
            stopwatch st = new stopwatch();//实例化类
            st.start();//开始计时

            console.writeline("开始初始化长度为10000000的int数组:");

            //// 定义一个数组
            int[] nums = new int[10000000];
            for (int i = 0; i < 10000000; i++)
            {
                nums[i] = 1 + 1;
            }

            //需要统计时间的代码段

            st.stop();//终止计时
            console.writeline(string.format("初始化长度为10000的int数组完毕!总耗时{0}毫秒", st.elapsedmilliseconds.tostring()));
        }
    }

 

三、arraylist集合简介

arraylist 是array的升级版,能够解决array的一些缺点
arraylist其内部实现也是array,只是其长度是可以动态,在其内部用一个变量记录控制长度,arraylist有如下一些特点

  • 1.长度不固定
  • 2.可以存储不同的数据类型(object)
  • 3.同样支持索引查询(可以直接通过小标访问)
  • 4.灵活性更强,以牺牲性能为代价

优缺点:
优点:
1、长度不固定,在定义是不必担长度溢出
2、可以存储任意数据类型
3、可根据索引查询,查询效率快
缺点:
1、由于长度不固定,执行效率低下,因为超出默认长度(10)后,会自动扩容拷贝数据,牺牲性能
2、由于存储类型是object,所以在存数据时会有装箱操作,在取数据时会有拆箱操作,影响效率
3、线程不安全,因为其内部实现是用size、array来共同控制,在新增操作时是非原子操作,所以非安全线程

使用技巧:
在实际使用过程中,为了避免自动扩容,可以预估数据长度,初始化一个数据长度,从而提高效率

练习实例代码:

    /// <summary>
    /// arraylist数组练习操作 
    /// </summary>
    public class arraylisttest
    {
        /// arraylist 是array的升级版,能够解决array的一些缺点
        /// arraylist其内部实现也是array,只是其长度是可以动态,在其内部用一个变量记录控制长度,arraylist有如下一些特点
        /// 1.长度不固定
        /// 2.可以存储不同的数据类型(object)
        /// 3.同样支持索引查询(可以直接通过小标访问)
        /// 4.灵活性更强,以牺牲性能为代价

        /// 优缺点:
        /// 优点:
        ///     1、长度不固定,在定义是不必担长度溢出
        ///     2、可以存储任意数据类型
        ///     3、可根据索引查询,查询效率快
        /// 缺点:
        ///     1、由于长度不固定,执行效率低下,因为超出默认长度(10)后,会自动扩容拷贝数据,牺牲性能
        ///     2、由于存储类型是object,所以在存数据时会有装箱操作,在取数据时会有拆箱操作,影响效率
        ///     3、线程不安全,因为其内部实现是用size、array来共同控制,在新增操作时是非原子操作,所以非安全线程
        ///     
        /// 使用技巧:
        ///     在实际使用过程中,为了避免自动扩容,可以预估数据长度,初始化一个数据长度,从而提高效率

        /// arraylist操作实例
        public static void arraylistopert()
        {

            //// 定义一个秒表,执行获取执行时间
            stopwatch st = new stopwatch();//实例化类

            //// 需要统计时间的代码段(统计初始化长度时的执行时间)
            st.start();//开始计时
            console.writeline("");
            console.writeline("");
            console.writeline("arrylist集合存储数据量为10000000,初始化一个长度,执行开始:");

            arraylist arraylist = new arraylist(10000000);

            //// 定义一个数组
            for (int i = 0; i < 10000000; i++)
            {
                arraylist.add(1 + 1);
            }

            st.stop();//终止计时
            console.writeline(string.format("arrylist集合存储数据量为10000000,初始化一个长度,执行完毕:!总耗时{0}毫秒", st.elapsedmilliseconds.tostring()));

            //// 需要统计时间的代码段(统计初始化非指定长度时的执行时间)

            st.restart();
            console.writeline("");
            console.writeline("arrylist集合存储数据量为10000000,初始化不指定长度,执行开始:");

            arraylist = new arraylist();

            //// 定义一个数组
            for (int i = 0; i < 10000000; i++)
            {
                arraylist.add(1 + 1);
            }

            st.stop();//终止计时
            console.writeline(string.format("arrylist集合存储数据量为10000000,初始化不指定长度,执行完毕:!总耗时{0}毫秒", st.elapsedmilliseconds.tostring()));
        }
    }

 

四、list集合简介

 

随着c#泛型的推出,为了避免arraylist一些缺点,微软推出了list集合
list集合内部还是采用的array实现,同时在定义时需要指定对应的数据类型
这样级保留了array集合的优点,同时也避免了arraylist集合的数据类型不安全和装箱带来的性能牺牲
list特点:

  • 1、数据长度不固定,自动增加
  • 2、存储相同的数据类型
  • 3、可根据索引查询,查询效率快

优缺点:
优点:
1、长度不固定,在定义是不必担长度溢出
2、存储相同数据类型的数据,避免的数据的装箱拆箱,提高了数据处理效率
3、支持索引查询,查询效率快
缺点:
1、由于长度不固定,执行效率低下,因为超出默认长度(10)后,会自动扩容拷贝数据,牺牲性能
2、线程不安全,因为其内部实现是用size、array来共同控制,在新增操作时是非原子操作,所以非安全线程

 

练习实例代码:

   /// <summary>
    /// list练习操作
    /// </summary>
    public class listtest
    {
        /// 随着c#泛型的推出,为了避免arraylist一些缺点,微软推出了list集合
        /// list集合内部还是采用的array实现,同时在定义时需要指定对应的数据类型
        /// 这样级保留了array集合的优点,同时也避免了arraylist集合的数据类型不安全和装箱带来的性能牺牲
        /// list特点:
        /// 1、数据长度不固定,自动增加
        /// 2、存储相同的数据类型
        /// 3、可根据索引查询,查询效率快
        /// 
        /// 优缺点:
        /// 优点:
        ///     1、长度不固定,在定义是不必担长度溢出
        ///     2、存储相同数据类型的数据,避免的数据的装箱拆箱,提高了数据处理效率
        ///     3、支持索引查询,查询效率快
        /// 缺点:
        ///     1、由于长度不固定,执行效率低下,因为超出默认长度(10)后,会自动扩容拷贝数据,牺牲性能
        ///     2、线程不安全,因为其内部实现是用size、array来共同控制,在新增操作时是非原子操作,所以非安全线程

        /// arraylist操作实例
        public static void listopert()
        {
            //// 定义一个秒表,执行获取执行时间
            stopwatch st = new stopwatch();//实例化类
            st.start();//开始计时
                       //// 需要统计时间的代码段(统计初始化长度时的执行时间)
            console.writeline("");
            console.writeline("");
            console.writeline("list集合存储数据量为10000000,初始化一个长度,执行开始:");

            list<int> list = new list<int>(10000000);

            //// 定义一个数组
            for (int i = 0; i < 10000000; i++)
            {
                list.add(1 + 1);
            }

            //需要统计时间的代码段

            st.stop();//终止计时
            console.writeline(string.format("list集合存储数据量为10000000,初始化一个长度,执行完毕:!总耗时{0}毫秒", st.elapsedmilliseconds.tostring()));

            //// 需要统计时间的代码段(统计初始化非指定长度时的执行时间)
            st.restart();
            console.writeline("");
            console.writeline("list集合存储数据量为10000000,初始化不指定长度,执行开始:");

            list = new list<int>();

            //// 定义一个数组
            for (int i = 0; i < 10000000; i++)
            {
                list.add(1 + 1);
            }

            st.stop();//终止计时
            console.writeline(string.format("list集合存储数据量为10000000,初始化不指定长度,执行完毕:!总耗时{0}毫秒", st.elapsedmilliseconds.tostring()));
        }
    }

 

五、linkedlist集合简介

linkedlist链表的底层是采用双向链表的方式实现,
在链表(linked list)中,每一个元素都指向下一个元素,以此来形成了一个链(chain)
可以从头部和尾部插入数据,在存储内存上采用非连续方式存储,链表有如下一些特点

  • 1、内存存储上是非连续的
  • 2、能够支持从头部和底部同时插入
  • 3、长度是非固定的

优缺点:
优点:
1、由于非连续存储,中部插入和删除元素效率高
2、长度非固定,在创建时不用考虑其长度
3、可以冲头部和底部添加元素
4、数据类型是安全的,在创建时需要指定的数据类型
缺点:
1、由于非连续存储,不能通过小标访问,查询效率低

练习实例代码:

    /// <summary>
    /// linkedlist练习操作
    /// </summary>
    public class linkedlisttest {
        /// linkedlist链表的底层是采用双向链表的方式实现,
        /// 在链表(linked list)中,每一个元素都指向下一个元素,以此来形成了一个链(chain)
        /// 可以从头部和尾部插入数据,在存储内存上采用非连续方式存储,链表有如下一些特点
        /// 1、内存存储上是非连续的
        /// 2、能够支持从头部和底部同时插入
        /// 3、长度是非固定的
        /// 优缺点:
        /// 优点:
        ///     1、由于非连续存储,中部插入和删除元素效率高
        ///     2、长度非固定,在创建时不用考虑其长度
        ///     3、可以冲头部和底部添加元素
        ///     4、数据类型是安全的,在创建时需要指定的数据类型
        ///  缺点:
        ///     1、由于非连续存储,不能通过小标访问,查询效率低

        /// linkedlist操作实例
        public static void linkedlisttestopert() {
            //// 定义一个秒表,执行获取执行时间
            stopwatch st = new stopwatch();//实例化类
            st.start();//开始计时
                       //// 需要统计时间的代码段(统计初始化长度时的执行时间)
            console.writeline("");
            console.writeline("");
            console.writeline("linked集合存储数据量为10000000,执行开始:");

            linkedlist<int> list = new linkedlist<int>();

            //// 定义一个数组
            for (int i = 0; i < 10000000; i++)
            {
                list.addfirst(1 + 1);
            }

            //需要统计时间的代码段

            st.stop();//终止计时
            console.writeline(string.format("linked集合存储数据量为10000000,执行完毕:!总耗时{0}毫秒", st.elapsedmilliseconds.tostring()));
        }
    }

 

六、每种集合数据执行结果对比分析

 

    class program
    {
        static void main(string[] args)
        {
            //// array数组操作测试
            arraytest.intarraytest();

            //// arraylist集合操测试
            arraylisttest.arraylistopert();

            //// list集合操作测试
            listtest.listopert();

            //// linkedlist集合操作测试
            linkedlisttest.linkedlisttestopert();

            ///// 通过测试数据
            //通过测试数据大概可以分析得出一些结论
            //1、整体效率上array效率最高,arraylist效率最低,list效率介于array和arraylist之间
            //2、arraylist和list集合,在定义时如果知道数据长度,那么初始化时,指定长度的效率比不指定的长度效率高
            
            
            //总结:
            //在数据集合使用选择上给出以下一些建议:
            //1、array:当元素的数量是固定的,并且需要使用下标时
            //2、arraylist:当存储的元素类型不同时
            //3、list:当元素的数量是固定的,并且需要使用下标时
            //4、linkedlist:当元素需要能够在列表的两端添加时
            console.readline();
        }
    }

  执行结果数据

数据结构之Array、ArrayList、List、LinkedList对比分析

 

通过测试数据大概可以分析得出一些结论
1、整体效率上array效率最高,arraylist效率最低,list效率介于array和arraylist之间
2、arraylist和list集合,在定义时如果知道数据长度,那么初始化时,指定长度的效率比不指定的长度效率高

七、总结:


在数据集合使用选择上给出以下一些建议:
1、array:当元素的数量是固定的,并且需要使用下标时
2、arraylist:当存储的元素类型不同时,初始化时给一个预估的长度
3、list:当元素的数量是固定的,并且需要使用下标时,初始化时给一个预估的长度
4、linkedlist:当元素需要能够在列表的两端添加时