devbox
2023面试高手
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构之链表

作者：2023面试高手 | 2024-05-04 09:37:04

赞

踩

数据结构之链表

目录

​编辑前言

一.链表

1.1链表的概念

1.2链表的8种结构

1.3单链表的实现

1.单链表的接口

1.4单链表的功能实现

1.定义链表节点

2.链表的头插

3.链表的尾插

4.在指定位置插入数据

5.获取单链表长度&清空单链表&单链表的打印

6.查找关键字key是否在单链表中出现

2.链表和顺序表的优缺点

3.完整代码

前言

在上一篇中我们介绍了顺序表。在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后 搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java 集合中又引入了LinkedList，即链表结构

一.链表

1.1链表的概念

链表是一种在物理存储结构上非连续学校结构，数据元素的逻辑结构是通过链表中的引用链接次序实现的。

注意：

1.链式结构在逻辑上是连续的，但是在物理上不一定连续。

2.节点（结点）一般都是从堆上申请出来的。

3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间有可能连续，但也有可能不连续。

1.2链表的8种结构

根据带头/不带头、单向/双向、循环/非循环来划分，链表有8种结构。

  1. 带头单向循环链表
  2. 不带头单向循环链表
  3. 带头双向循环链表
  4. 不带头双向循环链表
  5. 带头单向非循环链表
  6. 不带头单向非循环链表
  7. 带头双向非循环链表
  8. 不带头双向非循环链表

1.3单链表的实现

我们今天实现的是不带头单向非循环链表

1.单链表的接口

ILinkList.java

  1. package MLinkList;
  2.  
  3. public interface ILinkList {
  4.     // 1、无头单向非循环链表实现
  5.         //头插法
  6.         public void addFirst(int data);
  7.  
  8.         //尾插法
  9.         public void addLast(int data);
  10.  
  11.         //任意位置插入,第一个数据节点为0号下标
  12.         public void addIndex(int index, int data);
  13.  
  14.         //查找是否包含关键字key是否在单链表当中
  15.         public boolean contains(int key);
  16.  
  17.         //删除第一次出现关键字为key的节点
  18.         public void remove(int key);
  19.         //删除所有值为key的节点
  20.         public void removeAllKey(int key);
  21.  
  22.         //得到单链表的长度
  23.         public int size();
  24.         
  25.         //清空链表
  26.         public void clear();
  27.         //打印单链表
  28.         public void display();
  29. }

1.4单链表的功能实现

1.定义链表节点

我们需要先创建一个内部类，作为链表的节点。并创建个头指针、尾指针。

  1. /**
  2.      * ListNode 类定义了一个链表节点。
  3.      * 这个类包含一个整型数据和一个指向下一个节点的指针。
  4.      */
  5.     public class ListNode{
  6.         // 节点存储的数据
  7.         public int data;
  8.         // 指向下一个节点的指针
  9.         public ListNode next;
  10.         
  11.         /**
  12.          * ListNode 类的构造函数，用于创建一个新的链表节点。
  13.          * 
  14.          * @param data 节点存储的数据。
  15.          */
  16.         public ListNode(int data)
  17.         {
  18.             this.data = data; // 初始化节点数据
  19.         }
  20.     }
  21.  public ListNode head;//头指针
  22.     public ListNode last;//尾指针
2.链表的头插

进行头插，需要考虑两种情况：

  1. 头指针为空，让新节点作为头指针
  2. 头指针不为空，可以进行头插，头插的时候，先让新节点的指针指向头结点，再让头指针移动到新节点位置。
  1.    public void addFirst(int data) {
  2.         ListNode node = new ListNode(data); // 创建新节点，数据为传入的data
  3.         // 判断链表是否为空，如果为空，说明当前没有节点，直接将新节点作为头节点
  4.         if (head == null) {
  5.             head = node;
  6.             return;
  7.         }
  8.         // 链表不为空时，进行头插操作，新节点的next指向当前头节点，然后更新头节点为新节点
  9.         node.next = head;
  10.         head = node;
  11.     }
3.链表的尾插

