【数据结构】链表重难点突破
目录
（备注：本篇文章的代码是基于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. 删除链表的节点
大家可以尝试下这道题目：
链表进阶
关于代码的优化或大家有更好的思路 欢迎在评论区分享你的观点！
🌸🌸🌸 完结撒花 🌸🌸🌸
博主WX：g2279605572 欢迎大家与我交流！
原文地址：https://blog.csdn.net/2301_79263365/article/details/143994628
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！