【链表】单链表、双向循环链表

骑猪看日落 2024-03-24 18:19 181阅读 0赞

文章目录

  • 前言
  • 一：链表(LinkedList)
    • 1.1 链表分类
    • 1.2 介绍
    • 1.3 链表的概念及结构
  • 二：单链表
    • 2.1 单链表结构示意图
    • 2.2 单链表的应用实例
    • 2.3 单链表的添加
      • 2.3.1 直接添加到链表的尾部（不考虑顺序）
        • 2.3.1.1 整体思路
        • 2.3.1.2 代码实现
      • 2.3.2 按顺序插入到指定位置(如果有这个排名，则添加失败，并给出提示)
        • 2.3.2.1 思路分析
        • 2.3.2.2 代码实现
        • 2.3.2.3 测试
    • 2.4 单链表的修改
    • 2.5 单链表的删除
      • 2.5.1 思路分析
      • 2.5.2 代码实现
      • 2.5.3 测试
  • 三：常见的单链表面试题
    • 3.1 求单链表中有效节点的个数
    • 3.2 查找单链表中的倒数第k个结点
      • 3.2.1 思路
      • 3.2.2 代码实现
    • 3.3 单链表的反转
      • 3.3.1 思路分析
      • 3.3.2 代码实现
  • 四：双向环形链表
    • 4.1 单链表的不足
    • 4.2 介绍
    • 4.3 定义双向循环链表节点类
    • 4.4 将元素追加到链表的末尾
    • 4.5 将元素插入到指定下标处
    • 4.6 返回指定下标处的元素
    • 4.7 移除指定位置处的元素
    • 4.8 返回指定位置的节点
    • 4.9 重写toString方法
    • 4.10 测试

前言

问：为什么使用链表？
答：当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此又引入了LinkedList，即链表结构。

一：链表(LinkedList)

1.1 链表分类

链表可分为三类：单链表、双向链表、循环列表
单向或者双向：
在这里插入图片描述
带头或者不带头：
在这里插入图片描述
循环或者非循环：
在这里插入图片描述

1.2 介绍

链表是有序的列表，但是它在内存中是存储如下
在这里插入图片描述
在这里插入图片描述

  1. 链表是以节点的方式来存储,是链式存储
  2. 每个节点包含 data 域， next 域：指向下一个节点.
  3. 如图：发现链表的各个节点不一定是连续存储.
  4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

1.3 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序来实现的。类似于一节又一节火车。
在这里插入图片描述

二：单链表

2.1 单链表结构示意图

在这里插入图片描述

2.2 单链表的应用实例

实例：使用带head头的单向链表实现 –人物排行榜管理
功能：完成对人物的增删改查操作

2.3 单链表的添加

2.3.1 直接添加到链表的尾部（不考虑顺序）

在这里插入图片描述

2.3.1.1 整体思路
  1. 先创建一个head头节点，作用就是表示单链表的头
  2. 后面我们没添加一个节点，就直接加入到链表的最后
  3. 通过一个辅助变量遍历，帮助遍历整个链表