进行尾插时，同样需要考虑头结点是否为空

  1.  /**
  2.      * 使用尾插法向链表中添加元素。
  3.      * 该方法会将指定的元素添加到链表的末尾。
  4.      * 
  5.      * @param data 要添加到链表的数据。
  6.      */
  7.     public void addLast(int data) {
  8.         ListNode node = new ListNode(data); // 创建新节点，数据为data
  9.         
  10.         if (head == null) {
  11.             head = last = node; // 如果链表为空，将新节点同时设置为头节点和尾节点
  12.             return;
  13.         }
  14.         last.next = node; // 将当前尾节点的next指向新节点
  15.         last = last.next; // 更新尾节点为新添加的节点
  16.         
  17.     }
4.在指定位置插入数据

我们需要考虑3种情况：

  1. 要插入的位置是否合法
  2. index位置是在链表两端还是在链表内部，如果index==0，那么则直接调用头插法即可，如果index=size（），那么直接调用尾插法即可。
  3. 在链表内部，我们就需要找到index的前一个节点，再进行插入。（这里查找index的前一个节点，我们可以定义一个方法进行查找）
  1.  private void checkIndex(int index)throws IndexNoLegalException {
  2.         if (index < 0 || index > size()) {
  3.         throw new IndexNoLegalException("index位置不合法"+"index="+index);
  4.         }
  5.     }
  6.  
  7.     private ListNode findIndex(int index) {
  8.         ListNode cur = head;
  9.         while (index-- != 1) {
  10.             cur = cur.next;
  11.         }
  12.         return cur;
  13.     }
  14.     //任意位置插入,第一个数据节点为0号下标
  15.     public void addIndex(int index, int data) {
  16.         //判断index位置是合法
  17.         try {
  18.             checkIndex(index);
  19.         } catch (IndexNotLegalException e) {
  20.             e.printStackTrace();
  21.         }
  22.         if(index==0) {//头插
  23.             addFirst(data);
  24.         } 
  25.         if(index==size()) {//尾插
  26.             addLast(data);
  27.         }
  28.         //创建新节点，并查找index位置的前一个节点
  29.         ListNode node = new ListNode(data);
  30.         ListNode findlist=findIndex(index);
  31.         node.next=findlist.next;
  32.         findlist.next=node;
  33.     }
5.获取单链表长度&清空单链表&单链表的打印

这里主要是单链表的清空，我们也可以直接让head=last=null，但是更好的是把单链表中的节点都清空。

  1.  
  2.     /**
  3.      * 获取单链表的长度。
  4.      * @return 链表中节点的数目。
  5.      */
  6.     public int size() {
  7.         int count = 0; // 初始化计数器
  8.         ListNode cur = head; // 从头节点开始遍历
  9.         while (cur != null) {
  10.             count++;
  11.             cur = cur.next; // 移动到下一个节点
  12.         }
  13.         return count; // 返回计数结果
  14.     }
  15.     
  16.     /**
  17.      * 清空单链表，使其变为空链表。
  18.      */
  19.     public void clear() {
  20.         if (head == null) {
  21.             return; // 如果链表为空，则直接返回
  22.         }
  23.         ListNode cur = head; // 保存头节点的下一个节点，以避免丢失整个链表
  24.         while (cur != null) {
  25.             ListNode curN=cur.next;
  26.             cur=null;
  27.             cur=curN;
  28.         }
  29.         head = last = null; // 最后将头节点和尾节点都设置为null
  30.     }
  31.     
  32.     /**
  33.      * 打印单链表中的所有节点数据。
  34.      */
  35.     public void display() {
  36.         if (head == null) {
  37.             return; // 如果链表为空，则直接返回
  38.         }
  39.         ListNode cur = head; // 从头节点开始遍历
  40.         while (cur != null) {
  41.             System.out.print(cur.data + " "); // 打印当前节点的数据
  42.             cur = cur.next; // 移动到下一个节点
  43.         }
  44.         System.out.println(); // 换行
  45.     }
6.查找关键字key是否在单链表中出现

我们直接遍历单链表一遍即可，找到返回true

  1. /**
  2.      * 检查单链表中是否包含指定关键字。
  3.      * @param key 需要在单链表中查找的关键字。
  4.      * @return 如果链表中包含关键字，则返回true；否则返回false。
  5.      */
  6.     public boolean contains(int key){
  7.         // 如果链表头节点为空，直接返回false，表示链表为空，不可能包含关键字
  8.         if(head==null){
  9.             return false;
  10.         }
  11.         // 遍历链表，查找是否存在与key相等的节点
  12.         while(head!=null){
  13.             if(head.data==key){
  14.                 // 找到相等的节点，返回true
  15.                 return true;
  16.             }
  17.             head=head.next; // 移动到下一个节点继续查找
  18.         }
  19.         // 遍历完整个链表都没有找到相等的节点，返回false
  20.         return false;
  21.     }

