LinkedList与链表

ArrayList的缺陷

        在上一篇博客中，小编已经较为详细得给大家介绍了ArrayList这个结构了。但是ArrayList存在一些缺陷：由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。

        因此：java集合中又引入了LinkedList，即链表结构

---

链表

链表的概念及结构

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

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

双向 单向、带头 不带头、循环 不循环

我们主要学习：单向不带头非循环、双向不带头非循环

---

链表的实现

这里就是自己在写一些链表的方法的时候，自己动手实现一下，感受一下这个链表的内部结构。

代码展示：

package LinkedList;public class MySingleList {// 这里提供一个内部类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(34);ListNode node3 = new ListNode(45);ListNode node4 = new ListNode(56);ListNode node5 = new ListNode(67);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}/*** 下面是一个方法的实现【其实就是增删改查】*///头插法public void addFirst(int data){ListNode node = new ListNode(data);
//        // 要考虑列表为空的情况
//        if (head == null){
//            head = node;
//        }node.next = head;head = node;}//尾插法public void addLast(int data){ListNode node = new ListNode(data);// 要考虑列表为空的情况if (head == null){head = node;return;}ListNode curhead = head;while (curhead.next != null){curhead = curhead.next;}curhead.next = node;}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){ListNode curhead = head;if (index < 0 || index > size()) {System.out.println("您提供的index不合法！");return;}ListNode node = new ListNode(data);// 处理空链表情况if (head == null) {if (index == 0) {head = node;System.out.println("您的列表为空! 直接插入到第一个位置");} else {System.out.println("链表为空，index > 0 无效！");}return;}if (index == 0){addFirst(data);return;}for (int i = 0; i < index-1; i++) {curhead = curhead.next;}node.next = curhead.next;curhead.next = node;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){// 就默认列表为空就是没有ListNode curhead = head;while (curhead!=null){if (curhead.val == key){return true;}curhead = curhead.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){if (head == null) { // 处理空链表return;}// 处理删除头节点的情况if (head.val == key) {head = head.next;return;}ListNode cur = head;while (cur.next != null) { // 遍历链表if (cur.next.val == key) {cur.next = cur.next.next; // 删除当前匹配的节点return; // 只删除第一个匹配项}cur = cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){if (head == null) { // 处理空链表return;}// 处理删除所有头节点为 key 的情况while (head != null && head.val == key) {head = head.next;}// 处理删除中间或尾部的 keyListNode cur = head;while (cur != null && cur.next != null) {if (cur.next.val == key) {cur.next = cur.next.next; // 删除当前匹配的节点} else {cur = cur.next; // 只有当 cur.next 不是 key 时才移动}}}//得到单链表的长度public int size(){int ListSize = 0;ListNode curhead = head;// 来一个语句判断一下链表是否为空while (curhead != null){ListSize++;curhead = curhead.next;}return ListSize;  // 如果长度为0【即为空列表即返回这个，告诉用户这是一个空的列表】}// 清空所有链表public void clear() {this.head = null;}// 展示所有列表的数据public void display() {// 进来先判断一下链表是否为空if (head == null){System.out.println("该列表为空！");return;}ListNode curhead = head;while (curhead!=null){System.out.print(curhead.val+" ");curhead = curhead.next;}System.out.println();}}

注：小编这里的代码并不是最优的，只是起一个参考的作用。

测试代码：

package LinkedList;public class Test {public static void main(String[] args) {MySingleList mySingleList = new MySingleList();mySingleList.createList();  // 先把这个初始列表创建出来// 将列表全部展现出来mySingleList.display();// 得到单链表的长度int length = mySingleList.size();System.out.println("单链表的长度为："+length);// 进行头插mySingleList.addFirst(99);mySingleList.display();// 进行尾插mySingleList.addLast(520);mySingleList.display();// 任意位置插入mySingleList.addIndex(0, 1314);mySingleList.display();mySingleList.addIndex(8, 8989);mySingleList.display();// 查找是否包含关键字key是否在单链表当中boolean result = mySingleList.contains(99);if (result == true){System.out.println("链表中存在这个值！");}else {System.out.println("不好意思！链表中不存在这个值！");}// 删除第一次出现关键字为key的节点mySingleList.addFirst(99);mySingleList.addFirst(99);mySingleList.addLast(99);mySingleList.display();
//        mySingleList.remove(99);
//        mySingleList.display();//删除所有值为key的节点mySingleList.removeAllKey(99);mySingleList.display();}
}

测试代码不唯一，这里的测试代码也只是起一个参考作用【小编这里的方法代码和测试代码是放到了同一个包里】，大家的代码如果位置不一致，要注意限定修饰符的使用。

---

链表面试题

1. 删除链表中等于给定值 val 的所有节点。203. 移除链表元素 - 力扣（LeetCode）

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {if (head == null) { // 处理空链表return null;}// 处理删除所有头节点为 key 的情况while (head != null && head.val == val) {head = head.next;}// 处理删除中间或尾部的 keyListNode cur = head;while (cur != null && cur.next != null) {if (cur.next.val == val) {cur.next = cur.next.next; // 删除当前匹配的节点} else {cur = cur.next; // 只有当 cur.next 不是 key 时才移动}}return head;}
}

---

2. 反转一个单链表.206. 反转链表 - 力扣（LeetCode）

class Solution {public ListNode reverseList(ListNode head) {ListNode cur = head;ListNode pre = null; // 关键修改：pre 应该从 null 开始while (cur != null) {ListNode next = cur.next; // 先保存下一个节点cur.next = pre; // 反转当前节点的指向pre = cur; // 移动 pre 指针cur = next; // 继续遍历}return pre; // 反转后，pre 是新的头节点}
}

---

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

方法1：算数组长度

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public int size(ListNode head){int ListSize = 0;ListNode curhead = head;// 来一个语句判断一下链表是否为空while (curhead != null){ListSize++;curhead = curhead.next;}return ListSize;  // 如果长度为0【即为空列表即返回这个，告诉用户这是一个空的列表】}public ListNode middleNode(ListNode head) {ListNode cur = head;int index = size(head)/2;for(int i = 0; i < index; i++){cur = cur.next;}head = cur;return head;}
}

方法2：快慢指针

快指针都两步，慢指针走一步；当快指针走到末尾的时候，慢指针刚好走到中间位置；

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}
}

这个代码需要注意的点就是“空指针异常”，在判断循环条件的时候需要多加注意这个逻辑问题。

---

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

方法一：循环遍历，找到下标

 // 1.输入一个链表，输出该链表中倒数第k个结点public int return_val(int k){ListNode cur = head;for (int i = 0; i < size()-k; i++) {cur = cur.next;}return cur.val;}

方法2：快慢指针法

fast先走k-1步；fast和slow再同时走，当fast到终点的时候，slow就刚好到倒数第K个位置。

   public ListNode FindthToTail(int k){if (k <= 0 || k > size() || head == null){System.out.println("您提供的下标有误!");return null;}ListNode fast = head;ListNode slow = head;for (int i = 0; i < k-1; i++) {fast = fast.next;}while (fast.next!=null){fast = fast.next;slow = slow.next;}return slow;}

---

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

代码示例：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode headA = list1;ListNode headB = list2;ListNode nh = new ListNode();ListNode th = nh;while(headA!=null && headB!=null){if(headA.val > headB.val){th.next = headB;th = th.next;headB = headB.next;}else{th.next = headA;th = th.next;headA = headA.next;}}if(headA!=null){th.next = headA;}else{th.next = headB;}return nh.next;}
}

