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

Java集合类——LinkedList（单链表及双链表）_java有哪些类用了链表

作者：秋刀鱼在做梦 | 2024-07-30 20:13:32

赞

踩

java有哪些类用了链表

一，ArrayList的缺陷

1.空间浪费

在之前的博客中，我利用源码详细的讲解了ArrayList这个集合类（尤其是扩容机制），可以知道ArrayList的底层主要是一个动态的可变数组，容量满的时候需要进行1.5倍扩容。但是我们现在考虑这样一个问题，假设ArrayList底层数组的容量是100，我们需要存放101个元素时，当存放第101个元素时需要1.5倍扩容（扩容之后的容量是150），此时势必会造成49个存储空间的浪费！

2.时间开销大

ArrayList底层是一个数组，当我们对顺序表进行插入和删除时，需要移动大量的元素，大大提高了时间复杂度，所以可以看出ArrayList并不适用于进行大量插入和删除的操作。

针对上述ArrayList的两大缺陷，Java是否提供了其他的集合类或者数据结构来解决呢？

1.进行元素扩容时能否根据需求来进行扩容，需要多少空间就去申请多少空间；

2.在进行插入和删除的时候，可不可以不需要移动大量元素。

今天所要介绍的LinkedList集合类和链表的数据结构将很好的解决这两个问题！！！

二，链表

2.1 链表的概念

相对于顺序表，链表是一种在逻辑上连续，在存储上不一定连续的数据结构。其中链表每个元素之间的逻辑关系是通过引用来实现的。

链表中的每一个元素称为一个节点，每一个节点至少包含两类数据：

1.数据域（存放该节点的数据信息）

2.节点域（实现链表节点与节点之间的逻辑关系，对于单链表来说只需要存储一个next即可（存储下一个节点的地址），对于双链表来说则需要存储next和prev（分别存储下一个节点和前一个节点的地址））

2.2 链表的分类

1.单向或者双向

2.带头或者不带头

3.循环或者非循环

我们只需要重点掌握两种即可：

1.无头单向非循环链表（因为笔试的OJ题中经常会考）；

2.无头双向链表（因为LinkedList的底层就是不带头的双链表）。 

三，顺序表和链表的区别

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

四，无头单向非循环链表的实现

