链表结构

说到链表结构就不得不提起数据结构，什么是数据结构？就是用来组织和存储数据的某种结构。那么到底是某种结构呢？

数据结构分为：

• 线性结构
  • 数组，链表，栈，队列
• 树形结构
  • 二叉树，B树，红黑树等
• 图形结构
  • 邻接矩阵，邻接表等

那么链表就是我们这本文的主角，之前其实我们都接触过链表就是集合中基于List实现的linkedlist，但是在练习的过程中我发现好多同志只会用，不知道其中原理，知其然而不知其所以然。但是也会有同志说了我会用不就不就醒了，各位凡是要做到精益求精，知其然跟要知其所以然。为实现科技报国我们的祖国就需要这种人才，一起创新创建共创科技大国。

链表结构的定义

什么是链表

在逻辑结构上一个挨一个的数据，但是在实际存储时所在的内存地址却并不连续，相反数据随机分布在内存中的各个位置。

通过数据的指针指向下一个数据，这种存储结构称为链式存储，而这种链式存储所生成的表就是链表

链表分类

• 单向链表
• 双向链表
• 双向循环链表

单向链表

什么是单向链表

上面说到了什么是链表，那么在单向链表中我们将数据分为两个区域

• 数据域：存储数据
• 指针域：存储下一个节点的内存地址
  

在链表中它有一个专业名字叫做：节点。

一个节点指向下一个节点，这种链式结构称为单向链表

在单向链表中，链表的第一个节点称为首元节点

链表的最后一个节点称为尾节点

中间的这个节点的前一个节点称为前驱

中间的这个节点的后一个节点称为后继

通常在链表的前面会有一个节点称为头节点，当然头节点不是必须存在的。

• 头节点的作用是：用来存储链表的长度

在每一个链表中都会配备一个头指针，指针始终指向第一个节点，如果有链表中配备头节点则指向头节点，如果没有配备头节点则指向首元节点

头指针的定义是：用于在链表中挪动指针查找数据，直到找到对应的数据

单向链表的功能

• 增

  • 向链表的尾节点添加节点

    • 将新添加节点的内存地址存放到该链表尾节点的指针域中。通俗的讲：将尾节点的指针域指向新添加的节点

    • 此时尾节点就是新添加的这个节点

      

  • 向链表的首元节点之前添加节点

    • 将链表的首元节点的内存地址存放到新添加节点的指针域中。通俗的讲：新节点的指针指向首元节点

    • 此时首元节点是新添加的这个节点

      

  • 向链表中间添加节点

    • 将新添加节点的内存地址存放到前驱的指针域中，新添加节点的指针域存放后继的内存地址。通俗的讲：修改前驱的指针方向指向新添加的节点，新添加的节点执行后继即可

    

• 删

  • 删除尾节点

    • 尾节点的前驱的指针域不在存储尾节点的内存地址。通俗的讲：尾节点的指针域不在指向尾节点

  • 删除首元节点

    • 首元节点的指针域不存放后继的内存地址。通俗的讲：首元节点的指针与不在指向后继节点

  • 删除中间的某个节点

    • 删除节点的前驱指针域不再存放删除节点的内存地址，删除节点的指针域不再存储后继的内存地址，通俗的讲：删除节点的前驱指向删除节点的后继

      

    注意：被删除的节点称之为：野节点，这并不是真正意义上的删除，它在内存中依旧存在。那么野节点的最终归宿是被JVM的GC（垃圾回收器）所回收，也就是释放该节点的内存空间，这才是真正意义上的删除

    额外知识：java中的垃圾回收器（Garbage Collector，GC）负责管理内存的分配和释放。当一个对象没有任何引用指向它时，它就变得不可达，而垃圾回收器会将其标记为垃圾对象，并在适当的时候回收该对象所占用的内存空间。这个过程称为垃圾回收。

• 改

  • 挪动指针找到要修改的节点，之后讲修改节点的数据域中的数据修改掉

• 查

  • 挪动指针找到要所要查找的数据。

特点

• 节点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。

• 数据元素的个数可以自由扩充，插入，删除，只需要修改节点的指针方向，效率高

• 修改和查找节点数据需要挪动指针，按照节点的顺序进行依次查找或者修改，效率比较低

与数组的区别

回顾数组

数组的功能

• 增

  • 数据不能超过定义的数组长度
  • 数据少于定义数组的长度会造成内存浪费
  • 数组中间添加数据会将之后的数据内存位置往后挪动

  

