焦作市网站建设_网站建设公司_Banner设计_seo优化

List接口

List 列表是Collection集合的子接口，List是有序、可索引、可重复元素的集合。

1. 有序：是指List中的元素按顺序依次添加
2. 可索引：是指List中的元素可以像数组一样，通过索引获取元素
3. 可重复：是指List中的元素可重复添加

List有三种实现类：

1. ArrayList: 数组实现，随机访问快，增删慢（需要移动元素）
2. LinkedList：链表实现，增删快，随机访问慢
3. Vector： 线程安全但性能较低（已较少使用）

List是Collection集合的子接口，则自然继承了Collection集合的方法。由于List具有有序、可索引、可重复元素的独特特点，因此额外有一些跟索引有关的方法，常见方法如下：

Eget(intindex)// 获取指定索引的元素Eremove(intindex)// 删除指定索引的元素，返回被删除的元素对象Eset(intindex,Eelement)// 修改指定索引的元素，返回被修改的元素对象（原元素）voidadd(intindex,Eelement)// 在指定索引添加元素，原索引及之后的元素索引往后移

publicclassDemo0{publicstaticvoidmain(String[]args){// 创建列表对象Listlist=newArrayList();// 添加元素list.add("hello");list.add("world");list.add("java");// 获取指定索引的元素System.out.println(list.get(1));// world// 在list指定位置添加元素list.add(1,"zhang");System.out.println(list);// [hello, zhang, world, java]// 删除指定索引的元素System.out.println(list.remove(1));// zhangSystem.out.println(list);// [hello, world, java]// 修改指定索引的元素System.out.println(list.set(0,"hi"));// 返回原被修改的元素 hello System.out.println(list); // [hi, world, java]}}

需要注意，List有两个remove方法，但是返回类型和形参不同，并不是方法重写。

publicclassDemo4{publicstaticvoidmain(String[]args){List<String>list=newArrayList<>();list.add("hello");list.add("world");list.add("java");// List接口中的remove方法: E remove(int index)Strings=list.remove(1);// 删除指定索引的元素，返回被删除的元素System.out.println(s);// worldSystem.out.println(list);// [hello, java]// Collection接口中的remove方法: boolean remove(Object o)booleanb=list.remove("java");// 删除指定元素，返回布尔值System.out.println(b);// trueSystem.out.println(list);// [hello]}}

List 除了支持Collection集合的迭代器遍历、增强型for循环遍历方法外，还支持普通for循环遍历，以及ListIterator列表迭代器遍历。比如：

publicclassDemo5{publicstaticvoidmain(String[]args){// 创建List列表对象List<String>list=newArrayList<>();// 添加元素list.add("hello");list.add("world");list.add("java");// 迭代方式1：用迭代器IteratorIterator<String>iterator=list.iterator();// 创建迭代器对象while(iterator.hasNext()){Stringelement=iterator.next();System.out.println("当前元素: "+element);}System.out.println("-----------------");// 迭代方式2：用增强for循环for(Stringelement:list){System.out.println("当前元素: "+element);}// 迭代方式3：用普通for循环for(inti=0;i<list.size();i++){Stringelement=list.get(i);System.out.println("当前元素: "+element+" 当前索引为："+i);}System.out.println("-----------------");// 迭代方式4：用列表迭代器ListIteratorListIterator<String>listIterator=list.listIterator();while(listIterator.hasNext()){Stringelement=listIterator.next();System.out.println("当前元素: "+element);}}}

我们知道Iterator迭代器是一个接口，核心方法有：hasNext()、next()，另外有个remove()方法，可以实现集合在迭代遍历过程中，安全的删除集合元素，解决了Collection对象使用自己的remove()方法造成的异常问题。但是，Iterator接口并没有提供添加元素的方法，让集合在迭代遍历中途安全的添加元素。

而ListIterator这个接口继承Iterator，除了继承hasNext()、next()、remove()方法外，还额外提供一个set(E e)、add(E e)方法，让List在迭代遍历中途，也能够安全的设置、添加元素。

add(Ee):// 将元素插入到迭代器当前位置（即下一次next()调用将返回的元素之前）set(Ee):// 替换最后一次访问的元素

publicclassDemo6{publicstaticvoidmain(String[]args){// 创建列表对象List<String>list=newArrayList<>();// 添加元素list.add("hello");list.add("world");list.add("java");// 用Iterator迭代器遍历列表，并删除元素Iterator<String>it=list.iterator();while(it.hasNext()){Strings=it.next();System.out.println(s);// 打印遍历的元素if("hello".equals(s)){// 以下删除元素会抛出ConcurrentModificationException异常// list.remove(s);it.remove();// 使用Iterator的remove方法安全删除元素// 以下添加元素会抛出ConcurrentModificationException异常// list.add("python");}}System.out.println(list);// 打印列表 [world, java]System.out.println("----------------");// 创建另外一个列表对象List<String>list2=newArrayList<>();// 添加元素list2.add("hello");list2.add("world");list2.add("java");// 用ListIterator迭代器遍历列表，并删除元素、添加元素ListIterator<String>lit=list2.listIterator();while(lit.hasNext()){Strings=lit.next();System.out.println(s);// 打印遍历的元素if("hello".equals(s)){// 以下删除元素会抛出ConcurrentModificationException异常// list2.remove(s);lit.remove();// 使用ListIterator的remove方法安全删除元素// 以下添加元素会抛出ConcurrentModificationException异常// list2.add("python");lit.add("python");// 使用ListIterator的add方法安全添加元素}}System.out.println(list2);// 打印列表 [world, java, python] }}

List有4种遍历方式，在实际编程过程中，选择哪一种呢？

如果在遍历过程中需要用到索引，则需要选择普通for循环；
如果在遍历过程中，需要安全的删除元素，则可以使用Iterator迭代器或者ListIterator列表迭代器遍历；
如果在遍历过程中，需要安全的添加元素，则只能使用ListIterator列表迭代器遍历；

List相关的数据结构

数据结构是程序在内存中组织数据存储的方式，常见的数据结构有：栈、队列、数组、链表等。

栈

栈通常只在一端（栈顶）进行插入和删除操作，另一端（栈底）是封闭的。

栈可以想象成一个桶，数据是一层一层的放到桶里去。先进入栈的数据，是相对在底层，后进入栈的数据，相对在顶层。而数据要出栈，需要先把上层的数据拿出来。因此，越前面入栈的数据，出来得越晚，而越晚进入栈的数据，越靠近栈顶，越容易出栈。

即，栈具有先进后出，后进先出的特点。

栈的数据添加叫做入栈或压栈，站的数据移出叫做出栈或弹栈。

队列

队列可以想象成一个两边都畅通的管道，数据从管道一边进入，从另一边出去。先进入队列的数据，越靠前，越先出队列。

即，队列具有先进先出，后进后出的特点。

数组

数组是在内存中开辟连续存储空间的数据结构。由于是连续的存储空间，因此数组可以用索引快速检索到对应内存空间的数据。

数据有一个缺点，就是申明了数组大小后，数组长度就确定了。数组要存储更多数据，则需要申明一个新数组，然后把原数组内的数据都复制到新的数组。

另外，如果用数组存储有序的数据，虽然用索引检索的速度很快，但是插入新数据、删除新数据的速度很慢，这是因为在特定索引（顺序位置）增加新数据后，或者在特定索引（顺序位置）删除数据后，索引后的全部数据都要移动位置。也就是说， 链表的“索引检索”通常不如数组直接，因为需要从头遍历。

综上所述，数组的特点是索引检索很快，增、删很慢。

链表

链表可以想象为铁链，是用铁环（节点）组成的一条有序的链条。链表在内存中，是用一个个分散的节点组成的。每个链表节点中，都有这个节点存储的数据，和指向下一个节点的引用（双向链表还有指向上一个节点的引用）。

链表要插入数据，如果是在链表首、尾插入，则非常快，因为只需要在第一个节点或者最后一个节点修改一下对插入新节点的引用即可。如果是在某个索引插入，也比较快，就只需要从前顺序或从后逆序（双向链表才可以）找到待插入的索引，只需要断除原两个节点的引用，将新节点的引用相互链接即可完成插入。相比与数组插入数据需要移动其他数据，链表的插入速度快不少。删除数据同理。

链表是由内存中一个个节点相互链接组成的，因此要按索引顺序检索数据，相对较慢，因为需要从首节点正序或尾节点逆序，一个一个节点引用查找的方式去做检索。

综上所述，链表的特点是增、删很快，但是索引检索很慢。

ArrayList源码分析

ArrayList是List接口的实现类，底层实现是采用数组作为数据结构，动态进行扩容。因此，ArrayList具有查询速度快（基于数组索引查询）、增加/删除较慢（需要动态扩容或者缩容，需要大量移动索引后的数组元素）。

ArrayList类有个int size实例属性，表示ArrayList对象中元素的个数，以及默认添加元素所在数组位置的索引。还有个Object[] elementData实例属性，表示存储元素的Object数组。

为了加深对ArrayList的底层实现原理的理解，现模拟ArrayList实例添加数据，结合源码进行分析。

创建新ArrayList对象

publicclassDemo12{publicstaticvoidmain(String[]args){List<String>list=newArrayList<>();// 创建新ArrayList对象}}

在创建新ArrayList对象时，会调用ArrayList的无参构造方法：

privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};publicArrayList(){this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

从上述源码来看，调用无参构造方法后，实例属性elementData是一个空数组，而实例属性size会被默认初始化，int类型则是默认值0。

ArrayList对象添加1个元素

publicclassDemo12{publicstaticvoidmain(String[]args){List<String>list=newArrayList<>();// 创建新ArrayList对象list.add("hello");// 添加第一个元素}}

在为新ArrayList对象，添加第一个元素时，会调用add()方法：

// 将指定元素追加到此列表的末尾publicbooleanadd(Ee){modCount++;add(e,elementData,size);returntrue;}

modCount是继承自AbstractList抽象类的实例属性，用于记录List结构性修改的次数，主要用于迭代器并发修改检测。此处暂不展开。

add()方法调用时，会调用私有的辅助的add()方法：

privatevoidadd(Ee,Object[]elementData,ints){if(s==elementData.length)elementData=grow();elementData[s]=e;size=s+1;}

由于目前是初始化，元素为空的ArrayList实例，形参e为待添加的元素"hello"、elementData为空数组、s为0。因此满足条件s == elementData.length，执行elementData = grow()。此时调用grow()方法，并将新的数组赋值给elementData。

privateObject[]grow(){returngrow(size+1);}

grow()扩容方法，会调用一个私有的辅助grow()方法：

/** * 增加容量以确保它至少可以容纳由最小容量参数指定的元素数量。 * * @param minCapacity 所需的最小容量 * @throws OutOfMemoryError 如果 minCapacity 小于零 */privateObject[]grow(intminCapacity){intoldCapacity=elementData.length;if(oldCapacity>0||elementData!=DEFAULTCAPACITY_EMPTY_ELEMENTDATA){intnewCapacity=ArraysSupport.newLength(oldCapacity,minCapacity-oldCapacity,/* 最小增长 */oldCapacity>>1/* 首选增长 */);returnelementData=Arrays.copyOf(elementData,newCapacity);}else{returnelementData=newObject[Math.max(DEFAULT_CAPACITY,minCapacity)];}}

由于目前是初始化，元素为空的ArrayList实例，形参minCapacity为1（size为0，实参为size + 1）。局部变量oldCapacity为elementData.length，即为0。

oldCapacity 为0，DEFAULTCAPACITY_EMPTY_ELEMENTDATA为空数组，elementData为空数组，因此条件oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA为false，执行else代码块：

return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];

ArrayList定义有：

/** * 默认初始容量。 */privatestaticfinalintDEFAULT_CAPACITY=10;

minCapacity为1，DEFAULT_CAPACITY常量为10，所以Math.max(DEFAULT_CAPACITY, minCapacity)应该是Math.max(10, 1) = 10

因此新创建一个容量为10的数组进行返回。

这说明了，ArrayList在添加第一个元素时，会创建一个长度为10的数组用于存储元素。

回到待执行的方法：

privatevoidadd(Ee,Object[]elementData,ints){if(s==elementData.length)elementData=grow();elementData[s]=e;size=s+1;}

此时ArrayList对象中的实例属性elementData指向长度为10的数组。

执行elementData[s] = e，即数组第0索引，指向被添加的元素"hello"，完成元素添加操作。

执行完毕后，size + 1，ArrayList对象实例属性size为1，表明ArrayList对象有1个元素，下一个待添加的元素对象，存储到数组索引2。

LinkedList源码分析

LinkedList是List接口的实现类，底层实现是采用双向链表作为数据结构。因此，LinkedList的增加、删除较快，但是查询速度慢。

因为LinkedList采用双向链表，因此首、尾插入、获取或删除元素都即可，LinkedList额外提供了几个独有的特殊方法：

// 头部voidaddFirst(Ee)// 将元素插入列表开头EremoveFirst()// 移除并返回第一个元素EgetFirst()// 返回第一个元素// 尾部voidaddLast(Ee)// 将元素插入列表末尾EremoveLast()// 移除并返回最后一个元素EgetLast()// 返回最后一个元素

LinkedList有三个实例属性：

1. int size，表示LinkedList对象中元素的个数
2. Node< E> first，指向链表的第一个节点
3. Node< E> last，指向链表的最后一个节点

LinkedList使用双向链表作为数据，链表中的节点，有三个部分：

1. 存储元素对象
2. 指向下一个节点
3. 指向上一个节点

privatestaticclassNode<E>{Eitem;Node<E>next;Node<E>prev;Node(Node<E>prev,Eelement,Node<E>next){this.item=element;this.next=next;this.prev=prev;}}

为了加深对LinkedList的底层实现原理的理解，现模拟LinkedList实例添加数据，结合源码进行分析。

创建新LinkedList对象

publicclassDemo12{publicstaticvoidmain(String[]args){LinkedList<String>list=newLinkedList<>();// 创建新LinkedList对象}}

创建新LinkedList对象，会调用LinkedList的无参构造方法：

publicLinkedList(){}

此时，LinkedList对象的实例属性会初始化，实例属性size为0，first为null，last为null。

LinkedList对象添加1个元素

publicclassDemo12{publicstaticvoidmain(String[]args){LinkedList<String>list=newLinkedList<>();// 创建新LinkedList对象list.add("hello");}}

对LinkedList对象添加1个元素，会调用方法：

// 添加元素到列表尾部，等同于addLast方法publicbooleanadd(Ee){linkLast(e);returntrue;}

此时会调用linkLast方法：

voidlinkLast(Ee){finalNode<E>l=last;finalNode<E>newNode=newNode<>(l,e,null);last=newNode;if(l==null)first=newNode;elsel.next=newNode;size++;modCount++;}

首先将实例属性last赋值给局部变量l，由于LinkedList对象没有元素，此时last和l都是null。

然后new一个节点new Node<>(l, e, null)，这个新节点实例属性prev（用于指向上个节点）为l，即新节点指向null，实例属性item为待添加的元素“hello”，实例属性next（用于指向下一个节点）为null。

last = newNode，将LinkedList对象实例属性last指向新添加的节点。

由于局部变量l此时为null，因此执行条件分支if代码体first = newNode，将first也指向新添加的节点。

LinkedList对象实例属性size++，即元素数量+1。

此时，LinkedList对象的实例属性size为1，first和last都指向添加的第一个元素。

LinkedList对象添加第二个元素

publicclassDemo12{publicstaticvoidmain(String[]args){LinkedList<String>list=newLinkedList<>();// 创建新LinkedList对象list.add("hello");// 添加第一个元素list.add("world");// 添加第二个元素}}

对LinkedList对象添加第二个元素，会调用方法：

// 添加元素到列表尾部，等同于addLast方法publicbooleanadd(Ee){linkLast(e);returntrue;}

此时会调用linkLast方法：

voidlinkLast(Ee){finalNode<E>l=last;finalNode<E>newNode=newNode<>(l,e,null);last=newNode;if(l==null)first=newNode;elsel.next=newNode;size++;modCount++;}

首先将实例属性last赋值给局部变量l，此时last是指向刚添加的第一个元素所在的node1。

然后new一个节点new Node<>(l, e, null)，这个新节点实例属性prev（用于指向上个节点）为l，即新节点指向第一个元素所在的node1，实例属性item为待添加的元素“world”，实例属性next（用于指向下一个节点）为null。

last = newNode，将LinkedList对象实例属性last指向新添加的节点（之前指向node1）。

由于局部变量l此时指向node1，因此执行条件分支else代码体l.next = newNode，将l.next也就是node1的next执行新节点。

LinkedList对象实例属性size++，即元素数量+1。

此时，LinkedList对象的实例属性size为2，first指向第一个元素所在节点node1，last指向第二个元素所在节点node2。