当前位置： 首页 > article >正文

【Java】LinkedList实现类的使用

article 2024/10/27 17:18:21
LinkedList实现类的使用
  1. package com.star.test04;
  3. import java.util.Iterator;
  4. import java.util.LinkedList;
  6. /**
  7.  * @author : Starshine
  8.  */
  9. public class Test {
  10.     //这是main方法，程序的入口
  11.     public static void main(String[] args) {
  12.         /*
  13.         LinkedList常用方法：
  14.         增加 addFirst(E e) addLast(E e)
  15.              offer(E e) offerFirst(E e) offerLast(E e)
  16.         删除 poll()
  17.             pollFirst() pollLast()  ---》JDK1.6以后新出的方法，提高了代码的健壮性
  18.             removeFirst() removeLast()
  19.         修改
  20.         查看 element()
  21.              getFirst()  getLast()
  22.              indexOf(Object o)   lastIndexOf(Object o)
  23.              peek()
  24.              peekFirst() peekLast()
  25.         判断
  26.          */
  27.         //创建一个LinkedList集合对象：
  28.         LinkedList<String> list = new LinkedList<>();
  29.         list.add("aaaaa");
  30.         list.add("bbbbb");
  31.         list.add("ccccc");
  32.         list.add("ddddd");
  33.         list.add("eeeee");
  34.         list.add("bbbbb");
  35.         list.add("fffff");
  37.         list.addFirst("jj");
  38.         list.addLast("hh");
  40.         list.offer("kk");//添加元素在尾端
  41.         list.offerFirst("pp");
  42.         list.offerLast("rr");
  43.         System.out.println(list);//LinkedList可以添加重复数据
  44.         System.out.println(list.poll());//删除头上的元素并且将元素输出
  45.         System.out.println(list.pollFirst());
  46.         System.out.println(list.pollLast());
  48.         System.out.println(list.removeFirst());
  49.         System.out.println(list.removeLast());
  50.         System.out.println(list);//LinkedList可以添加重复数据
  52.         /*list.clear();//清空集合
  53.         System.out.println(list);*/
  54.         /*System.out.println(list.pollFirst());*/
  55.         /*System.out.println(list.removeFirst());报错：Exception in thread "main" java.util.NoSuchElementException*/
  58.         //集合的遍历：
  59.         System.out.println("---------------------");
  60.         //普通for循环：
  61.         for(int i = 0;i<list.size();i++){
  62.             System.out.println(list.get(i));
  63.         }
  64.         System.out.println("---------------------");
  65.         //增强for：
  66.         for(String s:list){
  67.             System.out.println(s);
  68.         }
  69.         System.out.println("---------------------");
  70.         //迭代器：
  71.         /*Iterator<String> it = list.iterator();
  72.         while(it.hasNext()){
  73.             System.out.println(it.next());
  74.         }*/
  75.         //下面这种方式好，节省内存
  76.         for(Iterator<String> it = list.iterator();it.hasNext();){
  77.             System.out.println(it.next());
  78.         }
  79.     }
  80. }

LinkedList简要底层原理图

