文章目录链表痛点数组列表各语言官方实现实验代码对于java程序员来说数组列表可能是用得最多的了对于年限比较高的程序员来说ArrayList都写吐了。链表痛点数组列表的出现是为了克服链表的一些缺点而诞生的。链表这个数据结构虽然好用但是也存在一个最重要的缺点就是按索引访问比较慢需要按照引用或者指针去循环检索随机访问复杂度是O(n)。再次链表额外存储空间大每个节点除了存储数据外还需要存储指针对于双向链表则存储了两个指针。最后是编程不友好比如很难使用二分法快速搜索很难进行切片和负索引这些靠下标实现的操作。指针的维护也增加了额外的编程负担。为此有了数组列表。数组列表数组列表内部实现是一个数组内部有个字段记录最后一个元素所在的数组索引。添加元素直接在在这个位置后添加。当数组满了的时候就对数组进行扩容。他的结构如下图所示扩容的方法是长度加一然后翻倍。但是数组列表也有缺点就是从头部删除需要将所有元素前移性能十分低下。其数据字段如下图:各语言官方实现java里数组列表的实现则是大家熟悉的ArrayList。此外还有线程安全的Vector等实现其方法大多通过synchronized关键字实现同步。在现代并发编程中Vector逐渐被CopyOnWriteArrayList或显式同步机制所替代。C语言没有官方的数组列表glib里有GArray和专门存储指针的GPtrArray。在windows编程里一般不是用GLIBwin32 API里提供了DPA和DCA两个数据结构用来实现数组列表。DPA用于存储指针DCA用于存储数据。C标准模板库STL提供了std::vector这是动态数组的标准实现具有自动扩容、随机访问和缓存友好的特点与之对应的是std::list为双向链表实现。JavaScript的Array对象在引擎底层如V8通常以动态数组的方式实现支持混合数据类型、动态扩展以及丰富的操作方法如push、pop、splice等。Rust标准库中的Vecvector是动态数组的实现它在堆上分配内存提供类型安全、零成本的抽象和高效的随机访问能力是Rust中最基础的集合类型。实验代码数组列表代码比链表简单我这里贴一下Java代码publicclassArrayListT{privateObject[]datanewObject[0];privateintindex;publicvoidaddLast(Tvalue){ensureCapacity();data[index]value;}publicTremoveLast(){return(T)data[index--];}publicvoidaddFirst(Tvalue){ensureCapacity();System.arraycopy(data,0,data,1,index);data[0]value;index;}publicTremoveFirst(){Ttemp(T)data[0];System.arraycopy(data,1,data,0,data.length-1);index--;returntemp;}publicTget(intindex){return(T)data[index];}privatevoidensureCapacity(){if(indexdata.length){Object[]arraynewObject[(data.length1)1];System.arraycopy(data,0,array,0,data.length);dataarray;}}}同样对于数组列表不建议自己实现而是建议使用各个语言官方库里的实现。比如java有ArrayList实现。
