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

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

作者：weixin_40725706 | 2024-06-16 10:10:59

赞

踩

数据结构之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<? extends E> 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<E> subList(int fromlndex, int tolndex)截取部分list 

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

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

ArrayList和LinkedList的区别

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

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

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

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

  

闽ICP备14008679号