---

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

代码示例：

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {// write code hereListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = pHead;while(cur != null){// 这是第一次插入的情况if(cur.val<x){if(be == null){be = bs = cur;}else{be.next = cur;be = be.next;}}else{if(ae == null){ae = as = cur;}else{ae.next = cur;ae = ae.next;}}cur = cur.next;}// 第一个段没有数据if(be == null){return as;}be.next = as;// 防止最大的数据不是最后一个if(as!=null){ae.next = null; }return bs;}
}

注：在写这个代码的时候，需要注意很多细节类的东西，尤其是一些极端情况，需要多画图看。

---

7. 链表的回文结构。链表的回文结构_牛客题霸_牛客网

三个步骤：

1.找到链表的中间节点

2.翻转中间节点以后的链表

3.从前/从后开始比较

代码示例：

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode A) {// 1.找到中间位置// write code hereListNode fast = A;ListNode slow = A;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}// 2.开始反转ListNode cur = slow.next;ListNode curNext = null;while(cur!=null){curNext = cur.next;cur.next = slow;slow = cur;cur = curNext;}// 3.开始往前往后走while(A!=slow){if(A.val != slow.val){return false;}if(A.next == slow){return true;}A = A.next;slow = slow.next;}return true;}
}

注：上述代码就是前面代码的综合，当我们在写代码的时候，应该考虑到奇数和偶数的不同情况。

