数据结构系列之链表的数据结构

àì夳堔傛蜴生んèń 2021-09-09 06:06 298阅读 0赞

## 数据结构系列之链表的数据结构 ##

在[上一章][Link 1]的学习中，我们知道了数组的基本概念和相关特性，接着本博客继续学习数据结构中一个比较常用的数据结构，链表。ps：本博客基于java中的数据结构。

### 1、什么是链表？ ###

链表是由一系列节点组成的很常见的数据结构，每一个节点都包含一个值和指向下一个节点的指针。“头”节点指向序列的第一个节点，序列的最后一个节点指向NULL（对于单链表）。链表也是线性的顺序存储数据，不过在内存地址上是不连续的。

画图表示单链表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0MjczOTE_size_16_color_FFFFFF_t_70]

### 2、链表和数组的对比 ###

在上一章节，学习了数组，所以这一章和数组做对比：

*  数组在内存地址是连续的，与数组不同，链接的节点（链接）不需要连续出现在内存中
 *  链表的大小不需要提前声明，只有内存允许就可以
 *  链表是动态的，所以新增移除节点都是控制指针就可以，所以链表的新增移除操作都是比较快的，这个和数组相反
 *  数组是通过下标指针就可以直接访问节点数据，而链表需要全局遍历，所以数组的访问速度是比较快，链接相反
 *  链表的数据结构需要更多的内存，因为链表不止要保存数据，还要保存下一个节点的指针

### 3、链表的类型分类 ###

数据结构中支持如下几种类型的链表：

*  单链表：在单链表中，节点的遍历只能往前遍历，指针从Head节点开始
 *  双向链表：双向链表的遍历导航可以和单链表一样往前遍历，也可以后腿，往后遍历
 *  循环链表：循环链表是一种特别的链表，其最后一个节点的`next`指针指向第一个节点，也即第一个节点的`previous`节点为最后一个节点

### 4、单链表的简介 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0MjczOTE_size_16_color_FFFFFF_t_70]  
由图看出链表的特性：

*  1、 Head节点指向第1个节点
 *  2、 最后一个节点指针指向null
 *  3、 每一个节点都存储数据和指向下一个节点的指针

### 5、双向链表简介 ###

画图表示双向链表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0MjczOTE_size_16_color_FFFFFF_t_70 1]  
由图可以归纳双向链表的特性：

*  1、Head节点指向链表的第一个节点
 *  2、每一个节点都有一个存储数据的节点，和指向下一个节点的`next`指针、指向上一个节点的`prev`指针
 *  3、第一个节点的`prev`指针指向null
 *  4、最好一个节点的`next`指针指向null

### 6、循环单向链表 ###

画图表示循环单向链表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0MjczOTE_size_16_color_FFFFFF_t_70 2]

由图归纳循环单向链表的特性：

*  1、 Head节点指向第1个节点
 *  2、Tail (Last) 指针指向列表的最后一个节点。
 *  3、每个节点都有存储数据的区域和一个指向下一个节点的指针
 *  4、最后一个节点的`next`指针指向第一个节点

### 7、链表的基本操作 ###

本章节以最简单的单链表，介绍链表的基本操作，开发语言基于Java

需要构建一个链表的节点模型，单链表只需要保存数据，加上一个next指针就行：

private static class Node<T> { 
 public T data;
 public Node next;
 Node(T data) { 
 this.data = data;
 next = null;
 }
 }

*  新增节点  
    这种情况，直接将新增节点附加到链表的后面，这里分情况：
    
     *  1、如果是empty的链表，直接将新节点作为head节点
     *  2、其它节点，直接附加到链表最后面既可

/** * 链表新增节点，直接附加到链表最后面 * @Date 2021/08/04 13:54 * @Param [list, data] * @return void */
 public static <T> void add(MySinglyLinkedList<T> list , T data) { 
 Node<T> newNode = new Node<T>(data);
 
 // 单链表是empty的，将新增的节点直接作为head节点
 if (list.head == null) { 
 list.head = newNode;
 }
 else { // 其它情况直接在链表后面附加上新节点
 Node<T> currentNode = list.head;
 while (currentNode.next != null) { 
 currentNode = currentNode.next;
 }
 // 将新增的节点作为最后一个节点
 currentNode.next = newNode;
 }
 }

如上的方法，都是固定在链表最后面加上的，然后可以实现在指定节点后面加上节点，这里分三步进行：

*  1、创建新的节点，赋值数据
 *  2、将新节点的指针指向前驱节点原来的next节点
 *  3、将前驱节点的指针指向新建的节点

/** * 在指定前驱节点后面附加新节点 * @Date 2021/08/04 14:26 * @Param prevNode 前驱节点 * @Param data 新增节点数据 * @return void */
 public static <T> void addAfter(Node<T> prevNode , T data) { 
 if (prevNode == null) { 
 System.out.println("前驱节点不能为null");
 }
 // 原本链表0->2，创建新节点1
 Node<T> newNode = new Node<T>(data);
 // 将新节点的指针指向前驱节点原本的next节点 1->2
 newNode.next = prevNode.next;
 // 将前驱节点的next指针指向新节点 0->1
 prevNode.next = newNode;
 }

