一、链表基本概念和基本代码实现
🍃 动态数组有个明显的缺点：可能会造成内存空间的大量浪费
🍃 能否用到多少就申请多少内存：链表可以办到
🍃 链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
🍀 链表（LinkedList）中有 size 属性【记录着链表中元素的个数、节点的个数】
🍀 链表中的 first 被称作头指针【它引用着链表中的第一个节点（头节点）】
🍀 链表中的元素是存储在Node 节点中的，一个Node 节点可被简单看作是一个元素
🍀 Node 也是一个类
🍀 Node 节点中的
element属性是该 Node 节点 存储的数据🍀 Node 节点中的
next属性引用着下一个节点（next存储着下一个节点的内存地址）🍀 尾节点的
next属性不存储任何内容（① 引用着 null；② 指向 null）
public class LinkedList<E> { private int size; // 头指针 private Node<E> first; /** * 每一个节点就是 Node 类的一个实例 */ private static class Node<E> { E element; Node<E> next; public Node(E element, Node<E> next) { this.element = element; this.next = next; } } }
二、链表、动态数组整合（面向接口编程）
🧡 ArrayList、LinkedList 继承（extends）抽象类 AbstractList
🧡 抽象类 AbstractList 抽取 ArrayList 和 LinkedList 的公共代码，并实现（implements）了 List 接口
🧡 List 接口定义了 LinkedList 和 ArrayList 要实现的全部代码
三、clear()
🧡 没有被引用的对象会被 Java 的垃圾回收器自动回收
public void clear() { size = 0; first = null; }
四、add(int index, E element)
🌼 要往 index 位置插入元素
🌼 找到
index - 1位置的节点（记作：prev）🌼 让新节点（记作：newNode）的 next 指向
prev.next（是新节点的下一个节点）🌼 让 prev 的 next 指针指向新节点（记作：newNode）
🌼 size++
(1) 找到 index 位置的节点
☃️ 要找 0 号位置的节点【first 头指针指向的就是 0 号位置的节点】
☃️ 要找 1 号位置的节点【first 头指针的 next 指向的就是 1 号位置的节点】
☃️ 要找 2 号位置的节点【first 头指针的 next 的 next 指向的就是 2 号位置的节点】
☃️ 要找0号位置的节点是0次 next，要找1号位置的节点是1次 next，要找2号位置的节点是2次 next，要找 index 位置的节点是 index 次 next
/** * 返回 index 位置的节点 */ private Node<E> node(int index) { rangeCheck(index); // 从头节点开始（默认指向头节点） Node<E> moveNode = first; for (int i = 0; i < index; i++) { moveNode = moveNode.next; } return moveNode; }
(2) get(int index) 和 set(int index, E element)
🌴 因为
node()方法返回了 index 位置的节点，所以get(int index)方法（返回 index 位置的元素 ） 方法也得以实现🌴 因为
node()方法返回了 index 位置的节点，所以set(int index, E element)方法（设置 index 位置的元素为 element ） 方法也得以实现
@Override public E get(int index) { Node<E> node = node(index); return node.element; }
@Override public E set(int index, E element) { Node<E> node = node(index); E old = node.element; node.element = element; return old; }
(3) add(int index, E element)
🍀 编写链表代码过程中，要注意边界测试
🍀 比如 index 为 0、size – 1、size 时
@Override public void add(int index, E element) { rangeCheck4Add(index); if (index == 0) { // 把元素插入到头节点的位置 first = new Node<>(element, first); } else { // 拿到【index - 1】位置的节点 Node<E> prev = node(index - 1); prev.next = new Node<>(element, prev.next); } size++; }
五、remove(int index)
@Override public E remove(int index) { rangeCheck(index); Node<E> node = first; if (index == 0) { // 删除头节点 first = node.next; } else { Node<E> prev = node(index - 1); node = prev.next; prev.next = node.next; } size--; return node.element; }
🌴 注意 index 等于 0 的时候
六、indexOf(E element)
🌴 遍历整个链表，取值比较
@Override public int indexOf(E element) { Node<E> moveNode = first; if (element == null) { for (int i = 0; i < size; i++) { if (null == moveNode.element) return i; moveNode = moveNode.next; } } else { for (int i = 0; i < size; i++) { if (element.equals(moveNode.element)) return i; moveNode = moveNode.next; } } return ELEMENT_NOT_FOUND; }
七、三个 Leetcode 的练习题
(1) 删除链表中的节点
题目地址：https://leetcode.cn/problems/delete-node-in-a-linked-list/
🌼有一个单链表的 head，我们想删除它其中的一个节点 node
🌼 给你一个需要删除的节点 node
🌼 你无法访问第一个节点 head
🌼 链表的所有值都是唯一的
🌼 给定的节点 node 不是链表中的最后一个节点
🌼 删除节点并不是指从内存中删除它
而是：
① 给定节点的值不应该存在于链表中
② 链表中的节点数应该减少 1
③
node前面的所有值顺序相同④
node后面的所有值顺序相同
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; } }
🍃 用要被删除的节点（delNode）的下一个节点的值（delNode.next.val）覆盖 delNode 的值
🍃 delNode 的 next 指向 delNode 的 next 的 next
(2) 反转一个链表
https://leetcode-cn.com/problems/reverse-linked-list/
① 递归反转一个链表
/** * 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 reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; } }
② 迭代反转一个链表
/** * 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 reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = null; while (head != null) { ListNode tmp = head.next; head.next = newHead; newHead = head; head = tmp; } return newHead; } }
(3) 判断一个链表是否有环（快慢指针）
https://leetcode.cn/problems/linked-list-cycle/
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) return false; ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) return false; slow = slow.next; fast = fast.next.next; } return true; } }
完整代码：https://gitee.com/zgq666good/datastructureandalgorithm.git
如有错误请不吝赐教
