首页 > 代码库 > java ArrayList与LinkedList知识点
java ArrayList与LinkedList知识点
一 ArrayList
1. 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; /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size;
2. arraylist初始化的时候可以指定大小,如果你知道大小,在创建的时候最好指定
public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = http://www.mamicode.com/new Object[initialCapacity];>
3. arraylist添加元素的时候,需要判断存放元素的数组是否需要扩容(扩容大小是原来大小的1/2+1)public boolean add(E e) { ensureCapacity(size + 1); // Increments modCount!! elementData[size++] = e; return true; } 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 = http://www.mamicode.com/Arrays.copyOf(elementData, newCapacity);>
4. arraylist 在指定位置添加元素或者移除指定位置元素,需要移动比较多的数据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++; } public E remove(int index) { RangeCheck(index); modCount++; E oldValue = http://www.mamicode.com/(E) elementData[index];>
二. LinkedList1. linkedlist是通过链表实现的,一个节点是一个对象,包含了自己前一个节点的和后一个节点的地址
private transient Entry<E> header = new Entry<E>(null, null, null); private transient int size = 0; 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; } }2. 添加元素是通过移动链表指针public boolean add(E e) { addBefore(e, header); return true; } 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; }3. 删除元素也是通过移动指针,所以理论上linkedlist比arraylist更适合添加和删除操作(不需要判断是否需要扩容,不需要移动大批的元素)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; } 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; }4. 获取元素需要遍历链表,比arraylist要慢public E get(int index) { return entry(index).element; } 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)) {//size 右移一位表示除以2,其实就是看从前遍历快还是从后遍历快 for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }5. linkedlist 迭代器,支持向前向后迭代,在迭代过程中移除元素。如果要遍历linkedlist,建议使用迭代器,因为如果使用get方法效率没迭代器高。(从get方法的源码可以看出)private class ListItr implements ListIterator<E> { private Entry<E> lastReturned = header; private Entry<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { //支持从指定位置开始迭代 if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); if (index < (size >> 1)) { next = header.next; for (nextIndex=0; nextIndex<index; nextIndex++) next = next.next; } else { next = header; for (nextIndex=size; nextIndex>index; nextIndex--) next = next.previous; } } public boolean hasNext() {//是否有下一个 return nextIndex != size; } public E next() { //下一个 checkForComodification(); if (nextIndex == size) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.element; } public boolean hasPrevious() { //是否有前一个 return nextIndex != 0; } public E previous() { //前一个 if (nextIndex == 0) throw new NoSuchElementException(); lastReturned = next = next.previous; nextIndex--; checkForComodification(); return lastReturned.element; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex-1; } public void remove() { //删除元素 checkForComodification(); Entry<E> lastNext = lastReturned.next; try { LinkedList.this.remove(lastReturned); } catch (NoSuchElementException e) { throw new IllegalStateException(); } if (next==lastReturned) next = lastNext; else nextIndex--; lastReturned = header; expectedModCount++; } public void set(E e) { if (lastReturned == header) throw new IllegalStateException(); checkForComodification(); lastReturned.element = e; } public void add(E e) { checkForComodification(); lastReturned = header; addBefore(e, next); nextIndex++; expectedModCount++; } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
java ArrayList与LinkedList知识点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。