[数据结构] 链表

一.链表

1.链表概念

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

注意:

• 从上图中可以看出 , 链表结构在逻辑上是连续的 , 但是在物理上是不连续的
• 现实中的结点一般都是从 堆上申请出来的
• 从堆上申请的空间 , 是按照一定的策略来分配的 , 两次申请的 空间可能连续 , 也可能不连续

2.链表分类(8种)

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

• 单向或双向
• 带头结点或者不带头结点
• 循环或非循环

头结点可以存放数据 , 但是无任何意义

3.链表的实现

• 无头单项非循环链表的实现
• 头插法 , 尾插法 , 任意位置插入 , 查找 , 删除 , 长度 , 清空 , 打印等功能 

①接口的实现

public interface IList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();public void clear();public void display();
}

②功能的实现

//无头单项非循环链表的实现
public class MyLinkedList implements IList {static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//求链表的长度@Overridepublic int size() {if(head == null) {return 0;}else {int len = 0;ListNode cur = head;while (cur.next != null){cur = cur.next;len++;}return len;}}//头插法@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);if(head == null){head =  node;}else {node.next = head;head = node;}}//尾插法@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null){head =  node;}else{ListNode cur = head;while(cur.next!=null){cur = cur.next;}cur.next = node;}}//在下标 index 位置 , 插入 data@Overridepublic void addIndex(int index, int data) {ListNode node = new ListNode(data);int len = size();if(index<0||index>len){throw new IndexOutOfBoundsException("下标越界");}if(index == 0){addFirst(data);}if(index == len){addLast(data);}ListNode cur = head;for (int i = 0; i < index; i++) {cur = cur.next;}node.next = cur.next;cur.next = node;}//查找是否包含关键字key是否在单链表当中@Overridepublic boolean contains(int key) {int len = size();if(len == 0) {return false;}ListNode cur = head;while (cur.next!=null)if(cur.val == key) {return true;}cur = cur.next;return false;}//删除第一次出现关键字为key的节点@Overridepublic 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的节点@Overridepublic void removeAllKey(int key) {if(head == null){return;}ListNode prev = head;ListNode cur = head.next;while (cur != null){if(cur.val == key){prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if(head.val == key ){head = head.next;}}//清空链表@Overridepublic void clear() {ListNode cur = head;while (cur!=null){ListNode curN = cur.next;cur = null;cur = curN;}head =null;}//打印链表@Overridepublic void display() {ListNode cur = head;while (cur!=null){System.out.println(cur.val+" ");cur = cur.next;}}
}

4.链表与数组的对比

• 内存分配：链表动态分配内存，数组需连续内存。
• 访问效率：数组随机访问O(1)，链表需遍历O(n)。
• 插入/删除：链表在已知位置操作更高效（O(1)或O(n)），数组需移动元素（O(n)）。

5.总结

• Java 中链表分为自定义链表和内置LinkedList，LinkedList是双向循环链表，功能强大；
• 链表的核心是节点和引用，增删灵活但查询效率低，适合频繁增删的场景；
• 需掌握链表的基本操作（增、删、反转）和经典算法问题，理解指针（引用）的移动逻辑。

例1:

• 给你单链表的头结点 head ，请你找出并返回链表的中间结点。
• 如果有两个中间结点，则返回第二个中间结点。

class Solution {public ListNode middleNode(ListNode head) {ListNode cur1 = head;//快指针ListNode cur2 = head;//慢指针while(cur1!=null&&cur1.next!=null){//cur1 = cur1.next.next;cur2 = cur2.next;}return cur2;}
}

例2:

• 链表的逆置

   //链表的逆置
public ListNode reverseList() {if(head == null||head.next == null) {return head;}ListNode cur = head.next;head.next = null;while(cur != null) {ListNode curN = cur.next;cur.next = head;head = cur;cur = curN;}return head;
}

例3:

•     获取倒数第 k 个结点的数据

    //获取倒数第 k 个结点的数据public int kthToLast( int k) {if(head == null) return -1;if(k <= 0) {return -1;}ListNode fast = head;ListNode slow = head;int count = 0;while(count != k-1) {fast = fast.next;if(fast == null) {return -1;}count++;}while(fast.next != null) {fast = fast.next;slow = slow.next;}return slow.val;}

完