4. LinkedList的模拟实现

java">public class MyLinkedList {static class ListNode{public int value;public ListNode prev;public ListNode next;public ListNode(int value) {this.value = value;}}public ListNode head;public ListNode last;/***查找是否包含关键字key是否在单链表中* @param key* @return*/public boolean contains(int key){if (head == null){return false;}ListNode cur = head;while (cur != null){if (cur.value == key){return true;}cur = cur.next;}return false;}/*** 得到链表的长度* @return*/public int size(){ListNode cur = head;int size = 0;while (cur != null){size++;cur = cur.next;}return size;}/*** 输出链表*/public void display(){ListNode cur = head;while (cur != null){System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}/*** 头插法* @param data*/public void addFirst(int data){ListNode node = new ListNode(data);if (head == null){head = node;last = node;return;}head.prev = node;node.next = head;head = node;}/*** 尾插法*/public void addLast(int data){ListNode node = new ListNode(data);if (head == null){head = node;last = node;}else {last.next = node;node.prev = last;last = node;}}/*** 在任意位置插入，第一个数据结点尾0号下标* @param index* @param data*/public void addIndex(int index, int data){//处理下标不合理的情况if (index < 0 || index > size()){System.out.println("输入的下标不合理");return;}//头插if (index == 0){addFirst(data);return;}//尾插if (index == size()){addLast(data);return;}//中间任意位置插ListNode cur = searchIndex(index);ListNode node = new ListNode(data);node.next = cur;node.prev = cur.prev;cur.prev.next = node;cur.prev = node;}/*** 查找下标为index的结点* @return*/private ListNode searchIndex(int index){ListNode cur = head;for (int i = 0; i < index; i++) {cur = cur.next;}return cur;}/*** 删除第一次出现的关键字key的结点* @param key*/public void remove(int key){if (head == null){return;}ListNode cur = head;while (cur != null){if (cur.value == key){//处理头节点，如果单独处理会出现越界的情况if (head.value == key){head = head.next;//判断是不是链表中只有一个结点if (head != null){head.prev = null;}else {last = null;}}else {//处理尾节点，如果单独处理会出现越界的情况cur.prev.next = cur.next;if (cur.next == null){last = cur.prev;}else {cur.next.prev = cur.prev;}}return;}else {cur = cur.next;}}}/*** 删除所有值为key的结点* @param key*/public void removeAllKey(int key){if (head == null){return;}ListNode cur = head;while (cur != null){if (cur.value == key){//处理头节点，如果单独处理会出现越界的情况if (head.value == key){head = head.next;//判断是不是链表中只有一个结点if (head != null){head.prev = null;}else {last = null;}}else {//处理尾节点，如果单独处理会出现越界的情况cur.prev.next = cur.next;if (cur.next == null){last = cur.prev;}else {cur.next.prev = cur.prev;}}}cur = cur.next;}}/*** 清空链表*/public void clear(){ListNode cur = head;while (cur != null){ListNode curN = cur.next;cur.prev = null;cur.next = null;cur = curN;}head = null;last = null;}
}

5. LinkedList的使用

5.1 什么是LinkedList

LinkedList的底层是双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

在集合框架中，LinkedList也实现了List接口，具体如下：

【说明】

1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5. LinkedList比较适合任意位置插入的场景

5.2 LinkedList的使用

5.2.1 LinkedList的构造

方法	解释
LinkedList()	无参构造
public LinkedList(Collection<?extends E>C)	使用其他集合容器中元素构造List

java"> public static void main(String[] args) {// 构造一个空的LinkedListList<Integer> list1 = new LinkedList<>();List<String> list2 = new java.util.ArrayList<>();list2.add("JavaSE");list2.add("JavaWeb");list2.add("JavaEE");// 使用ArrayList构造LinkedListList<String> list3 = new LinkedList<>(list2);}

5.2.2 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 subList(int fromIndex, int toIndex)	截取部分List

java">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);// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.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，否则返回falseif(!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位置的元素设置为elemSystem.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());}

5.2.3 LinkedList的遍历

java">    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());// 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();}

6. ArrayList和LinkedList的区别

不同点	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
头插	需要搬移元素，效率低O(N)	只需修改引用的指向，时间复杂度为O(1)
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