7.移除第一次出现key关键字的节点&移除所有key关键字的节点

移除出现一次关键字的节点：

  1. 判断链表是否为空
  2. 我们可以查找当前节点的下一个节点的值是否与key相同，如果相同，那就让当前节点的指针指向下一个节点的指针

移除所有出现关键字的节点

  1. 我们需要用到两个指针，一个用来跟踪prev，一个（cur）用来查找与key相同的节点，如果找到，那就让prev.next指向cur.next，删除key节点。
  2. 当走完循环时，我们还需要判断头结点是否与key相同，如果相同，那就需要让head指向下一个节点。
  1.  /**
  2.      * 删除链表中第一次出现的关键字为key的节点
  3.      * @param key 需要删除的节点的值
  4.      * 如果链表为空或者没有找到值为key的节点，则链表结构不变
  5.      */
  6.     public void remove(int key){
  7.         // 链表为空，直接返回
  8.         if(head==null){
  9.             return;
  10.         }
  11.         ListNode cur=head;
  12.         // 遍历链表，查找第一个值为key的节点
  13.         while(cur!=null) {
  14.             // 找到后，删除该节点
  15.             if(cur.next.data==key){
  16.                 cur.next=cur.next.next;
  17.                 return;
  18.             }
  19.             cur=cur.next;
  20.         }
  21.     }
  22.     /**
  23.      * 删除链表中所有值为key的节点
  24.      * @param key 需要删除的节点的值
  25.      * 该方法不返回任何内容
  26.      */
  27.     public void removeAllKey(int key){
  28.         // 如果链表为空，则直接返回
  29.         if(head==null){
  30.             return;
  31.         }
  32.         ListNode prev=head;// 记录当前节点的前一个节点
  33.         ListNode cur=head.next;// 记录当前操作的节点
  34.         while(cur!=null){
  35.             if(cur.data==key){
  36.                 prev.next=cur.next; // 如果当前节点的值等于key，则删除该节点
  37.             }else{
  38.                 prev=cur; // 否则，继续向前遍历
  39.             }
  40.             cur=cur.next;
  41.         }
  42.         // 如果头节点的值等于key，则更新头节点
  43.         if(head.data==key){
  44.             head=head.next;
  45.         }
  46.     }

这些是单链表的一些基本方法，我们测试一下，确实是我们所想的。

2.链表和顺序表的优缺点

链表：

优点：

1.插入和删除操作简单：由于链表的节点通过指针链接，插入和删除操作只需要修改指针的指向，不需要移动其他元素，因此时间复杂度为O(1)。

2.链表可以根据实际情况动态分配内存空间，只需要在插入新节点时分配新的内存，因此避免了固定大小的存储空间的限制。

缺点：

1.随机访问性能差，链表开辟的空间在内存中上随机开辟的，不一定连续，所以在访问的时候需要遍历查找。时间复杂度为O(N).

2.需要额外的存储空间，由于节点与节点之间是通过指针相连的，所以有额外的空间来存储下一个节点的位置。

顺序表：

优点：

1.支持随机访问：由于顺序表在内存中是连续的，可以通过下标直接访问顺序表中的元素。时间复杂度是O(1).

2.存储效率高，不需要开辟额外的空间存储指针。

缺点：

1.在插入和删除数据的时候，需要搬动其他元素，时间复杂度为O(N)。

2.存储空间固定：如果要扩容的话，可能会造成空间浪费。

3.完整代码

接口在上