*  移除节点  
    移除节点，可以在指定位置移除节点，这里可以分为几种情况：
    
     *  1、移除第一个节点。
     *  2、移除任何中间元素。
     *  3、移除最后一个元素。

/** * 指定下标移除链表节点 * @Date 2021/08/04 14:34 * @Param [list, pos] * @return void */
 public static <T> void removeAtPosition(MySinglyLinkedList<T> list , int pos) { 
 // 当前节点
 Node<T> currentNode = list.head;
 // 记录前一个节点
 Node<T> prevNode = null;
 // 下标计数器
 int counter = 0;
 if (currentNode != null) { 
 // 移除第一个节点
 if (pos == 0) { 
 // 指针移动，节点往后移，再将下一个节点置为head节点
 list.head = currentNode.next;
 }
 else { 
 while (currentNode!= null) { 
 // 找到移除节点要节点位置
 if (counter == pos) { 
 prevNode.next = currentNode.next;
 break;
 }
 else { 
 // 记录前驱节点
 prevNode = currentNode;
 // 往后遍历
 currentNode = currentNode.next;
 // 记录指针位置
 counter++;
 }
 }
 
 }
 }
 
 }

/** * 通过数据找到节点，移除节点 * @Date 2021/08/04 15:12 * @return void */
 public static <T> void removeByValue(MySinglyLinkedList<T> list , T data) { 
 Node<T> currentNode = list.head;
 Node<T> prevNode = null;
 if (currentNode != null) { 
 // 第一个节点
 if (currentNode.data == data) { 
 // 节点移动，改变head节点
 list.head = currentNode.next;
 }
 else { 
 while (currentNode != null && currentNode.data != data) { 
 prevNode = currentNode;
 currentNode = currentNode.next;
 }
 // 找到了节点
 if (currentNode != null) { 
 // 节点移动
 prevNode.next = currentNode.next;
 System.out.println(String.format("移除节点：%s" , data));
 }
 else { // 找不到对应节点
 System.out.println("遍历不到对应data的节点");
 }
 }
 }
 }

*  链表size  
    这个逻辑就比较容易理解了，直接遍历，统计就行

/** * 统计单遍历节点数量 * @Date 2021/08/04 16:25 * @Param [list] * @return int */
 public static <T> int size(MySinglyLinkedList<T> list) { 
 int counter = 0;
 Node<T> currentNode = list.head;
 while (currentNode.next != null) { 
 currentNode = currentNode.next;
 counter ++;
 }
 return counter;
 }

*  链表查询  
    变量查找的，可以通过递归，也可以用while循环

/** * 查询单链表 * @Date 2021/08/04 16:24 * @Param [head, data] * @return boolean */
 public static <T> boolean search(Node<T> head, T data) { 
 if (head == null) { 
 return false;
 }
 if (head.data == data) { 
 return true;
 }
 // 递归查找
 return search(head.next , data);
 }

### 8、Java实现链表实例 ###

