arraylist和linkedlist内部的实现大致是怎样的

1ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。 

2对于随机访问get和set，ArrayList优于LinkedList，因为ArrayList可以随机定位，而LinkedList要移动指针一步一步的移动到节点处。（参考数组与链表来思考）

3对于新增和删除 *** 作add和remove，LinedList比较占优势，只需要对指针进行修改即可，而ArrayList要移动数据来填补被删除的对象的空间。

ArrayList和LinkedList是两个集合类，用于存储一系列的对象引用(references)。

例如我们可以用ArrayList来存储一系列的String或者Integer。那么ArrayList和LinkedList在性能上有什么差别呢？什么时候应该用ArrayList什么时候又该用LinkedList呢？

一．时间复杂度

首先一点关键的是，ArrayList的内部实现是基于基础的对象数组的，因此，它使用get方法访问列表中的任意一个元素时(random-access)，它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的一端开始检查，直到另外一端。对LinkedList而言，访问列表中的某个指定元素没有更快的方法了。

假设我们有一个很大的列表，它里面的元素已经排好序了，这个列表可能是ArrayList类型的也可能是LinkedList类型的，现在我们对这个列表来进行二分查找(binary search)，比较列表是ArrayList和LinkedList时的查询速度，看下面的程序：

package commangocitytest;  

import javautilLinkedList;  

import javautilList;  

import javautilRandom;  

import javautilArrayList;  

import javautilArrays;  

import javautilCollections;  

public class TestList {  

     public static final int N=50000; 

     public static List values; 

     static{  

         Integer vals[]=new Integer[N]; 

         Random r=new Random(); 

         for(int i=0,currval=0;i<N;i++){  

             vals=new Integer(currval);  

             currval+=rnextInt(100)+1;  

         } 

         values=ArraysasList(vals);  

     } 

     static long timeList(List lst){  

         long start=SystemcurrentTimeMillis();  

         for(int i=0;i<N;i++){  

             int index=CollectionsbinarySearch(lst, valuesget(i));  

             if(index!=i)  

                 Systemoutprintln("错误");  

         }  

         return SystemcurrentTimeMillis()-start;  

     }  

     public static void main(String args[]){  

         Systemoutprintln("ArrayList消耗时间："+timeList(new ArrayList(values)));  

         Systemoutprintln("LinkedList消耗时间："+timeList(new LinkedList(values)));  

     }  

}package commangocitytest;   

import javautilLinkedList;   

import javautilList;   

import javautilRandom;   

import javautilArrayList;   

import javautilArrays;   

import javautilCollections;   

public class TestList {   

     public static final int N=50000;  

     public static List values;  

     static{   

         Integer vals[]=new Integer[N];  

         Random r=new Random();  

         for(int i=0,currval=0;i<N;i++){   

             vals=new Integer(currval);   

             currval+=rnextInt(100)+1;   

         }  

         values=ArraysasList(vals);   

     }  

     static long timeList(List lst){   

         long start=SystemcurrentTimeMillis();   

         for(int i=0;i<N;i++){   

             int index=CollectionsbinarySearch(lst, valuesget(i));   

             if(index!=i)   

                 Systemoutprintln("错误");   

         }   

         return SystemcurrentTimeMillis()-start;   

     }   

     public static void main(String args[]){   

         Systemoutprintln("ArrayList消耗时间："+timeList(new ArrayList(values)));   

         Systemoutprintln("LinkedList消耗时间："+timeList(new LinkedList(values)));   

     }   

}

我得到的输出是：ArrayList消耗时间：15

LinkedList消耗时间：2596

这个结果不是固定的，但是基本上ArrayList的时间要明显小于LinkedList的时间。因此在这种情况下不宜用LinkedList。二分查找法使用的随机访问(randomaccess)策略，而LinkedList是不支持快速的随机访问的。对一个LinkedList做随机访问所消耗的时间与这个list的大小是成比例的。而相应的，在ArrayList中进行随机访问所消耗的时间是固定的。

这是否表明ArrayList总是比LinkedList性能要好呢？这并不一定，在某些情况下LinkedList的表现要优于ArrayList，有些算法在LinkedList中实现时效率更高。比方说，利用Collectionsreverse方法对列表进行反转时，其性能就要好些。

看这样一个例子，假如我们有一个列表，要对其进行大量的插入和删除 *** 作，在这种情况下LinkedList就是一个较好的选择。请看如下一个极端的例子，我们重复的在一个列表的开端插入一个元素：

