再说具体的实现类之前,首先,说一下它们的共同的接口: List
List接口扩展了Collection并声明存储一系列元素的类集的特性。使用一个基于零的下标,元素可以通过它们在列表中的位置被插入和访问。一个列表可以包含重复元素.
除了由Collection定义的方法之外,List还定义了一些它自己的方法。注意当类集不能被修改时,其中的几种方法引发UnsupportedOperation Exception异常。当一个对象与另一个不兼容,例如当企图将一个不兼容的对象加入一个类集中时,将产生ClassCastException异常
对于由Collection定义的add( )和addAll( )方法,List增加了方法add(int, Object)和addAll(int, Collection)。这些方法在指定的下标处插入元素。由Collection定义的add(Object)和addAll(Collection)的语义也被List改变了,以便它们在列表的尾部增加元素
为了获得在指定位置存储的对象,可以用对象的下标调用get( )方法。为了给类表中的一个元素赋值,可以调用set( )方法,指定被改变的对象的下标。调用indexOf( )或lastIndexOf( )可以得到一个对象的下标
通过调用subList( )方法,可以获得列表的一个指定了开始下标和结束下标的子列表。subList( )方法使得列表处理十分方便。
ArrayList
ArrayList类扩展AbstractList并执行List接口。
ArrayList:我们可以将其看作是能够自动增长容量的数组。
ArrayList支持可随需要而增长的动态数组。在Java中,标准数组是定长的。在数组创建之后,它们不能被加长或缩短,这也就意味着你必须事先知道数组可以容纳多少元素。但是,你直到运行时才能知道需要多大的数组。为了解决这个问题,类集框架定义了ArrayList。本质上,ArrayList是对象引用的一个变长数组。也就是说,ArrayList能够动态地增加或减小其大小。数组列表以一个原始大小被创建。当超过了它的大小,类集自动增大。当对象被删除后,数组就可以缩小
ArrayList有如下的构造函数
– ArrayList( )
– ArrayList(Collection c)
– ArrayList(int capacity)
– 第一个构造函数建立一个空的数组列表。
– 第二个构造函数建立一个数组列表,该数组列表由类集c中的元素初始化。
– 第三个构造函数建立一个数组列表,该数组有指定的初始容量(capacity)。容量是用于存储元素的基本数组的大小。当元素被追加到数组列表上时,容量会自动增加
下面看一下ArrayList的源码:
首先,ArrayList里面有个数组。
/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. */ private transient Object[] elementData;
再来看一下构造函数。
/** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @exception IllegalArgumentException if the specified initial capacity * is negative */ public ArrayList(int initialCapacity) { super(); if (initialCapacity c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }
ArrayList 底层采用数组实现,当使用不带参数的构造方法生成 ArrayList 对象时,实际上会在底层生成一个长度为 10 的Object 类型数组.
如果增加的元素个数超过了 10 个,那么 ArrayList 底层会新生成一个数组,长度为原数组的 1.5 倍+1,然后将原数组的内容复制到新数组当中,并且后续增加的内容都会放到新数组当中。当新数组无法容纳增加的元素时,重复该过程。
/** * Increases the capacity of this <tt>ArrayList</tt> instance, if * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } }
在上述代码中,用到了Arrays.copyof方法,其代码如下:
/** * Copies the specified array, truncating or padding with nulls (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain <tt>null</tt>. * Such indices will exist if and only if the specified length * is greater than that of the original array. * The resulting array is of exactly the same class as the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with nulls * to obtain the specified length * @throws NegativeArraySizeException if <tt>newLength</tt> is negative * @throws NullPointerException if <tt>original</tt> is null * @since 1.6 */ public static <T> T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); } /** * Copies the specified array, truncating or padding with nulls (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain <tt>null</tt>. * Such indices will exist if and only if the specified length * is greater than that of the original array. * The resulting array is of the class <tt>newType</tt>. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @param newType the class of the copy to be returned * @return a copy of the original array, truncated or padded with nulls * to obtain the specified length * @throws NegativeArraySizeException if <tt>newLength</tt> is negative * @throws NullPointerException if <tt>original</tt> is null * @throws ArrayStoreException if an element copied from * <tt>original</tt> is not of a runtime type that can be stored in * an array of class <tt>newType</tt> * @since 1.6 */ public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; }
剩下的就是get/set/add/remove等方法了,其实质都是在对底层的数组做操作。
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { RangeCheck(index); return (E) elementData[index]; } /** * Replaces the element at the specified position in this list with * the specified element. * * @param index index of the element to replace * @param element element to be stored at the specified position * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) { RangeCheck(index); E oldValue = (E) elementData[index]; elementData[index] = element; return oldValue; } /** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacity(size + 1); // Increments modCount!! elementData[size++] = e; return true; } /** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { if (index > size || index < 0) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); ensureCapacity(size+1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } /** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). * * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { RangeCheck(index); modCount++; E oldValue = (E) elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work return oldValue; }
对于 ArrayList 元素的删除操作,需要将被删除元素的后续元素向前移动,代价比较高。
LinkedList
LinkedList类扩展AbstractSequentialList并执行List接口。它提供了一个链接列表数据结
构。它具有如下的两个构造函数,说明如下
– LinkedList( )
– LinkedList(Collection c)
– 第一个构造函数建立一个空的链接列表。
– 第二个构造函数建立一个链接列表,该链接列表由类集c中的元素初始化
LinkedList底层是由双向链表结构实现的。其定义如下:
private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; } }
双向循环列表的结构如下:
构造函数的代码如下:
/** * Constructs an empty list. */ public LinkedList() { header.next = header.previous = header; } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
可以看出,开始的时候只有header.
下面来看add方法:
/** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { addBefore(e, header); return true; }
其中用到了addBefore方法,代码如下:
private Entry<E> addBefore(E e, Entry<E> entry) { Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; }
以插入第一个元素为例,那么,e为当前新添加的元素,entry为header对象。新生成了一个newEntry对象,这个对象的元素是e,这个对象的previous为header,这个对象的下个元素为header.
生成完newEntry以后的那两句话的意思是,将当前元素的previous的后一个元素指向自己,把自己的后一个元素的Previous指向自己。
总体说来就是:
1.找到要插入的未知。将位置上的旧的元素作为新元素的next元素,然后将旧元素的previous元素做为新元素的previous元素。
2.将旧元素的previos元素的next指向新元素。
3.将新元素的next元素的previous指向新元素。
接下来是remove方法:
/** * Removes the first occurrence of the specified element from this list, * if it is present. If this list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained the specified element */ public boolean remove(Object o) { if (o==null) { for (Entry<E> e = header.next; e != header; e = e.next) { if (e.element==null) { remove(e); return true; } } } else { for (Entry<E> e = header.next; e != header; e = e.next) { if (o.equals(e.element)) { remove(e); return true; } } } return false; }
其中的remove(e)对应的是以下方法:
private E remove(Entry<E> e) { if (e == header) throw new NoSuchElementException(); E result = e.element; e.previous.next = e.next; e.next.previous = e.previous; e.next = e.previous = null; e.element = null; size--; modCount++; return result; }
get/set方法比较简单:
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { return entry(index).element; } /** * Replaces the element at the specified position in this list with the * specified element. * * @param index index of the element to replace * @param element element to be stored at the specified position * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) { Entry<E> e = entry(index); E oldVal = e.element; e.element = element; return oldVal; }
其中entry方法如下:
/** * Returns the indexed entry. */ private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }
此外,还有使用addFirst( )方法可以在列表头增加元素;使用addLast( )方法可以在列表的尾部增加元素。调用getFirst( )方法可以获得第一个元素。调用getLast( )方法可以得到最后一个元素。为了删除第一个元素,可以使用removeFirst( )方法;为了删除最后一个元素,可以调用removeLast( )方法。
/** * Returns the first element in this list. * * @return the first element in this list * @throws NoSuchElementException if this list is empty */ public E getFirst() { if (size==0) throw new NoSuchElementException(); return header.next.element; } /** * Returns the last element in this list. * * @return the last element in this list * @throws NoSuchElementException if this list is empty */ public E getLast() { if (size==0) throw new NoSuchElementException(); return header.previous.element; } /** * Removes and returns the first element from this list. * * @return the first element from this list * @throws NoSuchElementException if this list is empty */ public E removeFirst() { return remove(header.next); } /** * Removes and returns the last element from this list. * * @return the last element from this list * @throws NoSuchElementException if this list is empty */ public E removeLast() { return remove(header.previous); } /** * Inserts the specified element at the beginning of this list. * * @param e the element to add */ public void addFirst(E e) { addBefore(e, header.next); } /** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #add}. * * @param e the element to add */ public void addLast(E e) { addBefore(e, header); }
LinkedList也可以用来实现stack或者是queue
// Queue operations. /** * Retrieves, but does not remove, the head (first element) of this list. * @return the head of this list, or <tt>null</tt> if this list is empty * @since 1.5 */ public E peek() { if (size==0) return null; return getFirst(); } /** * Retrieves, but does not remove, the head (first element) of this list. * @return the head of this list * @throws NoSuchElementException if this list is empty * @since 1.5 */ public E element() { return getFirst(); } /** * Retrieves and removes the head (first element) of this list * @return the head of this list, or <tt>null</tt> if this list is empty * @since 1.5 */ public E poll() { if (size==0) return null; return removeFirst(); } /** * Retrieves and removes the head (first element) of this list. * * @return the head of this list * @throws NoSuchElementException if this list is empty * @since 1.5 */ public E remove() { return removeFirst(); } /** * Adds the specified element as the tail (last element) of this list. * * @param e the element to add * @return <tt>true</tt> (as specified by {@link Queue#offer}) * @since 1.5 */ public boolean offer(E e) { return add(e); }
// Deque operations /** * Inserts the specified element at the front of this list. * * @param e the element to insert * @return <tt>true</tt> (as specified by {@link Deque#offerFirst}) * @since 1.6 */ public boolean offerFirst(E e) { addFirst(e); return true; } /** * Inserts the specified element at the end of this list. * * @param e the element to insert * @return <tt>true</tt> (as specified by {@link Deque#offerLast}) * @since 1.6 */ public boolean offerLast(E e) { addLast(e); return true; } /** * Retrieves, but does not remove, the first element of this list, * or returns <tt>null</tt> if this list is empty. * * @return the first element of this list, or <tt>null</tt> * if this list is empty * @since 1.6 */ public E peekFirst() { if (size==0) return null; return getFirst(); } /** * Retrieves, but does not remove, the last element of this list, * or returns <tt>null</tt> if this list is empty. * * @return the last element of this list, or <tt>null</tt> * if this list is empty * @since 1.6 */ public E peekLast() { if (size==0) return null; return getLast(); } /** * Retrieves and removes the first element of this list, * or returns <tt>null</tt> if this list is empty. * * @return the first element of this list, or <tt>null</tt> if * this list is empty * @since 1.6 */ public E pollFirst() { if (size==0) return null; return removeFirst(); } /** * Retrieves and removes the last element of this list, * or returns <tt>null</tt> if this list is empty. * * @return the last element of this list, or <tt>null</tt> if * this list is empty * @since 1.6 */ public E pollLast() { if (size==0) return null; return removeLast(); }
/** * Pushes an element onto the stack represented by this list. In other * words, inserts the element at the front of this list. * * <p>This method is equivalent to {@link #addFirst}. * * @param e the element to push * @since 1.6 */ public void push(E e) { addFirst(e); } /** * Pops an element from the stack represented by this list. In other * words, removes and returns the first element of this list. * * <p>This method is equivalent to {@link #removeFirst()}. * * @return the element at the front of this list (which is the top * of the stack represented by this list) * @throws NoSuchElementException if this list is empty * @since 1.6 */ public E pop() { return removeFirst(); }
关于 ArrayList 与 LinkedList 的比较分析
a) ArrayList 底层采用数组实现,LinkedList 底层采用双向链表实现。
b) 当执行插入或者删除操作时,采用LinkedList比较好。
c) 当执行搜索操作时,采用ArrayList 比较好。
相关推荐
【Java面试题】ArrayList和LinkedList区别
一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。 2.对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要...
关于arraylist和linkedList的区别
2.在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动 3.LinkedList不支持高效的随机元素访问 4.ArrayList的
List最全总结( ArrayList, LinkedList, 匿名类)
Java ArrayList Vector LinkedList map区别 各种集合的区别 写得非常详细
Map+List+ArrayList+LinkedList Java源代码,适合初学者
主要介绍了如何区分Java中ArrayList和LinkedList,文中讲解非常细致,代码帮助大家更好的理解和学习,感兴趣的朋友可以了解下
主要通过实例对Java中ArrayList与LinkedList进行了对比,需要的朋友可以参考下
集合(Arraylist,LinkedList)进阶思维导图
杂谈基本数据结构–线性表: ... ArrayList和LinkedList是顺序存储结构和链式存储结构的表在java语言中的实现. ArrayList提供了一种可增长数组的实现,使用ArrayList,因为内部使用数组实现,所以,它
主要给大家介绍了ArrayList和LinkedList这两种list的五种循环遍历方式,各种方式的性能测试对比,根据ArrayList和LinkedList的源码实现分析性能结果,总结结论。相信对大家的理解和学习具有一定的参考价值,有需要的...
Java面试题10.ArrayList LinkedList.mp4
Java基础之集合List-ArrayList、LinkedList、Vector的底层实现和区别ArrayList底层实际是采用数组实现的(并且该数组的类型是
下面小编就为大家带来一篇java 集合之实现类ArrayList和LinkedList的方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
今天介绍一下Java的两个集合类,ArrayList和LinkedList,这两个集合的知识点几乎可以说面试必问的。感兴趣的朋友跟随小编一起看看吧
主要介绍了java 中ArrayList与LinkedList性能比较的相关资料,需要的朋友可以参考下
1. List概述List,就如图名字所示一样,是元素的有序列表 3. ArrayList示例[java] view plain copy public sta
主要介绍了Java中ArrayList与LinkedList列表结构的源码,文章最后对LinkedList和ArrayList以及Vector的特性有一个对比总结,需要的朋友可以参考下