定义一个MySingleList类来实现单链表的方法，用TestMySingleList类来测试MySingleList类的方法

  1. import java.util.List;
  2.  
  3. public class MySingleList {
  4.     static class ListNode {
  5.         public int val;
  6.         public ListNode next;
  7.  
  8.         public ListNode(int val) {
  9.             this.val = val;
  10.         }
  11.     }
  12.  
  13.     ListNode head;//第一节点的引用，默认为null
  14.  
  15.     //打印链表
  16.     public void display() {
  17.         ListNode cur = this.head;
  18.         while (cur != null) {
  19.             System.out.print(cur.val + " ");
  20.             cur = cur.next;
  21.         }
  22.         System.out.println();
  23.     }
  24.  
  25.     //获取链表长度
  26.     public int size() {
  27.         ListNode cur = this.head;
  28.         int count = 0;
  29.         while (cur != null) {
  30.             count++;
  31.             cur = cur.next;
  32.         }
  33.         return count;
  34.     }
  35.  
  36.     //头插法
  37.     public void addFirst(int data) {
  38.         ListNode node = new ListNode(data);
  39.         node.next = this.head;
  40.         this.head = node;
  41.     }
  42.  
  43.     //尾插法
  44.     public void addLast(int data) {
  45.         ListNode node = new ListNode(data);
  46.         ListNode cur = this.head;
  47.         if (this.head == null) {
  48.             this.head = node;
  49.         } else {
  50.             while (cur.next != null) {
  51.                 cur = cur.next;
  52.             }
  53.             //此时已经处于尾节点
  54.             cur.next = node;
  55.         }
  56.     }
  57.  
  58.     //任意index位置插入（假设第一个节点的下表为0）
  59.     public void add(int index, int data) {
  60.         //判断index位置的合法性
  61.         if (index < 0 || index > size()) {
  62.             System.out.println("index位置不合法！");//也可以抛异常
  63.         } else if (index == 0) {
  64.             addFirst(data);
  65.         } else if (index == size()) {
  66.             addLast(data);
  67.         } else {
  68.             //1.找到所需插入index位置的前驱
  69.             ListNode cur = findIndexPrev(index);
  70.             //2.修改引用的指向
  71.             ListNode node = new ListNode(data);
  72.             node.next = cur.next;
  73.             cur.next = node;
  74.         }
  75.     }
  76.  
  77.     private ListNode findIndexPrev(int index) {
  78.         ListNode cur = this.head;
  79.         while (index - 1 != 0) {
  80.             cur = cur.next;
  81.             index--;
  82.         }
  83.         return cur;
  84.     }
  85.  
  86.     //删除第一次出现的关键字key
  87.     public void remove(int key) {
  88.         if (this.head == null) {
  89.             System.out.println("链表为空！");
  90.             return;
  91.         }
  92.         if (this.head.val == key) {
  93.             this.head = this.head.next;
  94.             return;
  95.         }
  96.         ListNode cur = findPrev(key);//找到所需删除关键字key的前驱
  97.         if (cur == null) {
  98.             System.out.println("没有关键字key！");
  99.         } else {
  100.             cur.next = cur.next.next;
  101.         }
  102.     }
  103.  
  104.     private ListNode findPrev(int key) {
  105.         ListNode cur = this.head;
  106.         while (cur.next != null) {
  107.             if (cur.val == key) {
  108.                 return cur;
  109.             }
  110.             cur = cur.next;
  111.         }
  112.         return null;
  113.     }
  114.  
  115.     //删除所有出现的关键字key
  116.     public void removeAllKey(int key) {
  117.         if (this.head == null) {
  118.             System.out.println("链表为空！");
  119.             return;
  120.         }
  121.         ListNode prev = this.head;
  122.         ListNode cur = this.head.next;
  123.         while (cur != null) {
  124.             if (cur.val == key) {
  125.                 prev.next = cur.next;
  126.                 cur = cur.next;
  127.             } else {
  128.                 prev = cur;
  129.                 cur = cur.next;
  130.             }
  131.         }
  132.         if (this.head.val == key) {
  133.             this.head = this.head.next;
  134.         }
  135.     }
  136.  
  137.     //清空链表
  138.     public void clear() {
  139.         this.head = null;//单链表只需要将指向第一个节点的引用指向null即可
  140.     }
  141. }
  1. public class TestMySingleList {
  2.     public static void main(String[] args) {
  3.         MySingleList mySingleList = new MySingleList();
  4.         mySingleList.addLast(1);
  5.         mySingleList.addLast(2);
  6.         mySingleList.addLast(3);
  7.         mySingleList.addLast(4);
  8.         mySingleList.addLast(5);
  9.         mySingleList.display();
  10.         mySingleList.addFirst(0);
  11.         mySingleList.display();
  12.         mySingleList.remove(0);
  13.         mySingleList.addLast(1);
  14.         mySingleList.addLast(1);
  15.         mySingleList.addLast(1);
  16.         mySingleList.removeAllKey(1);
  17.         mySingleList.display();
  18.     }
  19. }

 

五，无头双向非循环链表的实现