模拟LinkedList源码
  1. package com.star.test05;
  3. /**
  4.  * @author : Starshine
  5.  */
  6. public class MyLinkedList {
  7.     //链中一定有一个首节点：
  8.     Node first;
  9.     //链中一定有一个尾节点：
  10.     Node last;
  11.     //计数器：
  12.     int count = 0;
  13.     //提供一个构造器：
  14.     public MyLinkedList(){
  16.     }
  17.     //添加元素方法：
  18.     public void add(Object o){
  19.         if(first == null){//证明你添加的元素是第一个节点：
  20.             //将添加的元素封装为一个Node对象：
  21.             Node n = new Node();
  22.             n.setPre(null);
  23.             n.setObj(o);
  24.             n.setNext(null);
  25.             //当前链中第一个节点变为n
  26.             first = n;
  27.             //当前链中最后一个节点变为n
  28.             last = n;
  29.         }else{//证明已经不是链中第一个节点了
  30.             //将添加的元素封装为一个Node对象：
  31.             Node n = new Node();
  32.             n.setPre(last);//n的上一个节点一定是当前链中的最后一个节点last
  33.             n.setObj(o);
  34.             n.setNext(null);
  35.             //当前链中的最后一个节点的下一个元素 要指向n
  36.             last.setNext(n);
  37.             //将最后一个节点变为n
  38.             last = n;
  39.         }
  40.         //链中元素数量加1
  41.         count++;
  42.     }
  44.     //得到集合中元素的数量：
  45.     public int getSize(){
  46.         return count;
  47.     }
  49.     //通过下标得到元素：
  50.     public Object get(int index){
  51.         //获取链表的头元素：
  52.         Node n = first;
  53.         //一路next得到想要的元素
  54.         for(int i=0;i<index;i++){
  55.             n = n.getNext();
  56.         }
  57.         return n.getObj();
  58.     }
  59. }
  60. class Test{
  61.     //这是main方法，程序的入口
  62.     public static void main(String[] args) {
  63.         //创建一个MyLinkedList集合对象：
  64.         MyLinkedList ml = new MyLinkedList();
  65.         ml.add("aa");
  66.         ml.add("bb");
  67.         ml.add("cc");
  68.         System.out.println(ml.getSize());
  69.         System.out.println(ml.get(0));
  70.     }
  71. }

debug验证数据添加成功：

LinkedList源码解析

【1】JDK1.7和JDK1.8的LinkedList的源码是一致的

【2】源码：

  1. public class LinkedList<E>{//E是一个泛型，具体的类型要在实例化的时候才会最终确定
  2.         transient int size = 0;//集合中元素的数量
  3.         //Node的内部类
  4.         private static class Node<E> {
  5.         E item;//当前元素
  6.         Node<E> next;//指向下一个元素地址
  7.         Node<E> prev;//上一个元素地址
  9.         Node(Node<E> prev, E element, Node<E> next) {
  10.             this.item = element;
  11.             this.next = next;
  12.             this.prev = prev;
  13.         }
  14.     }
  16.         transient Node<E> first;//链表的首节点
  17.         transient Node<E> last;//链表的尾节点
  18.         //空构造器：
  19.         public LinkedList() {
  20.     }
  21.         //添加元素操作：
  22.         public boolean add(E e) {
  23.         linkLast(e);
  24.         return true;
  25.     }
  26.         void linkLast(E e) {//添加的元素e
  27.         final Node<E> l = last;//将链表中的last节点给l 如果是第一个元素的话 l为null
  28.                 //将元素封装为一个Node具体的对象：
  29.         final Node<E> newNode = new Node<>(l, e, null);
  30.                 //将链表的last节点指向新的创建的对象：
  31.         last = newNode;
  32.                
  33.         if (l == null)//如果添加的是第一个节点
  34.             first = newNode;//将链表的first节点指向为新节点
  35.         else//如果添加的不是第一个节点
  36.             l.next = newNode;//将l的下一个指向为新的节点
  37.         size++;//集合中元素数量加1操作
  38.         modCount++;
  39.     }
  40.         //获取集合中元素数量
  41.         public int size() {
  42.         return size;
  43.     }
  44.         //通过索引得到元素：
  45.         public E get(int index) {
  46.         checkElementIndex(index);//健壮性考虑
  47.         return node(index).item;
  48.     }
  49.        
  50.     Node<E> node(int index) {
  51.         //如果index在链表的前半段，那么从前往后找
  53.         if (index < (size >> 1)) {
  54.             Node<E> x = first;
  55.             for (int i = 0; i < index; i++)
  56.                 x = x.next;
  57.             return x;
  58.         } else {//如果index在链表的后半段，那么从后往前找
  59.             Node<E> x = last;
  60.             for (int i = size - 1; i > index; i--)
  61.                 x = x.prev;
  62.             return x;
  63.         }
  64.     }
  66. }
面试题：iterator(),Iterator,Iterable关系