package commangocitytest; 

import javautil;  

public class ListDemo {  

     static final int N=50000;  

     static long timeList(List list){  

     long start=SystemcurrentTimeMillis();  

     Object o = new Object();  

     for(int i=0;i<N;i++)  

         listadd(0, o);  

     return SystemcurrentTimeMillis()-start;  

     }  

     public static void main(String[] args) {  

         Systemoutprintln("ArrayList耗时："+timeList(new ArrayList()));  

         Systemoutprintln("LinkedList耗时："+timeList(new LinkedList()));  

     }  

}package commangocitytest;  

import javautil;   

public class ListDemo {   

     static final int N=50000;   

     static long timeList(List list){   

     long start=SystemcurrentTimeMillis();   

     Object o = new Object();   

     for(int i=0;i<N;i++)   

         listadd(0, o);   

     return SystemcurrentTimeMillis()-start;   

     }   

     public static void main(String[] args) {   

         Systemoutprintln("ArrayList耗时："+timeList(new ArrayList()));   

         Systemoutprintln("LinkedList耗时："+timeList(new LinkedList()));   

     }   

}

这时我的输出结果是：ArrayList耗时：2463

LinkedList耗时：15

这和前面一个例子的结果截然相反，当一个元素被加到ArrayList的最开端时，所有已经存在的元素都会后移，这就意味着数据移动和复制上的开销。相反的，将一个元素加到LinkedList的最开端只是简单的为这个元素分配一个记录，然后调整两个连接。在LinkedList的开端增加一个元素的开销是固定的，而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的。

二．空间复杂度

在LinkedList中有一个私有的内部类，定义如下：

private static class Entry {

         Object element; 

         Entry next; 

         Entry previous; 

     }

每个Entry对象reference列表中的一个元素，同时还有在LinkedList中它的上一个元素和下一个元素。一个有1000个元素的LinkedList对象将有1000个链接在一起的Entry对象，每个对象都对应于列表中的一个元素。这样的话，在一个LinkedList结构中将有一个很大的空间开销，因为它要存储这1000个Entity对象的相关信息。

ArrayList使用一个内置的数组来存储元素，这个数组的起始容量是10当数组需要增长时，新的容量按如下公式获得：新容量=(旧容量3)/2+1，也就是说每一次容量大概会增长50%。这就意味着，如果你有一个包含大量元素的ArrayList对象，那么最终将有很大的空间会被浪费掉，这个浪费是由ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素，数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配，将会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素，我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在ArrayList分配完毕之后去掉浪费掉的空间。

三．总结

ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：

性能总结：

1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。

2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。

3．LinkedList不支持高效的随机元素访问。

4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

可以这样说：当 *** 作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的 *** 作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。

LinkedList类

     LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些 *** 作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

    注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：

List list = CollectionssynchronizedList(new LinkedList());

ArrayList类

ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。

size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。

每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

和LinkedList一样，ArrayList也是非同步的（unsynchronized）。

总结

如果涉及到堆栈，队列等 *** 作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。

      尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。

每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity *** 作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。

注意，此实现不是同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。这通常是通过同步那些用来封装列表的对象来实现的。但如果没有这样的对象存在，则该列表需要运用{@link Collections#synchronizedList CollectionssynchronizedList}来进行“包装”，该方法最好是在创建列表对象时完成，为了避免对列表进行突发的非同步 *** 作。

下面我们讨论下ArrayList初始默认容量的问题。

有文章说ArrayList默认构造的容量为10，没错。 因为ArrayList的底层是由一个Object[]数组构成的，而这个Object[]数组，默认的长度是10，所以有的文章会说ArrayList长度容量为10。

然而你所指的size()方法，指的是“逻辑”长度。

所谓“逻辑”长度，是指内存已存在的“实际元素的长度” 而“空元素不被计算”

即：当你利用add()方法，向ArrayList内添加一个“元素”时，逻辑长度就增加1位。 而剩下的9个空元素不被计算。

1．publicvirtualintAdd(objectvalue);

将对象添加到ArrayList的结尾处

ArrayListaList=newArrayList();

aListAdd("a");

aListAdd("b");

aListAdd("c");

aListAdd("d");

aListAdd("e");

内容为abcde

2．publicvirtualvoidInsert(intindex,objectvalue);

将元素插入ArrayList的指定索引处

ArrayListaList=newArrayList();

aListAdd("a");

aListAdd("b");

aListAdd("c");

aListAdd("d");

aListAdd("e");

aListInsert(0,"aa");

结果为aaabcde

3．publicvirtualvoidInsertRange(intindex,ICollectionc);

将集合中的某个元素插入ArrayList的指定索引处

ArrayListaList=newArrayList();

aListAdd("a");

aListAdd("b");

aListAdd("c");

aListAdd("d");

aListAdd("e");

ArrayListlist2=newArrayList();

list2Add("tt");

list2Add("ttt");

aListInsertRange(2,list2);

结果为abtttttcde

四．删除

a)publicvirtualvoidRemove(objectobj);

