java ArrayList与LinkedList知识点

时间：2015-01-11 02:10:09 阅读：286 评论：0 收藏：0 [点我收藏+]

一 ArrayList

? ? ? ? ?1. ?arraylist里面是通过数组实现的

[java]?view plaincopy?
/**?
????*?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初始化的时候可以指定大小，如果你知道大小，在创建的时候最好指定

[java]?view plaincopy?
public?ArrayList(int?initialCapacity)?{??
????super();??
????????if?(initialCapacity?<?0)??
????????????throw?new?IllegalArgumentException("Illegal?Capacity:?"+??
???????????????????????????????????????????????initialCapacity);??
????this.elementData?=?new?Object[initialCapacity];??
????}??

? ? ? ? ?3. arraylist添加元素的时候，需要判断存放元素的数组是否需要扩容（扩容大小是原来大小的1/2+1）

[java]?view plaincopy?
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?=?Arrays.copyOf(elementData,?newCapacity);??
????}??
????}??

? ? ? ? 4. arraylist 在指定位置添加元素或者移除指定位置元素，需要移动比较多的数据

[java]?view plaincopy?
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?=?(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;??
????}??

二. ?LinkedList

? ? ? ? ? 1. linkedlist是通过链表实现的，一个节点是一个对象，包含了自己前一个节点的和后一个节点的地址

[java]?view plaincopy?
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. 添加元素是通过移动链表指针

[java]?view plaincopy?
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更适合添加和删除操作（不需要判断是否需要扩容，不需要移动大批的元素）

[java]?view plaincopy?
?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要慢

[java]?view plaincopy?
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方法的源码可以看出）

[java]?view plaincopy?
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知识点

原文：http://liwenshui322.iteye.com/blog/2174664

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)