2.3.1.2 代码实现
  1. public class SingleLinkedListDemo {
  3.     public static void main(String[] args) {
  5.         //创建节点
  6.         HeroNode hero1 = new HeroNode(1, "蔡徐坤", "ikun");
  7.         HeroNode hero2 = new HeroNode(2, "刀郎", "罗刹海市");
  8.         HeroNode hero3 = new HeroNode(3, "那英", "哪有鸟");
  9.         HeroNode hero4 = new HeroNode(4, "汪峰", "春天里");
  10.         HeroNode hero5 = new HeroNode(5, "杨坤", "马户");
  11.         //创建链表
  12.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  13.         singleLinkedList.add(hero1);
  14.         singleLinkedList.add(hero2);
  15.         singleLinkedList.add(hero3);
  16.         singleLinkedList.add(hero4);
  17.         singleLinkedList.add(hero5);
  18.         //显示
  19.         singleLinkedList.list();
  20.     }
  21. }
  23. /**
  24.  * 定义singleLinkedList来管理我们的人员
  25.  */
  26. class SingleLinkedList {
  28.     //先初始化头节点,头节点不要动,不存放具体数据
  29.     private final HeroNode head = new HeroNode(0, "", "");
  31.     /**
  32.      * 添加节点到单链表
  33.      * 思路：当不考虑编号顺序时，
  34.      * 1.找到当前列表的最后一个节点
  35.      * 2.将最后这个节点的next指向新的节点
  36.      *
  37.      * @param heroNode
  38.      */
  39.     public void add(HeroNode heroNode) {
  41.         //因为head节点不能动，因此我们需要设置一个辅助变量temp，并且遍历temp
  42.         HeroNode temp = head;
  43.         //遍历链表，找到最后一个节点
  44.         while (temp.next != null) {
  46.             //找到链表的最后一个节点
  47.             //如果没有找到，就将temp临时变量后移
  48.             temp = temp.next;
  49.         }
  50.         //当退出while循环时，temp就指向了链表的最后
  51.         temp.next = heroNode;
  52.     }
  54.     /**
  55.      * 显示链表
  56.      */
  57.     public void list() {
  59.         //判断链表是否为空
  60.         if (head.next == null) {
  62.             System.out.println("链表为空");
  63.             return;
  64.         }
  65.         //因为头节点不能动，因此我们需要使用一个辅助变量来遍历
  66.         HeroNode temp = head.next;
  67.         while (temp != null) {
  69.             //判断是否到链表的最后
  70.             //输出节点信息
  71.             System.out.println(temp);
  72.             //将temp后移
  73.             temp = temp.next;
  74.         }
  76.     }
  78. }
  81. /**
  82.  * 定义HeroNode，每个HeroNode对象就是一个节点
  83.  */
  84. class HeroNode {
  86.     //头节点
  87.     public int no;
  88.     public String name;
  89.     public String nickname;
  90.     //指向下一个节点
  91.     public HeroNode next;
  93.     /**
  94.      * 构造器
  95.      */
  96.     public HeroNode(int no, String name, String nickname) {
  98.         this.no = no;
  99.         this.name = name;
  100.         this.nickname = nickname;
  101.     }
  103.     /**
  104.      * 重写toString方法
  105.      *
  106.      * @return String
  107.      */
  108.     @Override
  109.     public String toString() {
  111.         return "HeroNode{" + "no=" + no + ", name='" + name + ", nickname='" + nickname + '}';
  112.     }
  115. }

在这里插入图片描述

2.3.2 按顺序插入到指定位置(如果有这个排名，则添加失败，并给出提示)

在这里插入图片描述

2.3.2.1 思路分析

需按照编号的书序添加：

  1. 首先找到新添加的节点的位置，是通过辅助变量（指针），通过遍历来搞定
  2. 新的节点.next = temp.next;
  3. 将temp.next指向新的节点
2.3.2.2 代码实现
  1. /**
  2.      * 按照顺序插入到指定位置，如果有这个排名，则添加失败，并给出提示
  3.      *
  4.      * @param heroNode
  5.      */
  6.     public void addByOrder(HeroNode heroNode) {
  8.         //因为head节点不能动，因此我们需要设置一个辅助变量temp，并且遍历temp
  9.         //因为是单链表，所以我们找的temp是位于添加位置的前一个节点，否则无法插入
  10.         HeroNode temp = head;
  11.         //添加的编号是否存在，默认为false
  12.         boolean flag = false;
  13.         //说明temp已经在链表的最后
  14.         while (true) {
  16.             if (temp.next == null) {
  18.                 break;
  19.             }
  20.             //位置找到，就在temp的后面插入
  21.             if (temp.next.no > heroNode.no) {
  23.                 break;
  24.             } else if (temp.next.no == heroNode.no) {
  26.                 //此时说明heroNode编号已经存在,将flag变为true
  27.                 flag = true;
  28.             }
  29.             //如果以上条件都不满足，则将temp后移
  30.             temp = temp.next;
  31.         }
  33.         //判断flag的值，如果flag为true则不能添加
  34.         if (flag) {
  36.             System.out.printf("编号%d,已经存在,无法添加", heroNode.no);
  37.         } else {
  39.             //插入到链表中，temp的后面
  40.             heroNode.next = temp.next;
  41.             temp.next = heroNode;
  42.         }
  43.     }
