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;
}
// 处理删除中间或尾部的 key
ListNode 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;
}
// 处理删除中间或尾部的 key
ListNode 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 here
ListNode 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 here
ListNode 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的区别
一般从存储和操作两方面进行比较
补充：那顺序表和链表的区别是什么？
