【数据结构】链表重难点突破
目录
一、链表的概念
二、链表的实现
2.1 链表的构建
2.2 从链表头部添加元素
2.3 从链表尾部添加元素
2.4 链表任意位置添加元素
2.5 常规方法实现
2.6 获取指定位置的元素
2.7 获取指定元素的位置
2.8 修改链表中某一节点
2.9 删除链表的头结点
2.10 删除链表的尾节点
2.11 删除任意位置节点
三、力扣刷题
LCR 136. 删除链表的节点
链表进阶
（备注：本篇文章的代码是基于Java实现）
一、链表的概念
（该部分主要对链表进行简单的介绍，通过简洁易懂的语言带大家快速认识链表！）
链表和数组是数据结构中最为常用的两种存储结构，链表是如同链条一般的指针来连接元素，链表的特点是插入和删除数据十分方便，但查找和读取数据 与数组相比 则较为低效。
链表与数组之间的差异：
| 内容 | 链表 | 数组 |
| 存储连续性 | 逻辑连续，物理不连续 | 逻辑、物理都连续 |
| 添加数据 | O(1) | O(N) |
| 删除数据 | O(1) | O(N) |
| 查询数据 | O(N) | O(1) |
| 修改数据 | O(N) | O(1) |
我们可以发现，一条链表是由许多个节点构成，节点中存储数据，并存储下一个节点的引用(指针)
二、链表的实现
（该部分将通过Java语言模拟链表的底层实现）
2.1 链表的构建
2.1.1 首先创建节点对象
public class ListNode {
public int val; //当前节点的值
public ListNode next; //下一个节点的引用
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}2.1.2 创建链表的异常处理对象（在链表的操作过程中我们要考虑对异常进行处理）
public class LinkedListException extends RuntimeException{
public LinkedListException(String message){
super(message);
}
}2.1.3 创建接口，定义链表要实现的方法
2.1.4 构建链表，并实现接口
public class MyLinkedList {
private ListNode head; //头指针
private ListNode tail; //尾指针
private int size; //链表容量
}2.2 从链表头部添加元素
接口：
//头部添加
void addFirst(int val);实现类：（addFirst）
@Override
public void addFirst(int val) {
//创建一个新节点
ListNode newNode = new ListNode(val);
//如果链表为空,则头指针和尾指针都指向新节点
if (head == null) {
head = newNode;
tail = newNode;
} else {
//链表不为空,则新节点指向原来链表的头节点,并更新头指针指向新节点
newNode.next = head;
head = newNode;
}
//每次添加一个新节点,原链表长度加1
size++;
}测试：
为了方便打印输出结果，大家也可以和上图一样，重写toString方法：
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
ListNode curr = head;
while (curr != null) {
sb.append(curr.val).append(",");
curr = curr.next;
}
if (size > 0) sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}2.3 从链表尾部添加元素
接口：
//尾部添加
void addLast(int val);实现类：（addLast）
@Override
public void addLast(int val) {
ListNode newNode = new ListNode(val);
//链表为空,则头指针指向新节点
if (head == null) {
head = newNode;
} else {
//链表不为空,需要从头节点一直找到最后一个指向空的节点,再将新节点连接到表尾
ListNode curr = head;
while (curr.next!=null) curr= curr.next;
curr.next = newNode;
}
size++;
}测试：
2.4 链表任意位置添加元素
接口：
/**
* 任意位置添加
* @param index 插入的位置
* @param val 插入的元素
*/
void add(int index, int val);实现类：（add）
@Override
public void add(int index, int val) {
//入参判断
if (index < 0 || index > size) throw new LinkedListException("链表索引越界异常");
//创建新节点
ListNode newNode = new ListNode(val);
//头部添加
if (index == 0) {
addFirst(val);
return;
}
//尾部添加
if (index == size) {
addLast(val);
return;
}
//找到要插入位置的前一个节点
ListNode curr = head;
for (int i = 0; i < index - 1; i++) {
curr = curr.next;
}
newNode.next = curr.next;
curr.next = newNode;
size++;
}测试：
2.5 常规方法实现
判断链表是否为空isEmpty、获取链表长度size、获取链表头节点getFirst、获取链表尾节点getLast
接口：(这几个方法的实现都较为简单，这里我一起进行演示)
//判断链表是否为空
boolean isEmpty();
//获取链表长度
int size();
//获取头节点的值
int getFirst();
//获取尾节点的值
int getLast();实现类：
//判断链表是否为空
@Override
public boolean isEmpty() {
return size == 0;
}
//获取链表长度
@Override
public int size() {
return size;
}
//获取头节点的值
@Override
public int getFirst() {
//这里链表为空要进行异常处理
if (isEmpty()) throw new LinkedListException("链表为空");
return head.val;
}
//获取尾节点的值
@Override
public int getLast() {
if (isEmpty()) throw new LinkedListException("链表为空");
ListNode curr = head;
while (curr.next != null) curr = curr.next;//O(N)
return curr.val;
}测试：
2.6 获取指定位置的元素
接口：
//获取任意位置节点的值
int get(int index);实现类：
@Override
public int get(int index) {
//判断索引是否合法
if (index < 0 || index >= size) throw new LinkedListException("索引越界异");
//直接返回头节点
if (index == 0) {
return getFirst();
}
//直接返回为节点
if (index == size - 1) {
return getLast();
}
//遍历
ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.val;
}测试：
2.7 获取指定元素的位置
接口：
/**
* 通过值找索引
* @param val 要查找的元素
* @return 返回该元素的位置
*/
int indexOf(int val);实现类：
@Override
public int indexOf(int val) {
//若链表为空直接返回-1
if (isEmpty()) return -1;
ListNode curr = head;
int index = 0;
while (curr != null) {
//如果找到 直接返回索引
if (curr.val == val) {
return index;
}
curr = curr.next;
index++;
}
//未找到 返回-1
return -1;
}测试：
2.8 修改链表中某一节点
接口：
/**
* 修改元素
* @param index 旧元素的位置
* @param val 新元素的值
*/
void set(int index, int val);实现类：
@Override
public void set(int index, int val) {
//链表为空 无法修改
if (isEmpty()) throw new LinkedListException("链表为空");
//判断索引是否合法
if (index < 0 || index >= size) throw new LinkedListException("索引越界");
ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
curr.val = val;
}测试：
2.9 删除链表的头结点
接口：
//删除头节点
void removeFirst();实现类：
@Override
public void removeFirst() {
//链表为空要进行异常处理
if (isEmpty()) throw new LinkedListException("链表为空");
ListNode next = head.next;
head.next = null;
head = next;
size--;
}测试：
2.10 删除链表的尾节点
接口：
//删除尾节点
void removeLast();
实现类：
@Override
public void removeLast() {
if (isEmpty()) throw new LinkedListException("链表为空异常，删除失败");
if (size==1){
head=null;
size--;
return;
}
ListNode pre = head;
for (int i = 0; i < size -2; i++) {
pre = pre.next;
}
ListNode target = pre.next;
ListNode next = target.next;
pre.next = next;
target.next = null;
size--;
}测试：
2.11 删除任意位置节点
接口：
//删除任意位置节点
void remove(int index);实现类：
@Override
public void remove(int index) {
if (isEmpty()) throw new LinkedListException("链表为空");
if (index < 0 || index >= size) throw new LinkedListException("索引越界");
if (index == 0) {
removeFirst();
return;
}
ListNode pre = head;
for (int i = 0; i < index - 1; i++) {
pre = pre.next;
}
ListNode target = pre.next;
ListNode next = target.next;
pre.next = next;
target.next = null;
size--;
}测试：
三、力扣刷题
LCR 136. 删除链表的节点
大家可以尝试下这道题目：
LCR 136. 删除链表的节点 - 力扣（LeetCode）
链表进阶
【快慢指针】突破环形链表-CSDN博客
关于代码的优化或大家有更好的思路 欢迎在评论区分享你的观点！
🌸🌸🌸 完结撒花 🌸🌸🌸
博主WX：g2279605572 欢迎大家与我交流！