从ArrayList中移除特定对象的第一个匹配项,注意是第一个

ArrayListaList=newArrayList();

aListAdd("a");

aListAdd("b");

aListAdd("c");

aListAdd("d");

aListAdd("e");

aListRemove("a");

结果为bcde

2publicvirtualvoidRemoveAt(intindex);

移除ArrayList的指定索引处的元素

aListAdd("a");

aListAdd("b");

aListAdd("c");

aListAdd("d");

aListAdd("e");

aListRemoveAt(0);

结果为bcde

3．publicvirtualvoidRemoveRange(intindex,intcount);

从ArrayList中移除一定范围的元素。Index表示索引，count表示从索引处开始的数目

aListAdd("a");

aListAdd("b");

aListAdd("c");

aListAdd("d");

aListAdd("e");

aListRemoveRange(1,3);

结果为ae

4．publicvirtualvoidClear();

从ArrayList中移除所有元素。

五．排序

a)publicvirtualvoidSort();

对ArrayList或它的一部分中的元素进行排序。

ArrayListaList=newArrayList();

aListAdd("e");

aListAdd("a");

aListAdd("b");

aListAdd("c");

aListAdd("d");

DropDownList1DataSource=aList;//DropDownListDropDownList1;

DropDownList1DataBind();

结果为eabcd

ArrayListaList=newArrayList();

aListAdd("a");

aListAdd("b");

aListAdd("c");

aListAdd("d");

aListAdd("e");

aListSort();//排序

DropDownList1DataSource=aList;//DropDownListDropDownList1;

DropDownList1DataBind();

结果为abcde

b)publicvirtualvoidReverse();

将ArrayList或它的一部分中元素的顺序反转。

ArrayListaList=newArrayList();

aListAdd("a");

aListAdd("b");

aListAdd("c");

aListAdd("d");

aListAdd("e");

aListReverse();//反转

DropDownList1DataSource=aList;//DropDownListDropDownList1;

DropDownList1DataBind();

结果为edcba

六．查找

a)publicvirtualintIndexOf(object);

b)publicvirtualintIndexOf(object,int);

c)publicvirtualintIndexOf(object,int,int);

返回ArrayList或它的一部分中某个值的第一个匹配项的从零开始的索引。没找到返回-1。

ArrayListaList=newArrayList();

aListAdd("a");

aListAdd("b");

aListAdd("c");

aListAdd("d");

aListAdd("e");

intnIndex=aListIndexOf(“a”);//1

nIndex=aListIndexOf(“p”);//没找到，-1

d)publicvirtualintLastIndexOf(object);

e)publicvirtualintLastIndexOf(object,int);

f)publicvirtualintLastIndexOf(object,int,int);

返回ArrayList或它的一部分中某个值的最后一个匹配项的从零开始的索引。

ArrayListaList=newArrayList();

aListAdd("a");

aListAdd("b");

aListAdd("a");//同0

aListAdd("d");

aListAdd("e");

intnIndex=aListLastIndexOf("a");//值为2而不是0

g)publicvirtualboolContains(objectitem);

确定某个元素是否在ArrayList中。包含返回true,否则返回false

七．其他

1．publicvirtualintCapacity{get;set;}

获取或设置ArrayList可包含的元素数。

2．publicvirtualintCount{get;}

获取ArrayList中实际包含的元素数。

Capacity是ArrayList可以存储的元素数。Count是ArrayList中实际包含的元素数。Capacity总是大于或等于Count。如果在添加元素时，Count超过Capacity，则该列表的容量会通过自动重新分配内部数组加倍。

如果Capacity的值显式设置，则内部数组也需要重新分配以容纳指定的容量。如果Capacity被显式设置为0，则公共语言运行库将其设置为默认容量。默认容量为16。

在调用Clear后，Count为0，而此时Capacity切是默认容量16，而不是0

3．publicvirtualvoidTrimToSize();