/** * 单链表java代码实现 * @date 2021/08/04 */
 public class MySinglyLinkedList<T> { 
 
 public Node<T> head;
 
 private static class Node<T> { 
 public T data;
 public Node next;
 Node(T data) { 
 this.data = data;
 next = null;
 }
 }
 
 /** * 链表新增节点，直接附加到链表最后面 * @Date 2021/08/04 13:54 * @Param [list, data] * @return void */
 public static <T> void add(MySinglyLinkedList<T> list , T data) { 
 Node<T> newNode = new Node<T>(data);
 
 // 单链表是empty的，将新增的节点直接作为head节点
 if (list.head == null) { 
 list.head = newNode;
 }
 else { // 其它情况直接在链接后面附加上新节点
 Node<T> currentNode = list.head;
 while (currentNode.next != null) { 
 currentNode = currentNode.next;
 }
 // 将新增的节点作为最后一个节点
 currentNode.next = newNode;
 }
 }
 
 /** * 在指定前驱节点后面附加新节点 * @Date 2021/08/04 14:26 * @Param prevNode 前驱节点 * @Param data 新增节点数据 * @return void */
 public static <T> void addAfter(Node<T> prevNode , T data) { 
 if (prevNode == null) { 
 System.out.println("前驱节点不能为null");
 }
 // 原本链表0->2，创建新节点1
 Node<T> newNode = new Node<T>(data);
 // 将新节点的指针指向前驱节点原本的next节点 1->2
 newNode.next = prevNode.next;
 // 将前驱节点的next指针指向新节点 0->1
 prevNode.next = newNode;
 }
 
 /** * 指定下标移除链表节点 * @Date 2021/08/04 14:34 * @Param [list, pos] * @return void */
 public static <T> void removeAtPosition(MySinglyLinkedList<T> list , int pos) { 
 // 当前节点
 Node<T> currentNode = list.head;
 // 记录前一个节点
 Node<T> prevNode = null;
 // 下标计数器
 int counter = 0;
 if (currentNode != null) { 
 // 移除第一个节点
 if (pos == 0) { 
 // 指针移动，节点往后移，再将下一个节点置为head节点
 list.head = currentNode.next;
 }
 else { 
 while (currentNode!= null) { 
 // 找到移除节点要节点位置
 if (counter == pos) { 
 prevNode.next = currentNode.next;
 break;
 }
 else { 
 // 记录前驱节点
 prevNode = currentNode;
 // 往后遍历
 currentNode = currentNode.next;
 // 记录指针位置
 counter++;
 }
 }
 
 }
 }
 
 }
 
 /** * 通过数据找到节点，移除节点 * @Date 2021/08/04 15:12 * @return void */
 public static <T> void removeByValue(MySinglyLinkedList<T> list , T data) { 
 Node<T> currentNode = list.head;
 Node<T> prevNode = null;
 if (currentNode != null) { 
 // 第一个节点
 if (currentNode.data == data) { 
 // 节点移动，改变head节点
 list.head = currentNode.next;
 }
 else { 
 while (currentNode != null && currentNode.data != data) { 
 prevNode = currentNode;
 currentNode = currentNode.next;
 }
 // 找到了节点
 if (currentNode != null) { 
 // 节点移动
 prevNode.next = currentNode.next;
 System.out.println(String.format("移除节点：%s" , data));
 }
 else { // 找不到对应节点
 System.out.println("遍历不到对应data的节点");
 }
 }
 }
 }
 
 /** * 打印单链表数据 * @Date 2021/08/04 16:24 * @Param [list] * @return void */
 public static <T> void printLinkedList(MySinglyLinkedList<T> list) { 
 Node<T> currentNode = list.head;
 while (currentNode != null) { 
 if (currentNode.next != null) { 
 System.out.print(String.format("%s -> ", currentNode.data));
 }
 else { 
 System.out.print(String.format("%s", currentNode.data));
 }
 currentNode = currentNode.next;
 }
 System.out.println();
 }
 
 /** * 查询单链表 * @Date 2021/08/04 16:24 * @Param [head, data] * @return boolean */
 public static <T> boolean search(Node<T> head, T data) { 
 if (head == null) { 
 return false;
 }
 if (head.data == data) { 
 return true;
 }
 // 递归查找
 return search(head.next , data);
 }
 
 /** * 统计单遍历节点数量 * @Date 2021/08/04 16:25 * @Param [list] * @return int */
 public static <T> int size(MySinglyLinkedList<T> list) { 
 int counter = 0;
 Node<T> currentNode = list.head;
 while (currentNode.next != null) { 
 currentNode = currentNode.next;
 counter ++;
 }
 return counter;
 }
 
 public static MySinglyLinkedList<Integer> buildLinedList() { 
 MySinglyLinkedList<Integer> list = new MySinglyLinkedList<Integer>();
 MySinglyLinkedList.add(list , 0);
 MySinglyLinkedList.add(list , 1);
 MySinglyLinkedList.add(list , 2);
 MySinglyLinkedList.add(list , 3);
 MySinglyLinkedList.add(list , 4);
 MySinglyLinkedList.add(list , 5);
 MySinglyLinkedList.add(list , 6);
 MySinglyLinkedList.add(list , 7);
 MySinglyLinkedList.add(list , 8);
 MySinglyLinkedList.add(list , 9);
 MySinglyLinkedList.add(list , 10);
 return list;
 }
 
 
 public static void main(String[] args) { 
 MySinglyLinkedList<Integer> list = buildLinedList();
 
 System.out.println(String.format("linked list size : %s" , size(list)));
 // 打印验证，0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
 printLinkedList(list);
 
 // 在head节点的下一个节点后面加上新节点
 addAfter(list.head.next , 11);
 // 打印验证，0 -> 1 -> 11 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
 printLinkedList(list);
 
 // 重置链表
 list = buildLinedList();
 // 在对应位置移除链表节点
 removeAtPosition(list , 1);
 // 打印验证，0 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
 printLinkedList(list);
 
 // 重置链表
 list = buildLinedList();
 // 根据数据移除链表节点
 removeByValue(list , 10);
 // 打印验证 ，0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
 printLinkedList(list);
 
 // 重置链表
 list = buildLinedList();
 Node headNode = list.head;
 if (search(headNode , 5)) { 
 System.out.println("查找到对应的节点");
 }
 else { 
 System.out.println("不能查找到对应节点");
 }
 
 }
 
 }

### 9、参考文档资料 ###

[https://www.javadevjournal.com/data-structure/linked-list/][https_www.javadevjournal.com_data-structure_linked-list]

[Link 1]: https://smilenicky.blog.csdn.net/article/details/119252880
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0MjczOTE_size_16_color_FFFFFF_t_70]: /images/20210813/b4b29b9a020f4f89aae183dbe43068a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0MjczOTE_size_16_color_FFFFFF_t_70 1]: /images/20210813/e9718bb62c2b4cc7a97627c817a59a37.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0MjczOTE_size_16_color_FFFFFF_t_70 2]: /images/20210813/b6cd5f7b6fdb49c090666744112e291b.png
[https_www.javadevjournal.com_data-structure_linked-list]: https://www.javadevjournal.com/data-structure/linked-list/