疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Array ArrayList LinkList的区别剖析


 

       这是一个面试中我们经常被问到的问题

  Array、ArrayList、LinkList之间的区别:Array、ArrayList、LinkList均属于泛型的范畴,都用来存放元素,主要区别是Array是一个固定大小的容器,底层采用的是线性连续空间来存放元素,ArrayList同样也是一个容器,但是其大小不固定,底层采用的也是线性连续空间来存放元素,当线性连续空间不足以存放元素时,又重新申请一片更大的空间(大约是原空间的2倍),将原有的内容移过去,因此从这里可以看出,Array要比ArrayList的效率高,因为不需要重新申请空间,LinkList也是一个容器,但底层采用的是链表,因此不存在扩容问题,除非整个内存空间都不足了,由于采用的是链表,因此查找效率也比较低,但删除效率比较高。

  Array测试源代码(其实这个压根没必要测试,大家都用过J):

  [java]

  //来个复杂点的吧

  String [][]array=new String[5][];

  //再加个for循环,每个小数组又是一个小数组

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

  array[i]=new String[i+1];

  }

  //从上面的代码中,可以看出的是数组的大小一旦确定,其内存空间的布局也就

  //确定了,大小也就确定了

  //来个复杂点的吧

  String [][]array=new String[5][];

  //再加个for循环,每个小数组又是一个小数组

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

  array[i]=new String[i+1];

  }

  //从上面的代码中,可以看出的是数组的大小一旦确定,其内存空间的布局也就

  //确定了,大小也就确定了上面的代码,太简单了,每个Java书上都有,没有的,扔了它吧

  ArrayList的测试代码:

  [java]

  //声明一个数组对象,采用的是ArrayList,从这里可以看出的是,ArrayList里可以存放任意

  //类型,这也就是泛型

  ArrayList array=new ArrayList();

  //在这个数组对象里面存放元素

  array.add("test1");

  array.add("test2");

  //将值打印出来

  for(int i=0;i

  System.out.println(array.get(i));

  //声明一个数组对象,采用的是ArrayList,从这里可以看出的是,ArrayList里可以存放任意

  //类型,这也就是泛型

  ArrayList array=new ArrayList();

  //在这个数组对象里面存放元素

  array.add("test1");

  array.add("test2");

  //将值打印出来

  for(int i=0;i

  System.out.println(array.get(i));

  上面的代码,同样也是很简单的,不做分析,要分析的就是ArrayList与Array的不同,则要深入ArrayList的源代码

  ArrayList核心源代码:

  [java]

  public class ArrayList extends AbstractList

  implements List, RandomAccess, Cloneable, java.io.Serializable

  {

  private static final long serialVersionUID = 8683452581122892189L;

  /**

  从这里,可以看出的是,ArrayList里面是通过数组来存放元素的,数组名叫elementData,类型是Object

  */

  private transient Object[] elementData;

  /**

  * 数组的尺寸,上面有个关键字transient,有些人没见过,是用在Java的序列化时。

  *

  * @serial

  */

  private int size;

  /**

  * Constructs an empty list with the specified initial capacity.

  *

  * @param initialCapacity the initial capacity of the list

  *下面这个是构造函数,从这里可以看出,如果声明时给构造函数传递了一个初始大小,则使用这个大小来开僻空间

  * is negative

  */

  public ArrayList(int initialCapacity) {

  super();

  if (initialCapacity < 0)

  throw new IllegalArgumentException("Illegal Capacity: "+

  initialCapacity);

  this.elementData = new Object[initialCapacity];

  }

  /**

  * 如果使用默认构造函数,则默认情况下会开僻一个10B的大小空间

  */

  public ArrayList() {

  this(10);

  }

  public class ArrayList extends AbstractList

  implements List, RandomAccess, Cloneable, java.io.Serializable

  {

  private static final long serialVersionUID = 8683452581122892189L;

  /**

  从这里,可以看出的是,ArrayList里面是通过数组来存放元素的,数组名叫elementData,类型是Object

  */

  private transient Object[] elementData;

  /**

  * 数组的尺寸,上面有个关键字transient,有些人没见过,是用在Java的序列化时。

  *

  * @serial

  */

  private int size;

  /**

  * Constructs an empty list with the specified initial capacity.

  *

  * @param initialCapacity the initial capacity of the list

  *下面这个是构造函数,从这里可以看出,如果声明时给构造函数传递了一个初始大小,则使用这个大小来开僻空间

  * is negative

  */

  public ArrayList(int initialCapacity) {

  super();

  if (initialCapacity < 0)

  throw new IllegalArgumentException("Illegal Capacity: "+

  initialCapacity);

  this.elementData = new Object[initialCapacity];

  }

  /**

  * 如果使用默认构造函数,则默认情况下会开僻一个10B的大小空间

  */

  public ArrayList() {

  this(10);

  }

  从上面的代码中,可以看出的是ArrayList的内层空间布局也是采用数组来实现的,因此与数组没什么区别,下面就看看其有区别的地方

  不同之处的源代码:

  [java]

  public boolean add(E e) {

  ensureCapacity(size + 1); // Increments modCount!!

  elementData[size++] = e;

  return true;

  }

  public boolean add(E e) {

  ensureCapacity(size + 1); // Increments modCount!!

  elementData[size++] = e;

  return true;

  }上面这个函数是ArrayList中一个泛型向集合增加的方法,在这个方法中为了向集合中增加一个元素,必须要确定的是集合中有足够的空间,因此这个函数的关键是函数

  ensureCapacity(size+1),再看看其源代码

  [java]

  public void ensureCapacity(int minCapacity) {

  modCount++;

  //获取当前容器的大小

  int oldCapacity = elementData.length;

  //如果填加一个元素后,新容器的大小minCapacity大于oldCapacity,则表示容器已

  //无法存放元素了,执行下面的逻辑

  if (minCapacity > oldCapacity) {

  Object oldData[] = elementData;

  //重新设定容器的大小,新容器的大小,为原来容器的150%倍+1

  int newCapacity = (oldCapacity * 3)/2 + 1;

  //容器增大后,如果还不够存放的话,就执行下面的逻辑

  if (newCapacity < minCapacity)

  //将容器的大小直接设为minCapacity

  newCapacity = minCapacity;

  // minCapacity is usually close to size, so this is a win:

  //这里会重新开僻空间,并将原来的元素copy进去

  elementData = Arrays.copyOf(elementData, newCapacity);

  }

  public void ensureCapacity(int minCapacity) {

  modCount++;

  //获取当前容器的大小

  int oldCapacity = elementData.length;

  //如果填加一个元素后,新容器的大小minCapacity大于oldCapacity,则表示容器已

  //无法存放元素了,执行下面的逻辑

  if (minCapacity > oldCapacity) {

  Object oldData[] = elementData;

  //重新设定容器的大小,新容器的大小,为原来容器的150%倍+1

  int newCapacity = (oldCapacity * 3)/2 + 1;

  //容器增大后,如果还不够存放的话,就执行下面的逻辑

  if (newCapacity < minCapacity)

  //将容器的大小直接设为minCapacity

  newCapacity = minCapacity;

  // minCapacity is usually close to size, so this is a win:

  //这里会重新开僻空间,并将原来的元素copy进去

  elementData = Arrays.copyOf(elementData, newCapacity);

  }

  上面我已经注释的很详细了,与Array的区别也是显而易见的,在容器容量不足时,会自动扩容

  LinkList的测试源代码

  [java]

  //声明一个数组对象,采用的是LinkedList,从这里可以看出的是,LinkedList里可以存放任意

  //类型,这也就是泛型

  LinkedList array=new LinkedList();

  //在这个数组对象里面存放元素

  array.add("test1");

  array.add("test2");

  //将值打印出来

  for(int i=0;i

  System.out.println(array.get(i));

  //声明一个数组对象,采用的是LinkedList,从这里可以看出的是,LinkedList里可以存放任意

  //类型,这也就是泛型

  LinkedList array=new LinkedList();

  //在这个数组对象里面存放元素

  array.add("test1");

  array.add("test2");

  //将值打印出来

  for(int i=0;i

  System.out.println(array.get(i));

  上面的代码与ArrayList没什么区别,是的,真正有区别的是在其实现上,看看LinkList实现的核心源代码吧:)

  [java]

  public class LinkedList

  extends AbstractSequentialList

  implements List, Deque, Cloneable, java.io.Serializable

  { //与ArrayList不同吧,不是用数组吧,有header,是不是想起链表了,是的,这里就是用链表

  private transient Entry header = new Entry(null, null, null);

  private transient int size = 0;

  /**

  * 这个就是构造函数啦(默认的)指针均指向了header,看来还是个双向循环链表

  */

  public LinkedList() {

  header.next = header.previous = header;

  }

  public class LinkedList

  extends AbstractSequentialList

  implements List, Deque, Cloneable, java.io.Serializable

  { //与ArrayList不同吧,不是用数组吧,有header,是不是想起链表了,是的,这里就是用链表

  private transient Entry header = new Entry(null, null, null);

  private transient int size = 0;

  /**

  * 这个就是构造函数啦(默认的)指针均指向了header,看来还是个双向循环链表

  */

  public LinkedList() {

  header.next = header.previous = header;

  }

  从上面的代码中,可以看到的是里面真的是用链表实现的,你可以再看看其他的代码,只要理解C/C++里的链表,很容易理解的:)