2.3.2.3 测试
  1. singleLinkedList.addByOrder(hero4);
  2.         singleLinkedList.addByOrder(hero1);
  3.         singleLinkedList.addByOrder(hero3);
  4.         singleLinkedList.addByOrder(hero2);
  5.         singleLinkedList.addByOrder(hero5);

在这里插入图片描述
此时顺序添加功能就实现了！

2.4 单链表的修改

  1. /**
  2.      * 通过no编号进行修改，no编号不可以修改
  3.      *
  4.      * @param newHeroNode
  5.      */
  6.     public void update(HeroNode newHeroNode) {
  8.         //判断链表是否为空
  9.         if (head.next == null) {
  11.             System.out.println("链表为空");
  12.             return;
  13.         }
  14.         //根据no编号找到需要修改的节点
  15.         //定义一个辅助变量
  16.         HeroNode temp = head.next;
  17.         //表示是否找到该节点
  18.         boolean flag = false;
  19.         while (true) {
  21.             if (temp == null) {
  23.                 //链表已经遍历结束
  24.                 break;
  25.             }
  26.             if (temp.no == newHeroNode.no) {
  28.                 //此时说明已经找到了
  29.                 flag = true;
  30.                 break;
  31.             }
  32.             //将temp后移
  33.             temp = temp.next;
  35.         }
  36.         //根据flag判断是否找到该节点
  37.         if(flag){
  39.             //找到了，则将temp重新赋值
  40.             temp.name = newHeroNode.name;
  41.             temp.nickname = newHeroNode.nickname;
  42.         } else {
  44.             //没找到该节点
  45.             System.out.printf("没有找到编号为%d的节点，无法修改\n", newHeroNode.no);
  47.         }
  49.     }

在这里插入图片描述

2.5 单链表的删除

2.5.1 思路分析

在这里插入图片描述
从单链表中删除一个节点的思路：

  1. 我们需要先找到删除节点的前一个节点temp
  2. temp.next = temp.next.next
  3. 被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收

2.5.2 代码实现

  1. /**
  2.      * 思路
  3.      * 1.因为头节点不能动，所以我们需要一个temp临时变量来找到删除节点的前一个节点
  4.      * 2.在比较时，我们需要将temp.next.no和需要删除节点的no进行比较
  5.      *
  6.      * @param no 需要删除节点的编号
  7.      */
  8.     public void delete(int no) {
  10.         //因为head节点不能动，因此我们需要设置一个辅助变量temp，并且遍历temp
  11.         //因为是单链表，所以我们找的temp是位于添加位置的前一个节点
  12.         HeroNode temp = head;
  13.         //表示是否找到该节点
  14.         boolean flag = false;
  15.         while (true) {
  17.             //说明temp已经在链表的最后
  18.             if (temp.next == null) {
  20.                 break;
  21.             }
  22.             //找到待删除节点的前一个节点
  23.             if (temp.next.no == no) {
  25.                 flag = true;
  26.                 break;
  27.             }
  28.             //如果以上条件都不满足，则将temp后移
  29.             temp = temp.next;
  30.         }
  32.         //判断flag的值，如果flag为true则找到
  33.         if (flag) {
  35.             //可以删除
  36.             temp.next = temp.next.next;
  37.         } else {
  39.             System.out.printf("编号%d,不存在,无法删除", no);
  40.         }
  41.     }

2.5.3 测试

删除节点信息为3的信息

  1. //删除一个节点信息
  2. singleLinkedList.delete(3);

在这里插入图片描述