• 删

• 改

• 查

区别

实现单项链表

MyList

/*** @CreateName SIN* @CreateDate 2023/07/27 16:28* @description 定义链表功能规范，避免子类编码随意性。同时也实现了程序的解耦，提高代码的可维护性。*/
//泛型E任何数据类型
public interface MyList<E> {//添加节点数据void add(E element);//获取节点数据(根据具体的指针找到对应的数据）E get(int index);//获取链表的长度int size();//根据指针移除节点E remove(int index);//修改节点数据E set(int index,E element);
}

MyLinkedList

package com.sin.linkedList;/*** @CreateName SIN* @CreateDate 2023/07/27 16:35* @description*/
public class MyLinkedList<E> implements MyList<E>{// 存放链表的头节点private Node head;// 记录链表的长度private int size;/*** 向链表中添加节点* @param element 添加的节点*/@Overridepublic void add(E element) {//创建一个新的节点，存储传入的元素Node<E> node = new Node<E>(element,null);//获取链表尾节点Node tail = getTail();//如果链表为空，if (tail == null){//将新节点设置为头节点this.head = node;}else{//否则，在尾节点后面添加新节点tail.next = node;}//记录元素的个数this.size++;}/*** 获取尾节点* @return 返回尾节点*/private Node getTail(){//判断当前头节点是否为空if(this.head == null){return null;}//遍历链表//从头节点开始遍历链表Node node = this.head;while (true){//如果下一个节点为空，则表示当前节点为尾节点，则跳出循环if(node.next == null){break;}//在循环的过程中，移动指针，指向下一个节点node = node.next;}//返回尾节点return node;}/*** 根据指针获取节点数据* @param index* @return 返回节点数据*/@Overridepublic E get(int index) {//1,校验index的合法性pointerIndex(index);//2,根据具体位置获取对应的节点数据Node<E> node = getNode(index);//3,将节点中的元素返回return node.item;}/*** 校验所给定的指针是否在链表的有效范围内* @param index*/private void pointerIndex(int index){// 大于等于0并且小于链表长度if (!(index >= 0 && index < this.size)){//获取最大的索引指int a = this.size-1;// 抛出索引越界异常，显示错误信息throw new IndexOutOfBoundsException("你输入的指针为："+index + "最大指针为："+a);}}/*** 根据指针获取节点* @return 返回给定索引处的节点*/private Node getNode(int index){//从头节点开始遍历链表Node<E> node = this.head;//移动指针，指向下一个节点，直到所给定的索引位置for (int i = 0;i< index;i++){node = node.next;}//返回给定索引处的节点return node;}@Overridepublic int size() {return this.size;}@Overridepublic E remove(int index) {//校验index的合法性this.pointerIndex(index);//根据index指针找到该节点对象数据Node<E> node = this.getNode(index);//获取该节点对象中的元素E item = node.item;//向该节点对象中单向链表删除//判断当前删除的节点是否为头节点if (this.head == node){this.head = node.next;//如果是删除头节点，头节点的下一个节点，赋值给了头节点}else {Node<E> node1 = this.head;//拿头节点for (int i = 0 ; i<index - 1 ; i++){node1=node1.next;}node1.next = node.next;//将节点的下一个节点赋值给该节点}node.next = null;this.size -- ;//删除成功长度减一return item;//返回元素}/*** 修改节点数据* @param index 挪动指针* @return 返回修好的值*/@Overridepublic E set(int index,E element) {//校验index的合法性pointerIndex(index);//获取index处的节点Node<E> node = getNode(index);//将节点值数据进行赋值替换return node.item = element;}/*** 使用内部类定义单向链表中的节点对象**/class Node<E>{//数据域private E item;//存储的数据//指针域private Node next;//存储下一个节点对象的地址//无参构造方法public Node(){}//全参构造方法public Node(E item,Node next){this.item = item;this.next = next;}}
}

测试

public static void main(String[] args) {MyLinkedList myLinkedList = new MyLinkedList();myLinkedList.add(12);myLinkedList.add(13);myLinkedList.add(14);myLinkedList.add(15);myLinkedList.add(16);System.out.println("根据指针找到值"+myLinkedList.get(4));System.out.println("删除的节点"+myLinkedList.remove(0));System.out.println(myLinkedList);System.out.println(myLinkedList.size());System.out.println(myLinkedList.set(3,"张三");for (int i=0;i<myLinkedList.size(); i++){System.out.print(myLinkedList.get(i)+",");}}