定义一个MyLinkedList类来实现单链表的方法，用TestMyLinkedList类来测试MyLinkedList类的方法

  1. public class MyLinkedList {
  2.     static class ListNode {
  3.         public int val;
  4.         public ListNode prev;
  5.         public ListNode next;
  6.  
  7.         public ListNode(int val) {
  8.             this.val = val;
  9.         }
  10.     }
  11.  
  12.     ListNode head;//定义一个头引用，默认为null
  13.     ListNode tail;//定义一个尾引用，默认为null
  14.  
  15.     //打印链表
  16.     public void display() {
  17.         ListNode cur = this.head;
  18.         while (cur != null) {
  19.             System.out.print(cur.val + " ");
  20.             cur = cur.next;
  21.         }
  22.         System.out.println();
  23.     }
  24.  
  25.     //获取链表长度
  26.     public int size() {
  27.         ListNode cur = this.head;
  28.         int count = 0;
  29.         while (cur != null) {
  30.             count++;
  31.             cur = cur.next;
  32.         }
  33.         return count;
  34.     }
  35.  
  36.     //判断链表是否包含某个元素key
  37.     public boolean contains(int key) {
  38.         ListNode cur = this.head;
  39.         while (cur != null) {
  40.             if (cur.val == key) {
  41.                 return true;
  42.             }
  43.             cur = cur.next;
  44.         }
  45.         return false;
  46.     }
  47.  
  48.     //头插法
  49.     public void addFirst(int data) {
  50.         ListNode node = new ListNode(data);
  51.         if (this.head == null) {
  52.             this.head = node;
  53.             this.tail = node;
  54.         } else {
  55.             node.next = this.head;
  56.             this.head.prev = node;
  57.             this.head = node;
  58.         }
  59.     }
  60.  
  61.     //尾插法
  62.     public void addLast(int data) {
  63.         ListNode node = new ListNode(data);
  64.         if (this.head == null) {
  65.             this.head = node;
  66.             this.tail = node;
  67.         } else {
  68.             this.tail.next = node;
  69.             node.prev = this.tail;
  70.             this.tail = node;
  71.         }
  72.     }
  73.  
  74.     //任意index位置插入（假设第一个节点的下标为0）
  75.     public void add(int index, int data) {
  76.         //判断index位置的合法性
  77.         if (index < 0 || index > size()) {
  78.             System.out.println("index位置不合法！");//也可以抛异常
  79.         } else if (index == 0) {
  80.             addFirst(data);
  81.         } else if (index == size()) {
  82.             addLast(data);
  83.         } else {
  84.             //1.找到index位置的节点
  85.             ListNode cur = findIndexPrev(index);
  86.             //2.修改指向的引用
  87.             ListNode node = new ListNode(data);
  88.             node.next = cur;
  89.             node.prev = cur.prev;
  90.             cur.prev.next = node;
  91.             cur.prev = node;
  92.         }
  93.     }
  94.  
  95.     private ListNode findIndexPrev(int index) {
  96.         ListNode cur = this.head;
  97.         while (index != 0) {
  98.             cur = cur.next;
  99.             index--;
  100.         }
  101.         return cur;
  102.     }
  103.  
  104.     //删除第一次出现的关键字key
  105.     public void remove(int key) {
  106.         if (this.head == null) {
  107.             System.out.println("链表为空！");
  108.             return;
  109.         }
  110.         ListNode cur = this.head;
  111.         while (cur != null) {
  112.             if (cur.val == key) {
  113.                 if (cur == this.head) {
  114.                     this.head = this.head.next;
  115.                     if (this.head != null) {
  116.                         this.head.prev = null;
  117.                     } else {
  118.                         this.tail = null;
  119.                     }
  120.                 } else {
  121.                     cur.prev.next = cur.next;
  122.                     if (cur.next != null) {
  123.                         cur.next.prev = cur.prev;
  124.                     } else {
  125.                         this.tail = cur.prev;
  126.                         this.tail.next = null;
  127.                     }
  128.                 }
  129.                 return;
  130.             }
  131.             cur = cur.next;
  132.         }
  133.     }
  134.  
  135.     //删除所有出现的关键字key
  136.     public void removeAllKey(int key) {
  137.         if (this.head == null) {
  138.             System.out.println("链表为空！");
  139.             return;
  140.         }
  141.         ListNode cur = this.head;
  142.         while (cur != null) {
  143.             if (cur.val == key) {
  144.                 if (cur == this.head) {
  145.                     this.head = this.head.next;
  146.                     if (this.head != null) {
  147.                         this.head.prev = null;
  148.                     } else {
  149.                         this.tail = null;
  150.                     }
  151.                 } else {
  152.                     cur.prev.next = cur.next;
  153.                     if (cur.next != null) {
  154.                         cur.next.prev = cur.prev;
  155.                     } else {
  156.                         this.tail = cur.prev;
  157.                         this.tail.next = null;
  158.                     }
  159.                 }
  160.             }
  161.             cur = cur.next;
  162.         }
  163.     }
  164.  
  165.     //清空链表
  166.     public void clear() {
  167.         ListNode cur = this.head;
  168.         while (cur != null) {
  169.             ListNode curNext = cur.next;
  170.             cur.prev = null;
  171.             cur.next = null;
  172.             cur = curNext;
  173.         }
  174.         this.head = null;
  175.         this.tail = null;
  176.     }
  177. }
  1. public class TestMyLinkedList {
  2.     public static void main(String[] args) {
  3.         MyLinkedList myLinkedList = new MyLinkedList();
  4.         myLinkedList.addLast(1);
  5.         myLinkedList.addLast(2);
  6.         myLinkedList.addLast(3);
  7.         myLinkedList.addLast(4);
  8.         myLinkedList.addLast(5);
  9.         myLinkedList.addFirst(0);
  10.         myLinkedList.display();
  11.         myLinkedList.remove(0);
  12.         myLinkedList.display();
  13.         myLinkedList.add(2,10);
  14.         myLinkedList.display();
  15.         myLinkedList.addLast(1);
  16.         myLinkedList.addLast(1);
  17.         myLinkedList.removeAllKey(1);
  18.         myLinkedList.display();
  19.     }
  20. }

 

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

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

  

闽ICP备14008679号