三：常见的单链表面试题

3.1 求单链表中有效节点的个数

  1. /**
  2.      * 获取单链表的节点个数
  3.      * 注:如果是带头结点的，需求不统计头节点
  4.      *
  5.      * @param head
  6.      * @return
  7.      */
  8.     public static int getLength(HeroNode head) {
  10.         if (head.next == null) {
  12.             //空链表
  13.             return 0;
  14.         }
  15.         int length = 0;
  16.         //定义一个辅助变量
  17.         HeroNode temp = head.next;
  18.         //遍历
  19.         while (temp != null) {
  21.             length++;
  22.             temp = temp.next;
  23.         }
  24.         return length;
  25.     }

3.2 查找单链表中的倒数第k个结点

3.2.1 思路

  1. 1.编写一个方法，接收head节点，同时接收一个index（index表示倒数的第index个节点）
  2.  2.先把链表从头到尾遍历，得到链表的总长度size
  3.  3.得到size后，我们从链表的第一个开始遍历（size - index）个，就可以得到
  4.  4.如果找到了则返回该节点，否则返回null

3.2.2 代码实现

  1. /**
  2.      * 查找单链表中的倒数第k个结点
  3.      * 思路：
  4.      * 1.编写一个方法，接收head节点，同时接收一个index（index表示倒数的第index个节点）
  5.      * 2.先把链表从头到尾遍历，得到链表的总长度size
  6.      * 3.得到size后，我们从链表的第一个开始遍历（size - index）个，就可以得到
  7.      * 4.如果找到了则返回该节点，否则返回null
  8.      *
  9.      * @param head
  10.      * @param index
  11.      * @return
  12.      */
  13.     public static HeroNode findLastIndexNode(HeroNode head, int index) {
  15.         //如果链表为空，则返回null
  16.         if (head.next == null) {
  18.             return null;
  19.         }
  20.         //获取链表节点得个数
  21.         int size = getLength(head);
  22.         //遍历size - index，就是我们需要的倒数第k个节点
  23.         //先做index校验
  24.         if (index <= 0 || index > size) {
  26.             return null;
  27.         }
  28.         //定义辅助变量，for循环定位到倒数的index
  29.         //假设数组长度为8，我们需要找到倒数第3个数据，则就是正数第8 - 3 = 5个数据
  30.         HeroNode temp = head.next;
  31.         for (int i = 0; i < size - index; i++) {
  33.             temp = temp.next;
  34.         }
  35.         return temp;
  36.     }

3.3 单链表的反转

3.3.1 思路分析

在这里插入图片描述
在这里插入图片描述

思路：

1.先定义一个节点，reverseHead = new HeroHead();
2.从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并且放在新的链表reverseHead的最前端
3.原来的链表的head.next = reverseHead.next;

3.3.2 代码实现

  1. /**
  2.      * 单链表的反转
  3.      * 思路
  4.      * 1.先定义一个节点，reverseHead = new HeroHead();
  5.      * 2.从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并且放在新的链表reverseHead的最前端
  6.      * 3.原来的链表的head.next = reverseHead.next;
  7.      *
  8.      * @param head
  9.      */
  10.     public static void reverseList(HeroNode head) {
  12.         //如果只有一个节点或者链表是空的，则不需要反转
  13.         if (head.next == null || head.next.next == null) {
  15.             return;
  16.         }
  17.         //定义一个辅助变量，来帮助我们循环遍历链表,cur表示当前节点
  18.         HeroNode cur = head.next;
  19.         //指向当前节点cur的下一个节点
  20.         HeroNode next = null;
  21.         //定义一个空的链表
  22.         HeroNode reverseNode = new HeroNode(0, "", "");
  23.         //遍历原来的链表，每遍历一个节点，就将其取出，放到新链表reverseNode的最前端
  24.         //当cur为null时，说明已经遍历结束
  25.         while (cur != null) {
  27.             //先暂时保存当前节点的下一个节点
  28.             next = cur.next;
  29.             //将当前节点的下一个节点赋值给反转链表的最前端
  30.             cur.next = reverseNode.next;
  31.             //将cur连接到新的链表上
  32.             reverseNode.next = cur;
  33.             //将cur后移，继续向下遍历
  34.             cur = next;
  35.         }
  36.         //将head.next指向reverseNode.next,实现单链表的反转
  37.         head.next = reverseNode.next;
  38.     }