---

8. 输入两个链表，找出它们的第一个公共结点。160. 相交链表 - 力扣（LeetCode）

核心问题：

1.相交是Y字型

2.两个链表长度不一样主要在相交之前

3.可以先让最长链表引用先走他们的差值步

方法1：这个是小编自己画图想出来的方法

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {// 定义一个方法来求列表的长度public int size(ListNode head){int ListSize = 0;ListNode curhead = head;// 来一个语句判断一下链表是否为空while (curhead != null){ListSize++;curhead = curhead.next;}return ListSize;  // 如果长度为0【即为空列表即返回这个，告诉用户这是一个空的列表】}public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int ListSizeA = size(headA);  // 这是列表A的长度int ListSizeB = size(headB);  // 这是列表B的长度// 下面这一步是计算差值,并且先让长的走差值步int Difference = 0;ListNode curA = headA;ListNode curB = headB;if(ListSizeA > ListSizeB){Difference = ListSizeA - ListSizeB;for(int i = 0;i < Difference;i++){curA = curA.next;  // 如果列表a长，则先让curA先走差值步}}else{Difference = ListSizeB - ListSizeA;for(int i = 0;i < Difference;i++){curB = curB.next;  // 如果列表b长，则先让curB先走差值步}}// 接下来就是一块走了while(curA != null && curB != null){if(curA==curB){return curA;}curA = curA.next;curB = curB.next;}return null;}
}

方法2：由大家补充~

---

9. 给定一个链表，判断链表中是否有环。 141. 环形链表 - 力扣（LeetCode）