单链表功能实现：MyLinkltstto.java

  1. package MLinkList;
  2.  
  3. import SlowList.IndexNoLegalException;
  4.  
  5. public class MyLinklistto implements ILinkList{
  6.     // 1、无头单向非循环链表实现
  7.     /**
  8.      * ListNode 类定义了一个链表节点。
  9.      * 这个类包含一个整型数据和一个指向下一个节点的指针。
  10.      */
  11.     public class ListNode{
  12.         // 节点存储的数据
  13.         public int data;
  14.         // 指向下一个节点的指针
  15.         public ListNode next;
  16.  
  17.         /**
  18.          * ListNode 类的构造函数，用于创建一个新的链表节点。
  19.          *
  20.          * @param data 节点存储的数据。
  21.          */
  22.         public ListNode(int data)
  23.         {
  24.             this.data = data; // 初始化节点数据
  25.         }
  26.     }
  27.     public ListNode head;//头指针
  28.     public ListNode last;//尾指针
  29.  
  30.     /**
  31.      * 在链表的头部进行插入操作。
  32.      * 该方法会将新节点插入到链表的头部，如果链表为空，则新节点成为头节点；
  33.      * 如果链表不为空，则新节点将成为新的头节点，原头节点成为新节点的下一个节点。
  34.      *
  35.      * @param data 要插入节点的数据。
  36.      */
  37.     public void addFirst(int data) {
  38.         ListNode node = new ListNode(data); // 创建新节点，数据为传入的data
  39.         // 判断链表是否为空，如果为空，说明当前没有节点，直接将新节点作为头节点
  40.         if (head == null) {
  41.             head =last= node;
  42.             return;
  43.         }
  44.         // 链表不为空时，进行头插操作，新节点的next指向当前头节点，然后更新头节点为新节点
  45.         node.next = head;
  46.         head = node;
  47.     }
  48.     /**
  49.      * 使用尾插法向链表中添加元素。
  50.      * 该方法会将指定的元素添加到链表的末尾。
  51.      *
  52.      * @param data 要添加到链表的数据。
  53.      */
  54.     public void addLast(int data) {
  55.         ListNode node = new ListNode(data); // 创建新节点，数据为data
  56.  
  57.         if (head == null) {
  58.             head = last = node; // 如果链表为空，将新节点同时设置为头节点和尾节点
  59.             return;
  60.         }
  61.         last.next = node; // 将当前尾节点的next指向新节点
  62.         last = last.next; // 更新尾节点为新添加的节点
  63.  
  64.     }
  65.  
  66.     /**
  67.      * 检查索引是否合法。
  68.      * @param index 要检查的索引值。
  69.      * @throws IndexNoLegalException 如果索引不合法，则抛出异常。
  70.      */
  71.     private void checkIndex(int index)throws IndexNoLegalException {
  72.         if (index < 0 || index > size()) { // 索引超出范围不合法
  73.             throw new IndexNoLegalException("index位置不合法"+"index="+index);
  74.         }
  75.     }
  76.  
  77.     /**
  78.      * 查找指定索引位置的节点。
  79.      * @param index 目标索引位置。
  80.      * @return 返回指定索引位置的节点。
  81.      */
  82.     private ListNode findIndex(int index) {
  83.         ListNode cur = head; // 从头节点开始遍历
  84.         while (index-- != 1) { // 递减索引，找到目标位置的前一个节点
  85.             cur = cur.next;
  86.         }
  87.         return cur;
  88.     }
  89.  
  90.     /**
  91.      * 在任意位置插入一个节点。
  92.      * @param index 插入位置的索引。
  93.      * @param data 要插入的数据。
  94.      */
  95.     public void addIndex(int index, int data) {
  96.         // 判断插入位置是否合法
  97.         try {
  98.             checkIndex(index);
  99.         } catch (IndexNotLegalException e) {
  100.             e.printStackTrace();
  101.         }
  102.         if(index==0) { // 如果是插入到头部
  103.             addFirst(data);
  104.         }
  105.         if(index==size()) { // 如果是插入到尾部
  106.             addLast(data);
  107.         }
  108.         // 创建新节点，并插入到指定位置
  109.         ListNode node = new ListNode(data);
  110.         ListNode findlist=findIndex(index); // 找到插入位置的前一个节点
  111.         node.next=findlist.next; // 新节点接在前一个节点之后
  112.         findlist.next=node; // 前一个节点指向新节点
  113.     }
  114.  
  115.  
  116.     /**
  117.      * 检查单链表中是否包含指定关键字。
  118.      * @param key 需要在单链表中查找的关键字。
  119.      * @return 如果链表中包含关键字，则返回true；否则返回false。
  120.      */
  121.     public boolean contains(int key){
  122.         // 如果链表头节点为空，直接返回false，表示链表为空，不可能包含关键字
  123.         if(head==null){
  124.             return false;
  125.         }
  126.         // 遍历链表，查找是否存在与key相等的节点
  127.         while(head!=null){
  128.             if(head.data==key){
  129.                 // 找到相等的节点，返回true
  130.                 return true;
  131.             }
  132.             head=head.next; // 移动到下一个节点继续查找
  133.         }
  134.         // 遍历完整个链表都没有找到相等的节点，返回false
  135.         return false;
  136.     }
  137.  
  138.     /**
  139.      * 删除链表中第一次出现的关键字为key的节点
  140.      * @param key 需要删除的节点的值
  141.      * 如果链表为空或者没有找到值为key的节点，则链表结构不变
  142.      */
  143.     public void remove(int key){
  144.         // 链表为空，直接返回
  145.         if(head==null){
  146.             return;
  147.         }
  148.         ListNode cur=head;
  149.         // 遍历链表，查找第一个值为key的节点
  150.         while(cur!=null) {
  151.             // 找到后，删除该节点
  152.             if(cur.next.data==key){
  153.                 cur.next=cur.next.next;
  154.                 return;
  155.             }
  156.             cur=cur.next;
  157.         }
  158.     }
  159.     /**
  160.      * 删除链表中所有值为key的节点
  161.      * @param key 需要删除的节点的值
  162.      * 该方法不返回任何内容
  163.      */
  164.     public void removeAllKey(int key){
  165.         // 如果链表为空，则直接返回
  166.         if(head==null){
  167.             return;
  168.         }
  169.         ListNode prev=head;// 记录当前节点的前一个节点
  170.         ListNode cur=head.next;// 记录当前操作的节点
  171.         while(cur!=null){
  172.             if(cur.data==key){
  173.                 prev.next=cur.next; // 如果当前节点的值等于key，则删除该节点
  174.             }else{
  175.                 prev=cur; // 否则，继续向前遍历
  176.             }
  177.             cur=cur.next;
  178.         }
  179.         // 如果头节点的值等于key，则更新头节点
  180.         if(head.data==key){
  181.             head=head.next;
  182.         }
  183.     }
  184.  
  185.     /**
  186.      * 获取单链表的长度。
  187.      * @return 链表中节点的数目。
  188.      */
  189.     public int size() {
  190.         int count = 0; // 初始化计数器
  191.         ListNode cur = head; // 从头节点开始遍历
  192.         while (cur != null) {
  193.             count++;
  194.             cur = cur.next; // 移动到下一个节点
  195.         }
  196.         return count; // 返回计数结果
  197.     }
  198.  
  199.     /**
  200.      * 清空单链表，使其变为空链表。
  201.      */
  202.     public void clear() {
  203.         if (head == null) {
  204.             return; // 如果链表为空，则直接返回
  205.         }
  206.         ListNode cur = head; // 保存头节点的下一个节点，以避免丢失整个链表
  207.         while (cur != null) {
  208.             ListNode curN=cur.next;
  209.             cur=null;
  210.             cur=curN;
  211.         }
  212.         head = last = null; // 最后将头节点和尾节点都设置为null
  213.     }
  214.  
  215.     /**
  216.      * 打印单链表中的所有节点数据。
  217.      */
  218.     public void display() {
  219.         if (head == null) {
  220.             return; // 如果链表为空，则直接返回
  221.         }
  222.         ListNode cur = head; // 从头节点开始遍历
  223.         while (cur != null) {
  224.             System.out.print(cur.data + " "); // 打印当前节点的数据
  225.             cur = cur.next; // 移动到下一个节点
  226.         }
  227.         System.out.println(); // 换行
  228.     }
  229. }
  230.  
  231.

 测试：test2.java

  1. package MLinkList;
  2.  
  3. public class test2 {
  4.     public static void main(String[] args) {
  5.         MyLinklistto list = new MyLinklistto();
  6.         list.addFirst(2);
  7.         list.addFirst(3);
  8.         list.addFirst(4);
  9.         list.addFirst(4);
  10.         list.addFirst(4);
  11.         list.addLast(5);
  12.         list.addIndex(2, 6);
  13.         list.display();
  14.         System.out.println("=========");
  15.         list.removeAllKey(4);
  16.         list.display();
  17.     }
  18. }

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/533834
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号