四：双向环形链表

4.1 单链表的不足

  1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
  2. 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点。

4.2 介绍

有两个指针域，一个指向后一个结点，一个指向前一个结点。它存储了前一个结点的地址与后一个结点的地址，所以可以很方便的进行向前遍历或者向后遍历。同时它还是一个循环链表，可以通过第一个结点直接找到最后一个结点。
在这里插入图片描述

next：指向下一个节点
pre：指向上一个节点

4.3 定义双向循环链表节点类

  1. public class LinkedList<E> {
  3.     /**
  4.      * head用于存放头节点信息
  5.      */
  6.     private Node head;
  7.     /**
  8.      * 链表的长度
  9.      */
  10.     private Integer size = 0;
  12.     /**
  13.      *  Node用于描述表中的一个节点
  14.      *  其中，data用于存放于元素
  15.      *  next是存放前继节点
  16.      *  prev用于存放指向其后继节点
  17.      */
  18.     class Node {
  20.         //存放数据
  21.         E data;
  22.         //前继节点
  23.         Node next;
  24.         //后继节点
  25.         Node prev;
  26.         //构造器
  27.         public Node(E e){
  29.             data = e;
  30.         }
  31.     }
  33. /**
  34.      * 获得链表的长度
  35.      *
  36.      * @return
  37.      */
  38.     public int size() {
  40.         return size;
  41.     }
  42. }

4.4 将元素追加到链表的末尾

在这里插入图片描述

  1. /**
  2.      * 将元素追加到链表的末尾
  3.      * @param e 被添加的元素
  4.      * @return 添加成功，返回true
  5.      */
  6.     public boolean add(E e){
  8.         //将元素封装成一个节点
  9.         Node node = new Node(e);
  10.         //如果链表为空，则新节点就是头节点
  11.         if(head == null){
  13.             head = node;
  14.             head.next = node;
  15.             head.prev = node;
  16.             //链表的长度加1
  17.             size ++;
  18.             return true;
  19.         }
  20.         //找到末尾节点地址
  21.         Node last = head.prev;
  22.         //将新节点添加到未节点后面
  23.         last.next = node;
  24.         node.next = head;
  25.         head.prev = node;
  26.         node.prev = last;
  27.         //链表的长度加1
  28.         size ++;
  29.         return true;
  30.     }

4.5 将元素插入到指定下标处

在这里插入图片描述

  1. /**
  2.      * 将元素插入到指定下标处
  3.      * @param index
  4.      * @param e
  5.      */
  6.     public void add(int index,E e){
  8.         if( index < 0 || index > size ){
  10.             throw new IndexOutOfBoundsException("数组下标越界异常");
  11.         }
  12.         if(index == size){
  14.            add(e);
  15.         }
  16.         //将元素封装成一个节点
  17.         Node node = new Node(e);
  18.         Node next = getNode(index);
  19.         Node prev = next.prev;
  20.         next.prev = node;
  21.         node.prev = prev;
  22.         prev.next = node;
  23.         node.next = next;
  24.         if(index == 0){
  26.             head = node;
  27.         }
  28.         size ++;
  29.     }

4.6 返回指定下标处的元素

在这里插入图片描述

  1. /**
  2.      * 返回指定下标处的元素
  3.      * @param index 下标，从0开始
  4.      * @return 对应位置处的元素
  5.      */
  6.     public E get(Integer index){
  8.         if(index < 0 || index >= size){
  10.             throw new IndexOutOfBoundsException("数组下标越界异常");
  11.         }
  12.         Node node = getNode(index);
  13.         //返回该节点存放的数据
  14.         return node.data;
  15.     }