将容量设置为ArrayList中元素的实际数量。

如果不向列表中添加新元素，则此方法可用于最小化列表的内存系统开销。

若要完全清除列表中的所有元素，请在调用TrimToSize之前调用Clear方法。截去空ArrayList会将ArrayList的容量设置为默认容量，而不是零。

ArrayListaList=newArrayList();

aListAdd("a");

aListAdd("b");

aListAdd("c");

aListAdd("d");

aListAdd("e");//Count=5,Capacity=16,

aListTrimToSize();//Count=Capacity=5;

lisize()值的是里面存储的object的个数 并不是array的初始化长度 两个不是同一个意思 据个例子 初始化长度可以认为是默认初始化array有10个格子 其中4个格子里面存有东西 那么它的size方法将返回的值为4而不是10

ArrayList默认构造的容量为10，没错。

因为ArrayList的底层是由一个Object[]数组构成的，而这个Object[]数组，默认的长度是10，所以有的文章会说ArrayList长度容量为10。

然而你所指的size()方法，指的是“逻辑”长度。

所谓“逻辑”长度，是指内存已存在的“实际元素的长度” 而“空元素不被计算”

即：当你利用add()方法，向ArrayList内添加一个“元素”时，逻辑长度就增加1位。 而剩下的9个空元素不被计算。

Java容器类Collection、List、ArrayList、Vector及map、HashTable、HashMap区别

Collection是List和Set两个接口的基接口

List在Collection之上增加了"有序"

Set在Collection之上增加了"唯一"

而ArrayList是实现List的类所以他是有序的

它里边存放的元素在排列上存在一定的先后顺序

而且ArrayList是采用数组存放元素

另一种List LinkedList采用的则是链表。

Collection和Map接口之间的主要区别在于：Collection中存储了一组对象，而Map存储关键字/值对。

在Map对象中，每一个关键字最多有一个关联的值。

Map:不能包括两个相同的键，一个键最多能绑定一个值。null可以作为键，这样的键只有一个；可以有一个或多个键所对应的

值为null。当get()方法返回null值时，即可以表示Map中没有该键，也可以表示该键所对应的值为null。因此，在Map中不能由get()方法来判断Map中是否存在某个键，而应该用containsKey()方法来判断。

继承Map的类有：HashMap，HashTable

HashMap：Map的实现类，缺省情况下是非同步的，可以通过Map CollectionssynchronizedMap(Map m)来达到线程同步

HashTable：Dictionary的子类，确省是线程同步的。不允许关键字或值为null

当元素的顺序很重要时选用TreeMap，当元素不必以特定的顺序进行存储时，使用HashMap。Hashtable的使用不被推荐，因为HashMap提供了所有类似的功能，并且速度更快。当你需要在多线程环境下使用时，HashMap也可以转换为同步的。

为什么要使用集合类

当你事先不知道要存放数据的个数，或者你需要一种比数组下标存取机制更灵活的方法时，你就需要用到集合类。

理解集合类

集合类存放于javautil包中。

集合类存放的都是对象的引用，而非对象本身，出于表达上的便利，我们称集合中的对象就是指集合中对象的引用（reference)。

