【数据结构】链表重难点突破

目录

一、链表的概念

二、链表的实现

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）

    @Overridepublic void addFirst(int val) {//创建一个新节点ListNode newNode = new ListNode(val);//如果链表为空,则头指针和尾指针都指向新节点if (head == null) {head = newNode;tail = newNode;} else {//链表不为空,则新节点指向原来链表的头节点,并更新头指针指向新节点newNode.next = head;head = newNode;}//每次添加一个新节点,原链表长度加1size++;}

测试：

为了方便打印输出结果，大家也可以和上图一样，重写toString方法：

    @Overridepublic 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）

    @Overridepublic 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）

    @Overridepublic 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();

实现类：

    //判断链表是否为空@Overridepublic boolean isEmpty() {return size == 0;}//获取链表长度@Overridepublic int size() {return size;}//获取头节点的值@Overridepublic int getFirst() {//这里链表为空要进行异常处理if (isEmpty()) throw new LinkedListException("链表为空");return head.val;}//获取尾节点的值@Overridepublic 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);

实现类：

    @Overridepublic 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);

实现类：

    @Overridepublic int indexOf(int val) {//若链表为空直接返回-1if (isEmpty()) return -1;ListNode curr = head;int index = 0;while (curr != null) {//如果找到 直接返回索引if (curr.val == val) {return index;}curr = curr.next;index++;}//未找到 返回-1return -1;}

测试：

2.8 修改链表中某一节点

接口：

    /*** 修改元素* @param index 旧元素的位置* @param val 新元素的值*/void set(int index, int val);

实现类：

    @Overridepublic 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();

实现类：

    @Overridepublic void removeFirst() {//链表为空要进行异常处理if (isEmpty()) throw new LinkedListException("链表为空");ListNode next = head.next;head.next = null;head = next;size--;}

测试：

2.10 删除链表的尾节点

接口：

    //删除尾节点void removeLast();

实现类：

    @Overridepublic 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);

实现类：

    @Overridepublic 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   欢迎大家与我交流！