目录
一、链表
1. 链表的概念及结构
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
二.LinkedList的使用
1.LinkedList概念及结构
2. LinkedList的构造
3. LinkedList的方法
三. ArrayList和LinkedList的区别
一、链表
1. 链表的概念及结构
链表是一种
物理存储结构上非连续存储结构,数据元素的
逻辑顺序是通过链表中的
引用链接次序实现的
data表示数据;
next表示指针,它总是指向自身的下一个结点,对于只有一个结点的存在,这个next指针则永远指向自身,对于一个链表的尾部结点,next永远指向开头。
注意:
- 从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续
- 现实中的结点一般都是从堆上申请出来的
- 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
二.LinkedList的使用
1.LinkedList概念及结构
LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。
在集合框架中,LinkedList也实现了List接口
【说明】1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口,因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)
5. LinkedList比较适合任意位置插入的场景
2. LinkedList的构造
代码:
public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}
3. LinkedList的方法
代码:
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
System.out.println(list);
// 在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.out.println(list);
list.remove(); // remove(): 删除第一个元素,内部调用的是removeFirst()
list.removeFirst(); // removeFirst(): 删除第一个元素
list.removeLast(); // removeLast(): 删除最后元素
list.remove(1); // remove(index): 删除index位置的元素
System.out.println(list);
// contains(elem): 检测elem元素是否存在,如果存在返回true,否则返回false
if(!list.contains(1)){
list.add(0, 1);
}
list.add(1);
System.out.println(list);
System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
int elem = list.get(0); // get(index): 获取指定位置元素
list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
System.out.println(list);
// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
List<Integer> copy = list.subList(0, 3);
System.out.println(list);
System.out.println(copy);
list.clear(); // 将list中元素清空
System.out.println(list.size());
}
三. ArrayList和LinkedList的区别
由于
ArrayList其底层是一段连续空间,当
在ArrayList
任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后
搬移,时间复杂度为
O(n),效率比较低,因此
ArrayList
不适合做任意位置插入和删除比较多的场景。因此java 集合中又引入了LinkedList,即链表结构,
LinkedList
适合做任意位置插入和删除比较多的场景。