新奇思路：有点类似于操场跑步绕圈，当一个人跑得慢，一个人跑得快，过了一段时间后就会相遇【即有环一定会相遇】

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode slow = head;ListNode fast = head.next;while (fast != null && fast.next != null) {if (fast == slow) {return true;  // 快慢指针相遇，说明有环}fast = fast.next.next; // fast 每次走两步slow = slow.next;}return false;}
}

---

10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL.142. 环形链表 II - 力扣（LeetCode）

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {// 当我这个列表一个元素都没有的情况下if(head == null){return null;}ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;  // 快的一下子走两步slow = slow.next; // 慢的一下子走一步if(fast == slow){break;  // 退出循环}}if(fast == null || fast.next == null){return null;  // 没有环}fast = head;while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}
}

如上述代码中，我们还是依旧是使用快慢指针来进行思路的讲解。所以在链表中，我们要善于使用快慢指针，还同时要注意null的循环条件，是本身不为空，还是下一个不为空。

---

LinkedList的模拟实现

底层实现的一些底层模拟方法代码：

package double_LinkedList;public class My_double_LinkedList {static class ListNode{public int val;public ListNode pre;  // 这个是节点的前驱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;}// 如果这个链表不为空node.next = head;head.pre = node;head = node;}//尾插法public void addLast(int data){ListNode node = new ListNode(data);if (head == null){head = node;last = node;return;  // 一定要记得结果，不然就会执行下面的代码}
//        ListNode cur = head;// 这个循环是让cur走到最后一个节点
//        while (cur.next!=null){
//            cur = cur.next;
//        }
//        cur.next = node;
//        node.pre = cur;last.next = node;node.pre = last;last = node;}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){ListNode node = new ListNode(data);if (index < 0 || index > size() ){System.out.println("您提供的下标不合法！");return;}if(head == null){if (index==0){head = node;}else {System.out.println("您提供的下标不合法！");}}else {    // 就是head不为空的情况// 头插法if (index == 0){addFirst(data);return;}// 尾插法if (index == size()){addLast(data);return;}
//            ListNode curNext = null;ListNode cur = head;for (int i = 0; i < index; i++) {cur = cur.next;  // cur一直前进到插入位置的前一个}node.next = cur;node.pre = cur.pre;cur.pre.next = node;cur.pre = node;}}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){// 要考虑空链表得情况if (head == null){return false;}// 当非空链表的时候ListNode cur = head;while (cur.next != null){if (cur.val == key){return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key) {ListNode cur = head;while (cur != null){if (cur.val == key){// 删除头节点if (cur == head){head = head.next;if (head != null){// 考虑只有一个结点的情况head.pre = null;}else {last = null;}}else {// 删除中间节点和末尾节点if (cur.next != null){// 删除中间节点cur.pre.next = cur.next;cur.next.pre = cur.pre;}else {//删除尾巴节点cur.pre.next = cur.next;last = last.pre;}}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;if (head != null) {// 考虑只有一个结点的情况head.pre = null;} else {last = null;}} else {// 删除中间节点和末尾节点if (cur.next != null) {// 删除中间节点cur.pre.next = cur.next;cur.next.pre = cur.pre;} else {//删除尾巴节点cur.pre.next = cur.next;last = last.pre;}}}cur = cur.next;}}//得到单链表的长度public int size(){int usedSize = 0;ListNode cur = head;while (cur!=null){usedSize++;cur = cur.next;}return usedSize;}// 打印列表里面所有的值public void display(){// 第一步还是要判断一下链表是否为空if (head == null){return;}ListNode cur = head;while (cur != null){System.out.print(cur.val + " ");cur = cur.next;  // 要让节点往后走}System.out.println();  // 打印一个空格使其更美观}// 清楚列表里面所有的值public void clear(){ListNode cur = head;while (cur != null){ListNode curNext = cur.next;cur.pre = null;cur.next = null;cur = curNext;}head = null;  // 手动置空last = null;}
}

测试代码：

package double_LinkedList;public class Test {public static void main(String[] args) {My_double_LinkedList myDoubleLinkedList = new My_double_LinkedList();/*** 下面是一些方法的测试*///  1.头插法 + 打印链表里面的所有元素myDoubleLinkedList.addFirst(56);myDoubleLinkedList.addFirst(45);myDoubleLinkedList.addFirst(34);myDoubleLinkedList.addFirst(23);myDoubleLinkedList.addFirst(12);myDoubleLinkedList.display();// 2.尾插法 + 打印链表里面的所有元素myDoubleLinkedList.addLast(99);myDoubleLinkedList.addLast(1314);myDoubleLinkedList.display();// 3.链表的长度int lenth = myDoubleLinkedList.size();System.out.println("目前链表得长度是：" + lenth);System.out.println("==========================");// 4.任意位置插入myDoubleLinkedList.addIndex(0, 11);myDoubleLinkedList.addIndex(6, 888);myDoubleLinkedList.addIndex(3, 666);myDoubleLinkedList.display();myDoubleLinkedList.addIndex(13, 7777);System.out.println("===========================");// 5.找是否包含关键字key是否在单链表当中boolean result1 = myDoubleLinkedList.contains(888);System.out.println(result1);boolean result2 = myDoubleLinkedList.contains(5555);System.out.println(result2);System.out.println("===========================");// 6.删除第一次出现关键字为key的节点myDoubleLinkedList.display();myDoubleLinkedList.remove(1314);   // 删除最后一个myDoubleLinkedList.display();myDoubleLinkedList.remove(11);  // 删除第一个myDoubleLinkedList.display();myDoubleLinkedList.remove(666);  // 删除中间数值myDoubleLinkedList.display();System.out.println("===========================");// 7. 删除所有值为key的节点myDoubleLinkedList.addFirst(1111);myDoubleLinkedList.addFirst(1111);myDoubleLinkedList.addFirst(1111);myDoubleLinkedList.addIndex(4, 1111);myDoubleLinkedList.addLast(1111);myDoubleLinkedList.addLast(1111);myDoubleLinkedList.display();myDoubleLinkedList.removeAllKey(1111);myDoubleLinkedList.display();System.out.println("==========================");}
}

---

LinkedList的使用

什么是LinkedList

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

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

---

LinkedList的使用

举个例子：

List<Integer> list = new LinkedList<>();

其他常用方法：

ArrayList和LinkedList的区别

一般从存储和操作两方面进行比较

补充：那顺序表和链表的区别是什么？