11.2 链表List
List是java.util包下面的一个类,用来代替数组。在数据结构链表中,我们可以看到关于链表更抽象的表述。
链表,你可以用字面意思去理解:就是一条链。链上面有很多链节,就好像自行车的链条。
类似的数据结构有数组,它也是一串的数据。链表和数组的区别在于:
List | 数组 | |
---|---|---|
容量变化 | 支持容量长度发生变化 | 一旦定义不能修改 |
方法支持 | 内置多种方法 | 没有方法可供使用 |
下面将列出List比较常见的方法:
返回类型 | 函数 | 说明 | 示例 |
---|---|---|---|
int | size() | 返回链表的长度 | int len=list.size(),这个方法和数组的length是一样的 |
boolean | add(Ojbect ob) | 将ob添加到链表末尾 | list.add("abc") |
Object | remove(int i) | 把下标为i的元素从链表中移除,返回这个被移除的元素 | list.remove(2) |
boolean | addAll(Set set) | 将一个容器里所有元素都添加到链表 | list.add(list2) |
Object | get(int i) | 取得容器里第i个元素,下标从0开始 | list.get(0)。返回的类型是Object,需要强制类型转换:String str=(String)list.get(0)这个方法类似于数组的a[0] |
void | clear() | 清空链表,此方法调用完后,链表长度为0 | list.clear() |
下面的代码是典型的遍历整个链表的方法,假设A是这个链表list的类型,链表的元素的类型是一致的,于是在链表定义的时候,就应该指定这个类型,否则会有一个警告,如下所示:
//取得链表数据,可能是数据库查找List<String> list=....;for(int i=0;i <= list.size();i++){ A a=list.get(i); a.xxx(); 其他代码....;}
这里的list就是指定了元素类型为String,那么后面的ArrayList又是什么呢?这是链表的一个具体实现,List只是一个接口,它本身没有实体。而常用的List的实现类有ArrayList和LinkedList。两者的方法一致(都是实现了接口List),但对于某些情况的性能不一致。
List<String> list=new ArrayList();List<String> list2=new LinkedList();
1.ArrayList更接近数组,对于顺序访问元素更快,例如频繁使用get,如果新增加元素,可能需要新分配内存,开销比较大
2.LinkedList对于频繁增加和删除元素性能更好
对于数据比较小的普通应用,两者的性能差距可以忽略不计。
下面是使用ArrayList的一个例子:
import java.util.ArrayList;import java.util.List;public class Test{ public static void main(String[]args){ /* 新建一个链表,具体类型是ArrayList,Integer是int的包装类,此处不能使用int,只能使用包装类 */ List<Integer> list=new ArrayList(); for(int i=0;i < 5;i++){ list.add(i); } /* 遍历 */ for(int i:list){ System.out.println(i); } }}
List和ArrayList都需要导入,可以同时用import util.java.*;导入