什么是LinkedList
LinkList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将结点连接起来了，因此在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中，LinkedList也实现了List接口。
说明：
1.LinkedList实现了List接口
2.LinkedList的底层实现了双向链表
3.LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4.LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5.LinkedList比较适合任意位置的插入场景
LinkedList的使用
LinkedList的构造
| 方法 | 解释 |
| LinkedList() | 无参构造 |
| public LinkedList(Collection<? extends E> c) | 使用其它集合容器中元素构造List |
举个例子：
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Test { public static void main(String[] args) { //构造一个空的LinkedList List<Integer> list1 = new LinkedList<>(); //构建一个ArrayList数组，并添加元素 List<String> list2 = new ArrayList<>(); list2.add("JavaSE"); list2.add("JavaWeb"); list2.add("JavaEE"); //使用ArrayList构造LinkedList List<String> list3 = new LinkedList<>(list2); } }
LinkedList的其他常用方法的介绍
| 方法 | 解释 |
| boolean add(E e) | 尾插元素e |
| void add(int index, E element) | 将e插入index的位置 |
| boolean addAll(Collection<? extends E> c) | 尾插c中的元素 |
| E remove(int index) | 删除index位置的元素 |
| boolean remove(Object o) | 删除遇到的第一个o |
| E get(int index) | 获取下标index位置的元素 |
| E set(int index, E element) | 将下标为index位置元素设置为element |
| void clear() | 清空 |
| boolean contains(Object o) | 判断o是否在线性表中 |
| int indexOf(Object o) | 返回第一个o所在的下标 |
| int lastIndexOf(Object o) | 从后向前找第一个o的位置，返回其下标 |
| List<E> subList(int fromIndex, int toIndex) | 截取部分list |
import java.util.LinkedList; import java.util.List; public class Test { 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());//7 System.out.println(list);//1 2 3 4 5 6 7 //在起始位置插入零 list.add(0, 0);//add(elem):在index位置插入elem System.out.println(list);//0 1 2 3 4 5 6 7 list.remove();//remove():删除第一个元素，内部调用的是removeFirst() list.removeFirst();//removeFirst():删除第一个元素 list.removeLast();//removeLast():删除最后一个元素 list.remove(1);//remove(index):删除index位置的元素 System.out.println(list);//2 4 5 6 //contains(elem):检测elem元素是否存在，如果存在返回true,否则返回false if(!list.contains(1)) { list.add(0, 1); } list.add(1); System.out.println(list);//1 2 4 5 6 1 System.out.println(list.indexOf(1));//indexOf(elem):从前往后找到第一个elem的位置 //0 System.out.println(list.lastIndexOf(1));//lastIndexOf(elem):从后向前找第一个1的位置 //5 int elem = list.get(0); list.set(0, 100);//将index位置的元素设置为elem System.out.println(list);//100 2 4 5 6 1 //subList(from, to):用list中的(from, to)之间的元素构造一个新的LinkedList返回 List<Integer> copy = list.subList(0,3); System.out.println(list); System.out.println(copy);//100 2 4:注意java中是左闭右开的，所以不包含序号为三的结点 list.clear();//将list中的元素清空 System.out.println(list.size());//0 } }
LinkedList的遍历
import java.util.LinkedList; import java.util.ListIterator; public class Test { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7); System.out.println(list.size()); //foreach遍历 for(int e : list) { System.out.print(e + " "); } System.out.println(); //使用迭代器进行遍历-正向遍历 ListIterator<Integer> it = list.listIterator(); while(it.hasNext()) { System.out.print(it.next() + " "); } System.out.println(); //使用反向迭代器-反向遍历 ListIterator<Integer> rit = list.listIterator(list.size()); while(rit.hasPrevious()) { System.out.print(rit.previous() + " "); } System.out.println(); } }
补充：迭代器的是使用
import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class IteratorTest { public static void main(String[] args) { List<String> list = new ArrayList<>(); //添加元素到集合中 Iterator<String> iterator = list.listIterator(); while(iterator.hasNext()) { String element = iterator.next(); //处理元素 } iterator.remove(); } }
使用流程
1.获取集合的迭代器对象：通过调用集合的iterator方法获取迭代器对象。例如，对于ArrayList集合，可以使用iterator()方法获取迭代器对象。
2.遍历集合元素：通过使用迭代器的hasNext()和next()方法来遍历集合中的元素。hasNext()方法用于检查是否还有下一个元素，next()方法用于获取下一个元素的值。
ArrayList和LinkedList的区别
| 不同点 | ArrayList | LinkedList |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持O(N) |
| 头插 | 需要搬移元素，效率低O(N) | 只需修改引用的指向，时间复杂度为O(1) |
| 插入 | 空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
