• 数据结构之LinkedList与链表（上）

    找往期文章包括但不限于本期文章中不懂的知识点：

    个人主页：我要学编程(ಥ_ಥ)-CSDN博客

    所属专栏：数据结构（Java版）

    目录

    手动实现单链表的源码

    手动实现双链表的源码

    分析 LinkedList 的源码 

    LinkedList的使用 

    常用方法 

    ArrayList和LinkedList的区别

    单链表的学习，点我

    上面这篇博文是关于链表的基础知识、链表的分类以及单链表的实现。都详细的进行了说明。

    手动实现单链表的源码

    下面是Java版的链表源码： 

    1. // 无头单向非循环链表实现
    2. public class SingleLinkedList {
    3.     // 链表是有一个一个的节点组成，因此得先创建节点
    4.     // 链表的节点由两部分组成：数值域与地址域
    5.     // 既然有多个部分，那么就可以写在类中
    6.     // 又因为节点是在单链表中（单链表中包含一个又一个的节点）
    7.     // 因此节点就可以成为单链表的内部类
    8.  
    9.     // 静态内部类可以只通过类名来访问，方便
    10.     public static class listNode {
    11.         public int val; // 存放数值
    12.         // 是一个引用指向下一个节点的地址
    13.         public listNode next; // 指向下一个节点的地址
    14.  
    15.         public listNode(int val) {
    16.             // 新创建的节点的next应该为null，因为next为字段。因此其默认值为null，无需修改
    17.             this.val = val;
    18.         }
    19.     }
    20.  
    21.     public listNode head; // 头节点
    22.  
    23.     // 头插法
    24.     public void addFirst(int data){
    25.         listNode newNode = new listNode(data);
    26.         // 先判断这个链表是否有节点
    27.         if (head == null) {
    28.             //那么新增的这个节点就是头节点
    29.             head = newNode;
    30.         }else {
    31.             // 把新节点的next指向head，并且把head指向新节点
    32.             newNode.next = head;
    33.             head = newNode;
    34.         }
    35.     }
    36.  
    37.     // 尾插法
    38.     public void addLast(int data){
    39.         listNode newNode = new listNode(data);
    40.         // 先判断这个链表是否为空
    41.         if (head == null) {
    42.             head = newNode;
    43.         }else {
    44.             listNode cur = head;
    45.             // 找到尾节点
    46.             while (cur.next != null) {
    47.                 cur = cur.next;
    48.             }
    49.             // 将尾节点的next指向新节点，就完成了尾插
    50.             cur.next = newNode;
    51.         }
    52.     }
    53.  
    54.     // 任意位置插入,第一个数据节点为0号下标
    55.     public boolean addIndex(int index,int data) throws AddIndexofException{
    56.         // 先判断插入的位置是否合法
    57.         if (index < 0 || index > size()) {
    58.             throw new AddIndexofException("addIndex() index位置异常");
    59.         }
    60.         // 先判断这个链表是否为空，如果是空，既可以采取尾插，也可以采取头插
    61.         if (head == null) {
    62.             addLast(data);
    63.         }else if (index == 0) {
    64.             addFirst(data);
    65.         }else {
    66.             listNode newNode = new listNode(data);
    67.             // 找到pos-1的位置
    68.             listNode cur = head;
    69.             while (index-1 > 0) {
    70.                 cur = cur.next;
    71.                 index--;
    72.             }
    73.             // 两个的顺序不能变
    74.             newNode.next = cur.next;
    75.             cur.next = newNode;
    76.             return true;
    77.         }
    78.         return false;
    79.     }
    80.  
    81.     // 查找是否包含关键字key是否在单链表当中
    82.     public boolean contains(int key){
    83.         // 先判断链表是否为空
    84.         if (head == null) {
    85.             return false;
    86.         }
    87.         listNode cur = head;
    88.         while (cur != null) {
    89.             if (cur.val == key) {
    90.                 return true;
    91.             }
    92.             cur = cur.next;
    93.         }
    94.         return false;
    95.     }
    96.  
    97.     // 删除第一次出现关键字为key的节点
    98.     public void remove(int key) throws SingleLinkedisEmptyException, NotFindException{
    99.         // 判断链表是否为空
    100.         if (head == null) {
    101.             throw new SingleLinkedisEmptyException("单链表为空异常");
    102.         } else if (head.next == null) {
    103.             // 如果链表中只有一个元素的话，直接删除就行
    104.             if (head.val == key) {
    105.                 head = null;
    106.                 return;
    107.             }
    108.             else {
    109.                 throw new NotFindException("找不到要删除的数异常");
    110.             }        
    111.         } else if (head.val == key) {
    112.             // 头删
    113.             head = head.next;
    114.             return;
    115.         } else {
    116.             listNode cur = head;
    117.             while (cur.next != null) {
    118.                 if (cur.next.val == key) {
    119.                     // 开始删除
    120.                     listNode del = cur.next.next;
    121.                     cur.next = cur.next.next;
    122.                     // 可能这里会有疑惑被删除的节点的next不是还指向了其后一个位置吗？
    123.                     // 这样会不会有问题呢？当一个对象每人引用时，就会被标记回收
    124.                     // 当然手动置为null，也是可以的
    125.                     del = null;
    126.                     return;
    127.                 }
    128.                 cur = cur.next;
    129.             }
    130.         }
    131.         throw new NotFindException("找不到要删除的数异常");
    132.     }
    133.  
    134.     // 删除所有值为key的节点
    135.     public void removeAllKey(int key){
    136.         boolean flag = true;
    137.         // 判断链表是否为空
    138.         if (head == null) {
    139.             throw new SingleLinkedisEmptyException("单链表为空异常");
    140.         } else if (head.next == null) {
    141.             // 如果链表中只有一个元素的话，直接删除就行
    142.             if (head.val == key) {
    143.                 head = null;
    144.                 return;
    145.             }else {
    146.                 throw new NotFindException("没有找到要删除的数据！");
    147.             }
    148.         } else if (head.val == key) {
    149.             // 如果头节点的值key，那就循环删除直至头节点的不为key
    150.             while (head.val == key) {
    151.                 // 如果删除的只剩下最后一个节点了，就删除返回就行
    152.                 if (head.next == null) {
    153.                     head = head.next;
    154.                     return;
    155.                 }
    156.             }
    157.             flag = false;
    158.         } else {
    159.             listNode cur = head;
    160.             while (cur.next != null) {
    161.                 if (cur.next.val == key) {
    162.                     // 开始删除
    163.                     listNode del = cur.next.next;
    164.                     cur.next = cur.next.next;
    165.                     // 可能这里会有疑惑被删除的节点的next不是还指向了其后一个位置吗？
    166.                     // 这样会不会有问题呢？当一个对象每人引用时，就会被标记回收
    167.                     // 当然手动置为null，也是可以的
    168.                     del = null;
    169.                     flag = false;
    170.                 }else {
    171.                     // 可能会出现连续的数字的情况
    172.                     // 因此删除之后，还得判断这个cur之后的元素是否为key
    173.                     cur = cur.next;
    174.                 }
    175.             }
    176.         }
    177.         if (flag) {
    178.             throw new NotFindException("找不到要删除的数异常");
    179.         }
    180.     }
    181.  
    182.     // 得到单链表的长度
    183.     public int size(){
    184.         // 先判断这个链表是否为空
    185.         if (head == null) {
    186.             return 0;
    187.         }
    188.         listNode cur = head;
    189.         int count = 0;
    190.         while (cur != null) {
    191.             count++;
    192.             cur = cur.next;
    193.         }
    194.         return count;
    195.     }
    196.  
    197.     // 打印链表
    198.     public void display(){
    199.         listNode cur = head;
    200.         while (cur != null) {
    201.             System.out.print(cur.val+" ");
    202.             cur = cur.next;
    203.         }
    204.         System.out.println();
    205.     }
    206.  
    207.     // 清空链表
    208.     public void clear(){
    209.         // 暴力解法：把head置为null，那么就没有引用指向这个头节点了
    210.         // 那么这个头节点就会被垃圾回收器给回收掉
    211.         // head = null;
    212.  
    213.         // 上面那种方式可能会出现不安全的情况，因此采用遍历的形式
    214.         listNode cur = head;
    215.         while (cur != null) {
    216.             // cur.val = null;
    217.             listNode curNext = cur.next;
    218.             cur.next = null;
    219.             cur = curNext;
    220.         }
    221.         head = null;
    222.     }
    223. }

    AddlndexofException异常： 

    1. public class AddIndexofException extends RuntimeException{
    2.     public AddIndexofException() {
    3.         super();
    4.     }
    5.  
    6.     public AddIndexofException(String msg) {
    7.         super(msg);
    8.     }
    9. }

     NotFindException异常：

    1. public class NotFindException extends RuntimeException{
    2.     public NotFindException() {
    3.         super();
    4.     }
    5.  
    6.     public NotFindException(String msg) {
    7.         super(msg);
    8.     }
    9. }

     SingleLinkedisEmptyException异常：

    1. public class SingleLinkedisEmptyException extends RuntimeException{
    2.     public SingleLinkedisEmptyException() {
    3.         super();
    4.     }
    5.  
    6.     public SingleLinkedisEmptyException(String msg) {
    7.         super(msg);
    8.     }
    9. }

     这里来说明一下：为什么节点的引用是节点类型？

    首先，我们最开始在学习引用的时候，说过引用其实就是一个变量类型，用来存放地址。而在C语言中是用指针来存放地址，按照C语言的说法，节点的地址就得用节点类型的指针来接收。那么listNode 类型的 next，就得用 listNode 来接收（引用）。就好像，在 new 应该对象时，这个对象的地址会给到一个引用变量，而这个引用变量的类型就是 new 关键字后面的。例如：Person person = new Person();  。

    双链表的学习，点我

    上面这篇博文是关于链表的基础知识、链表的分类以及单链表的实现。都详细的进行了说明。

    手动实现双链表的源码

    1. public class MyLinkedList implements LinkedList {
    2.     //创建一个节点内部类
    3.     static class ListNode {
    4.         int val;
    5.         ListNode prev;
    6.         ListNode next;
    7.  
    8.         public ListNode(int val) {
    9.             this.val = val;
    10.         }
    11.     }
    12.     public ListNode head;
    13.     public ListNode last;
    14.  
    15.     // 头插
    16.     @Override
    17.     public void addFirst(int data) {
    18.         // 创建一个新的节点
    19.         ListNode newNode = new ListNode(data);
    20.         // 先判断链表是否为空
    21.         if (head == null) {
    22.             head = newNode;
    23.             last = newNode;
    24.         }else {
    25.             newNode.next = head;
    26.             head.prev = newNode;
    27.             head = newNode;
    28.         }
    29.     }
    30.  
    31.     @Override
    32.     public void addLast(int data) {
    33.         // 创建一个新的节点
    34.         ListNode newNode = new ListNode(data);
    35.         // 先判断链表是否为空
    36.         if (head == null) {
    37.             head = newNode;
    38.             last = newNode;
    39.         }else {
    40.             last.next = newNode;
    41.             newNode.prev = last;
    42.             last = newNode;
    43.         }
    44.     }
    45.  
    46.     @Override
    47.     public void addIndex(int data, int index) throws addIndexOfException {
    48.         // 判断这个index是否合法
    49.         if (index < 0 || index > size()) {
    50.             // 抛异常
    51.             throw new addIndexOfException("下标位置不合法异常！");
    52.         }
    53.         if (index == 0) {
    54.             // 头插
    55.             addFirst(data);
    56.         } else if (index == size()) {
    57.             // 尾插
    58.             addLast(data);
    59.         } else {
    60.             // 创建一个新的节点
    61.             ListNode newNode = new ListNode(data);
    62.             ListNode cur = head;
    63.             // 找到要插入的前一个位置
    64.             while (index-1 > 0) {
    65.                 cur = cur.next;
    66.                 index--;
    67.             }
    68.             ListNode curNext = cur.next;
    69.             cur.next = newNode;
    70.             newNode.next = curNext;
    71.             newNode.prev = cur;
    72.             curNext.prev = newNode;
    73.         }
    74.     }
    75.  
    76.     @Override
    77.     public boolean contains(int key) {
    78.         ListNode cur = head;
    79.         while (cur != null) {
    80.             if (cur.val == key) {
    81.                 return true;
    82.             }
    83.             cur = cur.next;
    84.         }
    85.         return false;
    86.     }
    87.  
    88.     @Override
    89.     public void remove(int key) {
    90.         if (head == null) {
    91.             // 链表为空，就抛异常
    92.             throw new LinkedListIsEmptyException("链表为空异常！");
    93.         }else if (head.next == null) {
    94.             // 链表里面只有一个元素
    95.             if (head.val == key) {
    96.                 head = null;
    97.                 last = null;
    98.                 return;
    99.             }else {
    100.                 throw new NotFindException("找不到要删除的数异常！");
    101.             }
    102.         }else {
    103.             // 头删
    104.             if (head.val == key) {
    105.                 head = head.next;
    106.                 return;
    107.             } else if (last.val == key) {
    108.                 // 尾删
    109.                 last = last.prev;
    110.                 last.next = null;
    111.                 return;
    112.             }
    113.             ListNode cur = head;
    114.             while (cur != null) {
    115.                 if (cur.val == key) {
    116.                     // 开始删除
    117.                     ListNode curNext = cur.next;
    118.                     cur.prev.next = curNext;
    119.                     curNext.prev = cur.prev;
    120.                     return;
    121.                 }
    122.                 cur = cur.next;
    123.             }
    124.             throw new NotFindException("找不到要删除的数异常！");
    125.         }
    126.     }
    127.  
    128.     @Override
    129.     public void removeAllkey(int key) {
    130.         if (head == null) {
    131.             // 链表为空，就抛异常
    132.             throw new LinkedListIsEmptyException("链表为空异常！");
    133.         }else if (head.next == null) {
    134.             // 链表里面只有一个元素
    135.             if (head.val == key) {
    136.                 head = null;
    137.                 last = null;
    138.                 return;
    139.             }else {
    140.                 throw new NotFindException("找不到要删除的数异常！");
    141.             }
    142.         }else {
    143.             boolean flag = false;
    144.             // 头删
    145.             while (head.val == key) {
    146.                 flag = true;
    147.                 head = head.next;
    148.                 if (head == null) {
    149.                     return;
    150.                 }
    151.             }
    152.             while (last.val == key) {
    153.                 // 尾删
    154.                 flag = true;
    155.                 last = last.prev;
    156.                 last.next = null;
    157.             }
    158.             ListNode cur = head;
    159.             while (cur != null) {
    160.                 if (cur.val == key) {
    161.                     // 开始删除
    162.                     flag = true;
    163.                     ListNode curNext = cur.next;
    164.                     cur.prev.next = curNext;
    165.                     curNext.prev = cur.prev;
    166.                 }
    167.                 cur = cur.next;
    168.             }
    169.             if (!flag) {
    170.                 throw new NotFindException("找不到要删除的数异常！");
    171.             }
    172.         }
    173.     }
    174.  
    175.     @Override
    176.     public int size() {
    177.         ListNode cur = head;
    178.         int count = 0;
    179.         while (cur != null) {
    180.             count++;
    181.             cur = cur.next;
    182.         }
    183.         return count;
    184.     }
    185.  
    186.     @Override
    187.     public void clear() {
    188.         // 暴力做法
    189.         // head = last = null;
    190.  
    191.         // 温柔做法
    192.         ListNode cur = head;
    193.         while (cur != null) {
    194.             // cur.val = null;
    195.             cur.prev = null;
    196.             ListNode curNext = cur.next;
    197.             cur.next = null;
    198.             cur = curNext;
    199.         }
    200.         head = last = null;
    201.     }
    202.  
    203.     @Override
    204.     public void display() {
    205.         ListNode cur = head;
    206.         while (cur != null) {
    207.             System.out.print(cur.val+" ");
    208.             cur = cur.next;
    209.         }
    210.         System.out.println();
    211.     }
    212. }

     addlndexOfException异常：

    1. public class addIndexOfException extends RuntimeException {
    2.     public addIndexOfException(String msg) {
    3.         super(msg);
    4.     }
    5.  
    6.     public addIndexOfException() {
    7.         super();
    8.     }
    9. }

    LinkedListlsEmptyException异常：

    1. public class LinkedListIsEmptyException extends RuntimeException {
    2.     public LinkedListIsEmptyException(String msg) {
    3.         super(msg);
    4.     }
    5.     public LinkedListIsEmptyException() {
    6.         super();
    7.     }
    8. }

     NotFindException异常：

    1. public class NotFindException extends RuntimeException {
    2.     public NotFindException(String msg) {
    3.         super(msg);
    4.     }
    5.     public NotFindException() {
    6.         super();
    7.     }
    8. }

    单链表和双链表在代码上，总体来说，大差不差。

    分析 LinkedList 的源码 

    LinkedList的底层使用了双向链表 

    LinkedList的使用 

    构造方法与 ArrayList 差不多，只有一个无参的和一个带参数的。带参的类型是实现了Collection接口就行。

    常用方法 

    方法说明
    boolean add(E e)尾插 e
    void add(int index, E element)将 e 插入到 index 位置
    boolean addAll(Collection c)尾插 c 中的所有元素
    E remove(int index)删除 index位置元素
    boolean remove(Object o)删除遇到的第一个o
    E get(int index)获取下标index 位置元素
    E set(int index, E element)将下标index位置元素设置为 element
    void clear()清空
    boolean contains(Object o)判断o是否在链表中
    int indexOf(Object o)返回第一个o所在下标
    int lastlndexOf(Object o)返回最后一个o的下标
    List subList(int fromlndex, int tolndex)截取部分list 

    同样这里 subList 的截取不会产生新的对象。

    其遍历方式和 ArrayList 是一样的。

    ArrayList和LinkedList的区别

    区别ArrayListLinkedList
    存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
    随机访问支持0(1)不支持：O(N)
    头插需要搬移元素，效率低O(N)只需修改引用的指向，时间复杂度为O(1)
    插入空间不够时需要扩容没有容量的概念
    应用场景元素高效存储+频繁访问任意位置插入和删除频繁

    好啦！本期 数据结构之LinkedList与链表（上）的学习之旅就到此结束啦！我们下一期再一起学习吧！

  • 相关阅读:
    微信小程序：用户基本信息的采集
    每日论文阅读 2022-11-11
    金仓数据库KingbaseES客户端应用参考手册--17. vacuumdb
    语义推理的功能组件动态绑定研究
    Centos 安装 OpenLDAP
    问一下ChatGPT如何学习开发iOS应用程序
    C++ 变量的声明和初始化方式
    React跨路由组件动画
    分库分表订单全局ID
    Git常用指令-1
  • 原文地址：https://blog.csdn.net/2301_80854132/article/details/139563576