【1】面试题：对应的关系：

【2】hasNext(),next()的具体实现：

【3】增强for循环  底层也是通过迭代器实现的：

ListIterator迭代器

【1】加入字符串：

  1. package com.star.test06;
  3. import java.util.ArrayList;
  4. import java.util.Iterator;
  5. import java.util.List;
  7. /**
  8.  * @author : Starshine
  9.  */
  10. public class Test2 {
  11.     //这是main方法，程序的入口
  12.     public static void main(String[] args) {
  13.         ArrayList<String> list = new ArrayList<>();
  14.         list.add("aa");
  15.         list.add("bb");
  16.         list.add("cc");
  17.         list.add("dd");
  18.         list.add("ee");
  19.         //在"cc"之后添加一个字符串"kk"
  20.         Iterator<String> it = list.iterator();
  21.         while(it.hasNext()){
  22.             if("cc".equals(it.next())){
  23.                 list.add("kk");
  24.             }
  25.         }
  27.     }
  28. }

发现报错：

出错原因：就是迭代器和list同时对集合进行操作：

解决办法：事情让一个“人”做 --》引入新的迭代器：ListIterator

迭代和添加操作都是靠ListIterator来完成的：

  1. package com.star.test06;
  3. import java.util.ArrayList;
  4. import java.util.Iterator;
  5. import java.util.List;
  6. import java.util.ListIterator;
  8. /**
  9.  * @author : Starshine
  10. */
  11. public class Test2 {
  12.     //这是main方法，程序的入口
  13.     public static void main(String[] args) {
  14.         ArrayList<String> list = new ArrayList<>();
  15.         list.add("aa");
  16.         list.add("bb");
  17.         list.add("cc");
  18.         list.add("dd");
  19.         list.add("ee");
  20.         //在"cc"之后添加一个字符串"kk"
  21.         ListIterator<String> it = list.listIterator();
  22.         while(it.hasNext()){
  23.             if("cc".equals(it.next())){
  24.                 it.add("kk");
  25.             }
  26.         }
  27.         System.out.println(it.hasNext());
  28.         System.out.println(it.hasPrevious());
  29.         //逆向遍历：
  30.         while(it.hasPrevious()){
  31.             System.out.println(it.previous());
  32.         }
  33.         System.out.println(it.hasNext());
  34.         System.out.println(it.hasPrevious());
  35.         System.out.println(list);
  37.     }
  38. }

http://www.kler.cn/news/367546.html

相关文章：

  • RestHighLevelClient操作es查询文档
  • 质量漫谈一
  • HarmonyOS 相对布局（RelativeContainer）
  • 逻辑回归与神经网络
  • Selenium爬虫技术：如何模拟鼠标悬停抓取动态内容
  • nginx 路径匹配,关于“/“对规则的影响
  • 苹果预告下周发布Mac新品：全系标配M4系列芯片
  • 前端处理API接口故障：多接口自动切换的实现方案
  • bluez hid host介绍，连接键盘/鼠标/手柄不是梦，安排
  • 日常实习与暑期实习详解
  • java使用正则表达式校验字符串pwd,是否符合包含大写小写数字特殊字符长度超过8位
  • Codeforces Round 981 (Div. 3) A - E 详细题解(C++)
  • maven分模块设计与私服
  • 如何用mmclassification训练多标签多分类数据
  • 如何理解前端与后端开发
  • entwine 和 conda环境下 使用和踩坑 详细步骤! 已解决
  • uptime kuma拨测系统
  • 身份证归属地查询接口-在线身份证归属地查询-身份证归属地查询API
  • 论文略读：Less is More: on the Over-Globalizing Problem in Graph Transformers
  • 2FA-双因素认证
  • 基于Python的智能求职分析系统
  • python 使用 企微机器人发送消息
  • 安全日志记录的重要性
  • 今天不分享技术，分享秋天的故事
  • Spring Boot框架下的厨艺社区开发
  • ALLO数据集：首个为月球轨道机器人近距离操作设计的异常检测基准开源数据集。