List In Java

I. List 接口

java.util.List:

List 接口是 Collection 接口的子接口，用法和 Collection 大致相同
List 中元素 有序 （有序指存储和取出的元素顺序一致）
List 中元素 可重复
列表中每个元素的插入位置可以精确地控制
根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素

II. List 集合的特有功能

添加功能
- void add(int index, E element) : 在列表的指定位置插入指定元素（可选操作）。将当前处于该位置的元素（如果有的话）和所有后续元素向右移动（在其索引中加 1）
- boolean addAll(int index, Collection<? extends E> c): 在列表的指定位置插入指定集合中的元素（可选操作），原有元素右移（其索引中加指定集合的 size）
获取功能
- E get(int index): : 获取指定位置的元素（遍历时和 size() 方法结合）
- int indexOf(Object o) ：返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1
- int lastIndexOf(Object o) ：返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1
删除功能
- E remove(int index) : 删除指定位置的元素，并将此元素返回
修改功能
- E set(int index, E element) ：用指定元素替换列表中指定位置的元素，返回被修改的元素

III. ListIterator

ListIterator接口, List 集合中特有的迭代器，继承了 Iterator 接口

1. ListIterator 实例化

ListIterator 实例化只能从 ListIterator 接口的具体实现类通过下述方法实现

ListIterator listIterator(): 返回 List 中 ListIterator 实例
ListIterator listIterator(int index): 返回 List 中的 ListIterator 实例，从列表的指定位置开始

2. ListIterator 的方法

boolean hasNext() : 正向遍历列表，如果仍有元素可以迭代，则返回 true
E next() : 返回列表中的下一个元素。可以重复调用此方法来迭代此列表，或混合调用 previous 来前后移动（注意交替调用 next 和 previous 将重复返回相同的元素）
void remove() : 从迭代器指向的 collection 中移除迭代器返回的最后一个元素（可选操作）。每次调用 next 只能调用一次此方法。如果进行迭代时用调用此方法之外的其他方式修改了该迭代器所指向的 collection，则迭代器的行为是不确定的
boolean hasPrevious() : 逆向遍历列表，如果仍有元素可以迭代，则返回 true
E previous() ：返回列表中的前一个元素。可以重复调用此方法来迭代列表，或混合调用 next 来前后移动（注意交替调用 next 和 previous 将重复返回相同的元素）
int nextIndex() ：返回对 next 的后续调用所返回元素的索引。（如果列表迭代器在列表的结尾，则返回列表的大小）
int previousIndex() ：返回对 previous 的后续调用所返回元素的索引。（如果列表迭代器在列表的开始，则返回 -1）
void set(E e) ：用指定元素替换 next 或 previous 返回的最后一个元素（可选操作）。只有在最后一次调用 next 或 previous 后既没有调用 ListIterator.remove 也没有调用 ListIterator.add 时才可以进行该调用。
void add(E e) ：将指定的元素插入列表（可选操作）。该元素直接插入到 next 返回的下一个元素的前面（如果有），或者 previous 返回的下一个元素之后（如果有）；如果列表没有元素，那么新元素就成为列表中的唯一元素

注意，ListIterator 可以实现逆向遍历，但是必须先正向遍历，才能逆向遍历，一般不使用。更多的情况是使用 Collection 的 iterator 中的方法

3. 修改List的注意事项

当我们在遍历一个 List 的时候，不能在遍历期间进行修改，否则会出现 java.util.ConcurrentModificationException。

比如现在有个问题：有一个List，如果这个 List 包含 “world” 元素, 那么就添加一个 “javaee” 元素，代码如下

package org.lovian.collections.list;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

/**
 * Q: There is a list, if this list contains "world", then add one "javaee"
 *
 * @author PENG Zhengshuai
 * @lovian.org
 *
 */