集合类型主要有3种：set(集）、list(列表）和map(映射)。

(1)集

集（set）是最简单的一种集合，它的对象不按特定方式排序，只是简单的把对象加入集合中，就像往口袋里放东西。

对集中成员的访问和 *** 作是通过集中对象的引用进行的，所以集中不能有重复对象。

集也有多种变体，可以实现排序等功能，如TreeSet，它把对象添加到集中的 *** 作将变为按照某种比较规则将其插入到有序的对象序列中。它实现的是SortedSet接口，也就是加入了对象比较的方法。通过对集中的对象迭代，我们可以得到一个升序的对象集合。

(2)列表

列表的主要特征是其对象以线性方式存储，没有特定顺序，只有一个开头和一个结尾，当然，它与根本没有顺序的集是不同的。

列表在数据结构中分别表现为：数组和向量、链表、堆栈、队列。

关于实现列表的集合类，是我们日常工作中经常用到的，将在后边的笔记详细介绍。

(3)映射

映射与集或列表有明显区别，映射中每个项都是成对的。映射中存储的每个对象都有一个相关的关键字（Key）对象，关键字决定了对象在映射中的存储位置，检索对象时必须提供相应的关键字，就像在字典中查单词一样。关键字应该是唯一的。

关键字本身并不能决定对象的存储位置，它需要对过一种散列(hashing)技术来处理，产生一个被称作散列码(hash code)的整数值，散列码通常用作一个偏置量，该偏置量是相对于分配给映射的内存区域起始位置的，由此确定关键字/对象对的存储位置。理想情况下，散列处理应该产生给定范围内均匀分布的值，而且每个关键字应得到不同的散列码。

集合类简介

javautil中共有13个类可用于管理集合对象，它们支持集、列表或映射等集合，以下是这些类的简单介绍

集：

HashSet： 使用HashMap的一个集的实现。虽然集定义成无序，但必须存在某种方法能相当高效地找到一个对象。使用一个HashMap对象实现集的存储和检索 *** 作是在固定时间内实现的

TreeSet： 在集中以升序对对象排序的集的实现。这意味着从一个TreeSet对象获得第一个迭代器将按升序提供对象。TreeSet类使用了一个TreeMap

列表：

Vector： 实现一个类似数组一样的表，自动增加容量来容纳你所需的元素。使用下标存储和检索对象就象在一个标准的数组中一样。你也可以用一个迭代器从一个Vector中检索对象。Vector是唯一的同步容器类当两个或多个线程同时访问时也是性能良好的。（同步即同时只能一个进程访问，其他等待）

Stack: 这个类从Vector派生而来，并且增加了方法实现栈一种后进先出的存储结构。

LinkedList: 实现一个链表。由这个类定义的链表也可以像栈或队列一样被使用。

ArrayList: 实现一个数组，它的规模可变并且能像链表一样被访问。它提供的功能类似Vector类但不同步。

映射：

HashTable： 实现一个映象，所有的键必须非空。为了能高效的工作，定义键的类必须实现hashcode()方法和equal()方法。这个类是前面java实现的一个继承，并且通常能在实现映象的其他类中更好的使用。

HashMap： 实现一个映象，允许存储空对象，而且允许键是空（由于键必须是唯一的，当然只能有一个）。

WeakHashMap： 实现这样一个映象：通常如果一个键对一个对象而言不再被引用，键/对象对将被舍弃。这与HashMap形成对照，映象中的键维持键/对象对的生命周期，尽管使用映象的程序不再有对键的引用，并且因此不能检索对象。

TreeMap： 实现这样一个映象，对象是按键升序排列的。

下图是集合类所实现的接口之间的关系：

Set和List都是由公共接口Collection扩展而来，所以它们都可以使用一个类型为Collection的变量来引用。这就意味着任何列表或集构成的集合都可以用这种方式引用，只有映射类除外（但也不是完全排除在外，因为可以从映射获得一个列表。）所以说，把一个列表或集传递给方法的标准途径是使用Collection类型的参数。

<hr>

List接口

List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。

和下面要提到的Set不同，List允许有相同的元素。

除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。

实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。

ArrayList类

ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。

size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。

每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

和LinkedList一样，ArrayList也是非同步的（unsynchronized）。

Map接口

请注意，Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。

HashMap类

HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子 *** 作时间开销和HashMap的容量成比例。因此，如果迭代 *** 作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。

----------------------------------------------------------------------------

1

List是接口，List特性就是有序,会确保以一定的顺序保存元素

ArrayList是它的实现类,是一个用数组实现的List

Map是接口,Map特性就是根据一个对象查找对象

HashMap是它的实现类,HashMap用hash表实现的Map,就是利用对象的hashcode(hashcode()是Object的方法)进行快速散列查找(关于散列查找,可以参看<<数据结构>>)

2

一般情况下,如果没有必要,推荐代码只同List,Map接口打交道

比如:List list = new ArrayList();

这样做的原因是list就相当于是一个泛型的实现,如果想改变list的类型,只需要:

List list = new LinkedList();//LinkedList也是List的实现类,也是ArrayList的兄弟类

这样,就不需要修改其它代码,这就是接口编程的优雅之处

另外的例子就是,在类的方法中,如下声明:

private void doMyAction(List list){}

这样这个方法能处理所有实现了List接口的类,一定程度上实现了泛型函数

3

如果开发的时候觉得ArrayList,HashMap的性能不能满足你的需要,可以通过实现List,Map(或者Collection)来定制你的自定义类

本文来自CSDN博客，转载请标明出处：>

以上就是关于arraylist和linkedlist内部的实现大致是怎样的全部的内容，包括:arraylist和linkedlist内部的实现大致是怎样的、arraylist默认数组长度、在Java中怎么修改ArrayList()中元素的值等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！