4.7 移除指定位置处的元素

在这里插入图片描述

  1. /**
  2.      * 移除指定位置处的元素
  3.      *
  4.      * @return
  5.      */
  6.     public E remove(Integer index) {
  8.         if (index < 0 || index >= size) {
  10.             throw new IndexOutOfBoundsException("数组下标越界异常");
  11.         }
  12.         //如果链表只有一个元素,则删除该节点以后，需要将head设置为null,并返回删除的元素
  13.         if (size == 1) {
  15.             E data = head.data;
  16.             head = null;
  17.             size--;
  18.             return data;
  19.         }
  20.         //找到要删除的节点
  21.         Node node = this.getNode(index);
  22.         //找到该节点的前驱节点和后继节点
  23.         Node next = node.next;
  24.         Node prev = node.prev;
  25.         //将该节点删除(其实就是在prev和next之间建立引用关系)
  26.         prev.next = next;
  27.         next.prev = prev;
  28.         //如果被删除的元素为头节点,则其下一个节点为头节点
  29.         if (index == 0) {
  31.             head = next;
  32.         }
  33.         //链表长度减1
  34.         size--;
  35.         return node.data;
  36.     }

4.8 返回指定位置的节点

  1. /**
  2.      * 返回指定位置的节点
  3.      *
  4.      * @param index
  5.      * @return
  6.      */
  7.     private Node getNode(Integer index) {
  9.         //从头结点开始遍历
  10.         Node node = this.head;
  11.         //此时可以用移位运算
  12.         //为了提升性能，可以通过比较index与链表的长度的一半来决定是向前遍历还是向后遍历
  13.         if (index < size >> 1) {
  15.             for (int i = 0; i < index; i++) {
  17.                 node = node.next;
  18.             }
  19.         } else {
  21.             for (int i = size; i > index; i--) {
  23.                 node = node.prev;
  24.             }
  25.         }
  26.         return node;
  27.     }

4.9 重写toString方法

  1. @Override
  2.     public String toString() {
  4.         if (head == null) {
  6.             return "[]";
  7.         }
  8.         StringBuilder stringBuilder = new StringBuilder("[");
  9.         stringBuilder.append(head.data);
  10.         Node node = head.next;
  11.         while (node.next != head) {
  13.             stringBuilder.append(",").append(node.data);
  14.             //继续查找下个节点
  15.             node = node.next;
  16.         }
  17.         return stringBuilder.append("]").toString();
  18.     }

4.10 测试

  1. public class LinkedListTest {
  3.     public static void main(String[] args) {
  5.         LinkedList<String> list = new LinkedList<>();
  6.         List<Integer> arrayList = new ArrayList<>();
  7.         list.add("Curry");
  8.         list.add("Green");
  9.         list.add("Thompson");
  10.         list.add("Durant");
  11.         list.add("James");
  12.         System.out.println("size():" + list.size());
  13.         System.out.println("get(2):" + list.get(2));
  14.         System.out.println("list:" + list.toString());
  15.     }
  16. }

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，181人围观）

还没有评论，来说两句吧...

相关阅读

    相关 循环链表及双向链表

    一、循环链表 循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。

    叁歲伎倆叁歲伎倆/ 0 赞/ 157 阅读

    相关 双向链表和循环链表

    一、双向链表 每个结点有两个指针域和若干数据域，其中一个指针域指向它的前趋结点，一个指向它的后继结点。它的优点是访问、插入、删除更方便，速度也快了。但“是以空间换时间”。

    冷不防冷不防/ 0 赞/ 305 阅读

    相关 双向链表与循环链表

    双向链表 单链表的一个优点是结构简单，但是它也有一个缺点，即在单链表中只能通过一个结点的引用访问其后续结点，而无法直接访问其前驱结点， 要在单链表中找到某个结点的前驱结点

    古城微笑少年丶古城微笑少年丶/ 0 赞/ 354 阅读