6. LinkedList与链表

一、ArrayList的缺陷

通过源码知道，ArrayList底层使用数组来存储元素，由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。所以，java集合中又引入了LinkedList，即链表结构。

二、链表

1. 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1.1 单向或者双向 

1.2 带头或者不带头

1.3 循环或者非循环

重点掌握两种:  

• 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
• 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2. 链表的实现

import java.util.List;public class MySingleLinkedList {static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//代表链表的头节点public void createList() {ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}public void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}/*** 从指定位置 newHead 开始打印链表* @param newHead*/public void display(ListNode newHead) {ListNode cur = newHead;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}public int size(){int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;}public void addFirst(int val) {ListNode node = new ListNode(val);node.next = head;head = node;}public void addLast(int val) {ListNode node = new ListNode(val);if(head == null) {head = node;return;}ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}public void addIndex(int index,int val) {//1.判断index的合法性try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}//2.index == 0  || index == size()if(index == 0) {addFirst(val);return;}if(index == size()) {addLast(val);return;}//3. 找到index的前一个位置ListNode cur = findIndexSubOne(index);//4. 进行连接ListNode node = new ListNode(val);node.next = cur.next;cur.next = node;}private ListNode findIndexSubOne(int index) {int count = 0;ListNode cur = head;while (count != index-1) {cur = cur.next;count++;}return cur;}private void checkIndex(int index) throws IndexNotLegalException{if(index < 0 || index > size()) {throw new IndexNotLegalException("index不合法");}}public boolean contains(int val) {ListNode cur = head;while (cur != null) {if(cur.val == val) {return true;}cur = cur.next;}return false;}public void remove(int val) {if(head == null) {return;}if(head.val == val) {head = head.next;return;}ListNode cur = head;while (cur.next != null) {if(cur.next.val == val) {ListNode del = cur.next;cur.next = del.next;return;}cur = cur.next;}}public void removeAllKey(int val) {//1. 判空if(this.head == null) {return;}//2. 定义prev 和 curListNode prev = head;ListNode cur = head.next;//3.开始判断并且删除while(cur != null) {if(cur.val == val) {prev.next = cur.next;//cur = cur.next;}else {prev = cur;//prev = prev.next;//cur = cur.next;}cur = cur.next;}//4.处理头节点if(head.val == val) {head = head.next;}}public void clear() {//head = null;ListNode cur = head;while (cur != null) {ListNode curN = cur.next;//cur.val = null;cur.next = null;cur = curN;}head = null;}
}

三、链表面试题

1. 删除链表中等于给定值 val 的所有节点。

2. 反转一个单链表。

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

4. 输入一个链表，返回该链表中倒数第k个结点。

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

7. 链表的回文结构。

8. 输入两个链表，找出它们的第一个公共结点。

9. 给定一个链表，判断链表中是否有环。

10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL。

四、LinkedList的模拟实现

public class MyLinkedList {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;//头插法public void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {head = node;last = node;//return;}else {node.next = head;head.prev = node;head = node;}}//尾插法public void addLast(int data){ListNode node = new ListNode(data);if(head == null) {head = last = node;}else {last.next = node;node.prev = last;last = node;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){if(index < 0 || index > size()) {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;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}private ListNode searchIndex(int index) {ListNode cur = head;int count = 0;while (count != index) {cur = cur.next;count++;}return cur;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur =cur.next;}return false;}//得到单链表的长度public int size(){int count = 0;ListNode cur = head;while (cur != null) {count++;cur =cur.next;}return count;}public void display(){ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur =cur.next;}System.out.println();}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {if(cur == head) {head = head.next;//判断 头节点是不是1个if(head != null) {head.prev = null;}else {last = null;}}else {cur.prev.next = cur.next;if(cur.next == null) {//cur.prev.next = cur.next;last = cur.prev;}else {//cur.prev.next = cur.next;cur.next.prev = cur.prev;}}return;}else {cur = cur.next;}}}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {if(cur == head) {head = head.next;//判断 头节点是不是1个if(head != null) {head.prev = null;}else {last = null;}}else {cur.prev.next = cur.next;if(cur.next == null) {//cur.prev.next = cur.next;last = cur.prev;}else {//cur.prev.next = cur.next;cur.next.prev = cur.prev;}}}cur = cur.next;}}public void clear(){ListNode cur = head;while (cur != null) {ListNode curN = cur.next;cur.next = null;cur.prev = null;cur = curN;}head = null;last = null;}}

五、LinkedList的使用

1. 什么是LinkedList

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

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

【说明】

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

2. LinkedList的使用

2.1 LinkedList的构造

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);
}

2.2 LinkedList的其他常用方法介绍

2.3 LinkedList的遍历

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);list.add(8);System.out.println(list.size());//foreach遍历for (int e:list) {System.out.print(e + ", ");  // 1, 2, 3, 4, 5, 6, 7, 8, }System.out.println();//使用迭代器遍历——正向遍历ListIterator<Integer> it = list.listIterator();while (it.hasNext()){System.out.print(it.next() + ", ");  // 1, 2, 3, 4, 5, 6, 7, 8, }System.out.println();//使用反向迭代器——反向遍历ListIterator<Integer> rit = list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() + ", ");  // 8, 7, 6, 5, 4, 3, 2, 1, }System.out.println();}
}

六、ArrayList和LinkedList的区别