- 浏览: 144352 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
EclipseEye:
fair_jm 写道不错 蛮详细的 谢谢分享
SWT/JFace专题 --- SWT中Display和多线程 -
fair_jm:
不错 蛮详细的 谢谢分享
SWT/JFace专题 --- SWT中Display和多线程
List
-----------
1.ArrayList(jdk1.5以前版本中Vector)
2.LinkedList(jdk1.5以前版本中Stack)
3.CopyOnWriteArrayList
------------------------------
ArrayList是数组的实现形式(内部存储结构是一个数组):
//添加新的元素到数组末尾时,如果超过了当前容量,就要对数组进行扩容,扩充为原来大小的1.5倍,
//由于扩容牵涉到整个数组的copy,对性能影响较大,所以如果知道要存放容量的大小,尽量在创建ArrayList时指定
-----------------------------------
添加元素后扩容情况的效果图:
//添加元素的方法,注意先调用ensureCapacity,保证有足够的容量(如果不足就扩容,上面有该方法介绍)
//由于add方法添加元素时,可能导致扩容操作,这也影响了其效率
-----
删除元素的效果图:
ensureCapacity
说明:ArrayList就是一个数组实现,适用于, 查找操作较多,而修改操作(add和delete)较少的情况,由于实现较为简单,就不再过多介绍,如果想更详细了解其实现,可以查看其源码。
下面要介绍的LinkedList适用于:查找较少,修改较多的情况(这与LinkedList的链式结构是有关系的)。
-------------------------------
LinkedList是链表结构的实现形式(内部存储结构是一个链表形式):
存储结构图示
LinkedList的类结构
LinkedList的成员变量
LinkedList的构造方法
addAll方法
LinkedList的节点存储结构
------------------------
LinkedList的get操作
LinkedList的add操作
添加新元素到链表的末端,图示如下:
----------------------------
LinkedList的delete操作
删除元素E3,图示如下:
另外,由于LinkedList实现了双向队列Deque接口,所以也具有队列的相关操作,可以当做一个队列使用。
-----------
1.ArrayList(jdk1.5以前版本中Vector)
2.LinkedList(jdk1.5以前版本中Stack)
3.CopyOnWriteArrayList
------------------------------
ArrayList是数组的实现形式(内部存储结构是一个数组):
public class ArrayList <E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private transient Object[] elementData;//存储元素的数组 //ArrayList的构造方法 public ArrayList(int initialCapacity) {//initialCapacity表示要创建的数组的容量 super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity];//创建initialCapacity长度的数组 } /** *默认的构造 容量为10 */ public ArrayList() { this(10); } /** * 通过传入集合变量的形式初始化创建list的数组 */ public ArrayList(Collection<? extends E> 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); }-----------------------------
//添加新的元素到数组末尾时,如果超过了当前容量,就要对数组进行扩容,扩充为原来大小的1.5倍,
//由于扩容牵涉到整个数组的copy,对性能影响较大,所以如果知道要存放容量的大小,尽量在创建ArrayList时指定
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); } }
-----------------------------------
//get方法实现很简单,就是指定到数组的index下标处,效率很高 public E get(int index) { RangeCheck(index); return (E) elementData[index]; }------
添加元素后扩容情况的效果图:
//添加元素的方法,注意先调用ensureCapacity,保证有足够的容量(如果不足就扩容,上面有该方法介绍)
//由于add方法添加元素时,可能导致扩容操作,这也影响了其效率
public boolean add(E e) { ensureCapacity(size + 1); elementData[size++] = e; return true; }
-----
删除元素的效果图:
//删除元素的remove操作,牵涉到删除位置index后边元素的copy,所以ArrayList的remove操作效率不高 public E remove(int index) { RangeCheck(index); modCount++; E oldValue = (E) elementData[index]; int numMoved = size - index - 1;//删除位置后边的元素个数 if (numMoved > 0)//把要删除位置index后边的元素重新copy到数组的index处及以后 System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // 把最后一个位置的元素置空,便于垃圾回收 return oldValue; }------------------
ensureCapacity
说明:ArrayList就是一个数组实现,适用于, 查找操作较多,而修改操作(add和delete)较少的情况,由于实现较为简单,就不再过多介绍,如果想更详细了解其实现,可以查看其源码。
下面要介绍的LinkedList适用于:查找较少,修改较多的情况(这与LinkedList的链式结构是有关系的)。
-------------------------------
LinkedList是链表结构的实现形式(内部存储结构是一个链表形式):
存储结构图示
LinkedList的类结构
public class LinkedList <E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList的成员变量
private transient Entry<E> header = new Entry<E>(null, null, null);//链表的头结点 private transient int size = 0;//链表中元素的个数
LinkedList的构造方法
/** * 构造一个空链表 */ public LinkedList() { header.next = header.previous = header; } /** * 通过传入一个集合初始化新链表 */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
addAll方法
public boolean addAll(int index, Collection<? extends E> c) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); Object[] a = c.toArray(); int numNew = a.length; if (numNew==0) return false; modCount++; Entry<E> successor = (index==size ? header : entry(index));//后继结点,如果index==size时,后继结点指向header头结点 Entry<E> predecessor = successor.previous;//前驱结点 for (int i=0; i<numNew; i++) {//把集合元素连成一个双向子链表 Entry<E> e = new Entry<E>((E)a[i], successor, predecessor); predecessor.next = e; predecessor = e; } successor.previous = predecessor;//“原始的后继结点"的前驱指向新子链表的最后一个结点 size += numNew;//更新size大小 return true; }
LinkedList的节点存储结构
private static class Entry<E> {//以内部类的形式定义Entry 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; } }
------------------------
LinkedList的get操作
//get操作,调用entry(index)方法,获得位置index位置的Entry对象 public E get(int index) { return entry(index).element; } //通过index得到指定位置的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)) {//优化了查找操作,如果index<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; }
LinkedList的add操作
添加新元素到链表的末端,图示如下:
//add操作,把元素添加到链表的未段 public boolean add(E e) { addBefore(e, header); return true; }
//把新元素e添加到entry的前面,当entry为header头结点时,相当于添加到链表的末端,如上图所示 private Entry<E> addBefore(E e, Entry<E> entry) { Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);//以entry作为后继,以entry的前驱作为前驱 newEntry.previous.next = newEntry;//更新引用 newEntry.next.previous = newEntry; size++;//元素个数 加1 modCount++;//修改次数 加1 return newEntry; }
----------------------------
LinkedList的delete操作
删除元素E3,图示如下:
//remove操作,先调用entry(index)方法(上面有介绍)获得Entry对象,然后调用remove(entry) public E remove(int index) { return remove(entry(index)); } //执行删除操作 private E remove(Entry<E> e) { if (e == header) throw new NoSuchElementException(); E result = e.element; e.previous.next = e.next;//改变e前驱结点的next引用 e.next.previous = e.previous;//改变e后继结点的previous引用 e.next = e.previous = null;//把e置空,便于GC回收 e.element = null; size--;//元素个数 减1 modCount++;//修改次数 加1 return result; }----------
另外,由于LinkedList实现了双向队列Deque接口,所以也具有队列的相关操作,可以当做一个队列使用。
发表评论
-
Nio Socket
2013-05-16 05:53 0asfda -
结合jdk源码解读,Error Exception
2013-05-10 04:00 0/* * @(#)Error.java 1.17 05/11 ... -
从不同的角度,重新审视class和interface
2013-05-07 03:40 0java开发中,对应class和interface的基本区别都 ... -
java.lang.Object
2013-05-07 03:35 0/* * @(#)Object.java 1.73 06/0 ... -
反射机制+类加载机制
2013-02-18 01:30 0反射机制+类加载机制 -
并发专题----使用开源软件Amino构建并发应用程序/多线程运行时分析工具MTRAT
2013-02-14 00:50 1341使用开源软件构建并发 ... -
并发专题 ---- 线程安全
2013-02-14 00:50 718线程安全 ================== ... -
并发专题 --- 锁
2013-02-14 00:50 778相比于synchronized,ReentrantLock 提 ... -
并发专题 ----(JMM)java内存模型
2013-02-14 00:50 507Java 内存模型 ------------ ... -
并发专题 ---java.util.concurrent 包
2013-02-13 02:26 1797java.util.concurrent 包 原 ... -
集合框架 Queue篇(8)---PriorityBlockingQueue、SynchronousQueue
2013-02-07 12:40 1270Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(7)---LinkedBlockingDeque
2013-02-07 12:40 829Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(6)---LinkedBlockingQueue
2013-02-07 12:39 801Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(5)---ArrayBlockingQueue
2013-02-06 10:39 674Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(4)---阻塞队列和生产者-消费者模式、DelayQueue
2013-02-06 10:39 965Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(3)---ConcurrentLinkedQueue
2013-02-06 10:38 1007Queue ------------ 1.ArrayDequ ... -
集合框架 Queue篇(2)---PriorityQueue
2013-02-06 10:38 800Queue ------------ 1.ArrayDeq ... -
集合框架 Queue篇(1)---ArrayDeque
2013-02-06 10:38 898Queue ------------ 1.ArrayDeq ... -
集合框架 Set篇---HashSet、LinkedHashSet、TreeSet、CopyOnWriteArraySet、ConcurrentSkipList
2013-02-05 08:43 1446Set --------- 1.HashSet 2.Link ... -
集合框架 List篇(2)---CopyOnWriteArrayList
2013-02-05 08:43 818List ----------- 1.ArrayList(jd ...
相关推荐
超全Java集合框架讲解 - 超全Java集合框架讲解 - 集合框架总览 - Iterator Iterable ListIterator - Map 和 Collection 接口 - Map 集合体系详解 - HashMap - LinkedHashMap - TreeMap - WeakHashMap - ...
Java集合框架中的List接口是一种有序的集合,它可以存储重复的元素。它是Collection接口的子接口,提供了一系列可以对列表进行操作的方法,如添加、插入、删除、获取元素等。List接口还可以通过索引访问元素,类似于...
该视频课件包括java基础集合框架之迭代器、List集合、ListIterator、Vector、ArrayList、LinkedList及HashSet等,详细课程内容如下>>
3)了解List接口及主要实现类(ArrayList、LinkedList、Vector) 4)了解Map接口及主要实现类(HashMap、TreeMap、HashTable) 二、实验内容及步骤 1、编写程序练习将以下5个Person类的对象放在一个HashSet中。 姓名...
常见的集合框架:Collection接口和Map接口 以及常见的List接口下实现的ArrayLIst集合,LinkedList集合,Set接口下的HashSet集合和LinkedHashSet集合, Map接口下实现的HashMap集合和LinkedHashMap集合
1.集合框架结构图 1 2.两种特殊的Java容器类List和Set分析 2 3. Collection 接口: 2 4.Iterator 接口: 3 5.List接口: 3 5.1 LinkedList类: 5 5.2 ArrayList类: 5 6.Set接口: 5 7.Map接口: 6 8....
剖析⾯试最常⻅问题之 Java 集合框架 集合概述 Java 集合概览 从下图可以看出,在 Java 中除了以 Map 结尾的类之外, 其他类都实现了 Collection 接⼝。 并且,以 Map 结尾的类都实现了 Map 接⼝。 说说 List,Set,...
java集合在日常开发中经常用到,对基础的掌握尤其重要,其中List,Set,Map的作用以及使用的场景和分类描述,其中Arraylist 与 LinkedList 区别,HashSet与TreeSet与LinkedHashSet对⽐,LinkedHashMap和HashMap,...
List、Set、Queue和Map是Java集合框架中的四个主要接口,它们各自具有不同的特点和用途。 1. List(列表): - 允许重复元素。 - 具有按照元素插入顺序维护的有序集合。 - 可以通过索引访问和操作元素。 - 常见实现类...
实现类:红色Collection|_____Set(HashSet)| |_____SortedSet(TreeSet)|_____List(LinkedList,ArrayList) Collection:集合层次中的根接口,JDK没有提供这个接口的实现类。Set:不能包含重复的元素,子接口SortedSet是...
1.ArrayList: 底层是数组结构、查询快、增删慢、不同步 添加第一个元素的时候,创建默认个数是10个,如果超出了10个,就创建一个长度为 10+10>>1=15的数组 2.LinkedList: 底层是链表结构、查询慢、增删快、不同步。...
包装类 String 类 字符串的特性 String 类的常见方法 StringBuffer 类 Math 类 Arrays 类 System 类 日期类包括1代2代3代 集合 集合的框架体系 Collection 接口和常用方法 Collection 接口实现类的特点 List 接口和...
14、JAVA集合框架之list接口、LinkedList类、ArrayList类、Vector类 15、JAVA集合框架之Set接口、HashSet类、TreeSet类 16、JAVA集合框架之Map接口、HashMap类、Trelap类、Hashtable类 17、JAVA异常Exception 18...
官方翻译:大小可变数组实现List接口的。 实现了所有可选列表操作,并允许所有元素,包括null。 除了实现List接口,此类提供方法来操作在内部用于存储列表中的阵列的大小。...这个类是成员的Java集合框架
1.请写出ArrayList,LinkedList,HashMap之间的区别和联系 本题侧重与对android集合框架的认识程度 这里进行解析 java集合框架Collection collection是集合框架的根,定义了集合操作的通用行为 继他之后存在四个子接口...
Java 集合框架 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的地址。 链表可分为单向链表和双向链表。 一个单向链表包含两个...
集合框架总览 -、Iterator Iterable ListIterator 二、Map 和 Collection 接口Map 集合体系详解 HashMap LinkedHashMap TreeMap WeakHashMap Hashtable Collection 集合体系详解 Set 接口 AbstractSet 抽象类...
泛型集合12.3.4 泛型集合泛型的场景:定义泛型:12.3.5 Colletions工具类 12.3.4 泛型集合 概念:参数化类型、类型安全的集合,强制集合元素的类型必须一致; 特点: 编译时即可检查,而非运行时抛出异常; 访问时,...
set, list, queue这些接口间的区别,set不可重复, arraylist的实现和linkedlist的实现区别,HashMap, HashTable。涉及到各种效率问题等,里面最好阅读一下源码 集合的遍历方法和使用iterator来遍历的区别,集合...