public class ListIteratorTest {
	public static void main(String[] args) {
		List<String> list = new ArrayList<>();
		list.add("hello");
		list.add("world");
		list.add("java");

		ListIterator<String> ite = list.listIterator();
		while(ite.hasNext()){
			String s = ite.next();
			if(s.equals("world"))
				list.add("javaee");	// Error!!
		}

		System.out.println("List: " + list);
	}
}

然而我们发现结果是这样的：

Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
	at java.util.ArrayList$Itr.next(ArrayList.java:851)
	at org.lovian.collections.list.ListIteratorTest.main(ListIteratorTest.java:23)

这个异常是什么意思呢？这是并发修改异常。当方法检测到对象的并发修改，但不允许这种修改时，就会抛出此异常

并发修改异常产生的原因：
- 迭代器是依赖于集合而存在的，在判断成功后，集合中添加了新元素，而迭代器并没有改变，所以迭代器和集合就不同步了，所以报错了
- 简而言之，迭代器遍历元素的时候，通过集合是不能修改元素的
解决方法：
- 1.通过迭代器迭代元素，修改元素（ListIterator）
- 2.通过集合遍历元素，集合修改元素（普通 for 循环）

所以正确的代码应该如下：

package org.lovian.collections.list;

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

/**
 * Q: There is a list, if this list contains "world", then add one "javaee"
 *
 * @author PENG Zhengshuai
 * @lovian.org
 *
 */
public class ListIteratorTest {
	public static void main(String[] args) {
		List<String> list = new ArrayList<>();
		list.add("hello");
		list.add("world");
		list.add("java");

		// Use list iterator to modify list
		ListIterator<String> ite = list.listIterator();
		while(ite.hasNext()){
			String s = ite.next();
			if(s.equals("world"))
				ite.add("java ee");	// add element after ite.next
		}

		System.out.println("List: " + list);

		// Use for loop to modify list
		for(int i = 0; i < list.size(); ++i){
			String s = list.get(i);
			if(s.equals("world")){
				list.add(i+1,"another"); // add element in index of the list
				list.add("end"); // add element in the end of list
			}
		}
		System.out.println("List: " + list);
	}
}

结果是：

List: [hello, world, java ee, java]
List: [hello, world, another, java ee, java, end]

IV. List 子类

List 的常用子类： ArrayList, Vector, LinkedList

1. List 子类特点

ArrayList：
- List接口的实现
- 底层数据结构是数组 Array，大小可变
- 线程不同步，只能通过ListIterator 的方法进行并发修改，其他方式不允许（结构上增删不允许，但值的修改是可以的）
- 线程不安全，效率高
- 查询快，增删慢
Vector：（较少用）
- List接口的实现
- 底层数据结构是数组 Array，大小可变
- 线程同步（JDK1.2开始将Vector改为List的接口实现），允许并发修改
- 线程安全，效率低
- 查询比ArrayList慢，增删慢
LinkedList：
- List接口的实现，同时实现了 Deque 接口
- 底层数据结构是双向链表 LinkedList，大小可变
- 提供了栈 stack 和双向队列 queue 的操作
- 线程不同步，只能通过ListIterator 的方法进行并发修改，其他方式不允许（结构上增删不允许，包括上文的for循环，但值的修改是可以的）
- 线程不安全，效率高
- 查询慢，增删快

所以在选用 List 的子类时，一般选 ArrayList 和 LinkedList，不选 Vector，即使需要线程安全，也有其他的替代类。如果对List的元素查询频率更高，选用 ArrayList，否则选用 LinkedList

2. ArrayList

ArrayList 基本上都是 List 的操作方法

3. Vector

vector 由于在集合体系出现之前就出现了，所以它有一些特殊方法：

添加功能
- public void addElement(E e) : 类似 add 方法
获取功能
- public E elementAt(int index) : 类似 get 方法
- public Enumeration elements() : 类似迭代器

虽然 vector 保留了这些原有方法，但是由于它现在继承了 Collection 体系，所以建议用 Collection 的通用方法

package org.lovian.collections.list;

import java.util.Enumeration;
import java.util.Iterator;
import java.util.Vector;

public class VectorDemo {
	public static void main(String[] args) {
		Vector<String> v = new Vector<>();

		// add elements
		v.add("hello");
		v.addElement("world");

		// traverse a vector
		Iterator<String> ite = v.iterator();
		while(ite.hasNext()){
			String s = ite.next();
			System.out.println(s);
		}

		System.out.println("=================");

		Enumeration<String> en = v.elements();
		while(en.hasMoreElements()){
			String s = en.nextElement();
			System.out.println(s);
		}

	}
}

result

hello
world
=================
hello
world

4. LinkedList

List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null）。除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

所以 LinkedList 也具有特殊方法：

添加功能
- public void addFirst(E e) : 将指定元素插入此列表的开头
- public void addLast(E e) : 将指定元素添加到此列表的结尾
获取功能
- public E getFirst() : 返回此列表的第一个元素
- public E getLast() : 返回此列表的最后一个元素
删除功能
- public E removeFirst() : 移除并返回此列表的第一个元素
- public E removeLast() : 移除并返回此列表的最后一个元素

package org.lovian.collections.list;

import java.util.LinkedList;

public class LinkedListDemo {
	public static void main(String[] args) {
		LinkedList<String> ll = new LinkedList<>();

		// add
		ll.add("hello");
		ll.add("world");
		System.out.println(ll);
		System.out.println("=========");

		// add first
		ll.addFirst("java");
		// add last
		ll.addLast("javaee");
		System.out.println(ll);
		System.out.println("first ele: " + ll.getFirst());
		System.out.println("last ele: " + ll.getLast());
		System.out.println("=========");

		System.out.println("remove first: " + ll.removeFirst());
		System.out.println("remove last: " + ll.removeLast());
		System.out.println("=========");
		System.out.println(ll);
	}
}

result:

[hello, world]
=========
[java, hello, world, javaee]
first ele: java
last ele: javaee
=========
remove first: java
remove last: javaee
=========
[hello, world]

5. ArrayList 去除重复值

因为 ArrayList 继承了 List，所以 ArrayList 是允许重复元素的出现，那么如何去除集合中的重复值？

思路一：创建新集合

创建一个新的 list，然后一个一个将元素从旧的 list 存入新的 list。在存的过程中，判断元素是否已经存入到了新的 list 里，如果没有就添加，如果有了就跳过。这样新的 list 中，就不包含重复值了。注意 ArrayList 的 contains 方法底层是 equals 方法，所以要注意是否重写父类的 equals 方法

思路二：选择排序思想

不创建新的 list，用选择排序思想，双重循环，找出重复值，然后将重复的值移除。

for(int x = 0; x < arraylist.size()-1; x++){
	for(int y = x + 1; y < arraylist.size(); y++){
		if(arraylist.get(x).equals(arraylist.get(y))){
			arraylist.remove(y);
			y--; // 因为用remove 移除一个元素，后面的元素会补位，如果后面补位的值和get(x) 相同，那么这个值会被略过，所以要重新检查一次
		}
	}
}

Share this on

Zhengshuai PENG

[JAVA] Java 中的列表 List

List In Java

I. List 接口

II. List 集合的特有功能

III. ListIterator

1. ListIterator 实例化

2. ListIterator 的方法

3. 修改List的注意事项

IV. List 子类

1. List 子类特点

2. ArrayList

3. Vector

4. LinkedList

5. ArrayList 去除重复值

思路一：创建新集合

思路二：选择排序思想

Related Posts

Zhengshuai PENG

[JAVA] Java 中的 列表 List

List In Java

I. List 接口

II. List 集合的特有功能

III. ListIterator

1. ListIterator 实例化

2. ListIterator 的方法

3. 修改List的注意事项

IV. List 子类

1. List 子类特点

2. ArrayList

3. Vector

4. LinkedList

5. ArrayList 去除重复值

思路一： 创建新集合

思路二： 选择排序思想

Related Posts

[JAVA] Java 中的列表 List

思路一：创建新集合

思路二：选择排序思想