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

Java——LinkedList

作者：笔触狂放9 | 2024-06-17 11:24:26

赞

踩

Java——LinkedList

1、链表

1.1 链表的概念及结构

链表在逻辑层面上是连续的，在物理层面上不一定是连续的

链表结构可分为，单向或双向、带头或不带头、循环或非循环，组合共计8种

重点：无头单向非循环链表、无头双向链表

1.2 模拟实现无头单向非循环链表

一个链表由若干节点组成，结合 内部类 知识，可将节点类定义在链表类中，成为内部类

  1. public class MySingleLinkedList {
  2.  
  3.     static class ListNode {//该内部类中定义的是节点的属性
  4.         public int val;
  5.         public ListNode next;
  6.  
  7.         public ListNode(int val) {
  8.             this.val = val;
  9.         }
  10.     }
  11.  
  12.     public ListNode head;//链表的头节点，定义在MySingleLinkedList类中
  13.     
  14. }

下面以穷举的方式创建链表方便理解（真正创建链表并非如此）

  1. //MySingleLinkedList类
  2.  
  3.     //该方法创建一个链表，头节点为node1，当该方法结束后，变量node1...都会销毁，只剩下头节点为head的链表
  4.     public void createdList(){
  5.         ListNode node1 = new ListNode(1);
  6.         ListNode node2 = new ListNode(2);
  7.         ListNode node3 = new ListNode(3);
  8.         ListNode node4 = new ListNode(4);
  9.         ListNode node5 = new ListNode(5);
  10.  
  11.         node1.next = node2;
  12.         node2.next = node3;
  13.         node3.next = node4;
  14.         node4.next = node5;
  15.  
  16.         this.head = node1;
  17.     }

打印链表

  1. //MySingleLinkedList 类
  2.  
  3.     public void display() {
  4.         ListNode cur = head; //若直接使用head进行遍历打印，将只能打印一次，再次调用该函数，头节点就不在原来的位置了
  5.         while(cur != null) { //注意！此处若写成 cur.next != null 则不会打印最后一个节点
  6.             System.out.print(cur.val + " ");
  7.             cur = cur.next;
  8.         }
  9.     }

求链表长度：

  1.     //遍历即可
  2.     public int size() {
  3.         ListNode cur = head;
  4.         int count = 0;
  5.         while(cur != null) {
  6.             cur = cur.next;
  7.             count++;
  8.         }
  9.         return count;
  10.     }

头插法：

  1.     public void addFirst(int data) {
  2.         ListNode newNode = new ListNode(data);
  3.         newNode.next = head;
  4.         head = newNode;
  5.     }

尾插法：

  1.     public void addLast(int data) {
  2.         ListNode newNode = new ListNode(data);
  3.         //不要忘记：判空！
  4.         if(head == null) {
  5.             head = newNode;
  6.             return;
  7.         }
  8.         ListNode cur = head;
  9.         while(cur.next != null) { //此处若写成 cur.next != null 则不会打印最后一个节点
  10.             cur = cur.next;
  11.         }
  12.         cur.next = newNode;
  13.     }

在index位置插入

  1. // IndexNotLegalException 异常类
  2. public class IndexNotLegalException extends RuntimeException{
  3.     public IndexNotLegalException() {
  4.  
  5.     }
  6.     public IndexNotLegalException(String msg) {
  7.         super(msg);
  8.     }
  9. }
  10.  
  11.  
  12. // MySingleLinkedList 类
  13.     public void addIndex(int index, int data) {
  14.         //1、判断index合法性
  15.         try{
  16.             checkIndex(index);
  17.         }catch(IndexNotLegalException e) {
  18.             e.printStackTrace();
  19.         }
  20.         //2、index == 0 || index == size()
  21.         if(index == 0) {
  22.             addFirst(data);
  23.             return;
  24.         }
  25.         if(index == size()) {
  26.             addLast(data);
  27.             return;
  28.         }
  29.         //3、找到index的前一个位置
  30.         ListNode cur = findIndexSubOne(index);
  31.         //4、进行连接
  32.         ListNode node = new ListNode(data);
  33.         node.next = cur.next;
  34.         cur.next = node;
  35.     }
  36.     private void checkIndex(int index) throws IndexNotLegalException{
  37.         if(index < 0 || index > size()) {
  38.             throw new IndexNotLegalException("index不合法！");
  39.         }
  40.     }
  41.     private ListNode findIndexSubOne(int index) {
  42.         int count = 0;
  43.         ListNode cur = head;
  44.         while(count < index-1) {
  45.             cur = cur.next;
  46.             count++;
  47.         }
  48.         return cur;
  49.     }

查找关键字key是否包含在链表中

  1.     public boolean contains(int key) {
  2.         ListNode cur = head;
  3.         while(cur != null) {
  4.             if(cur.val == key) {
  5.                 return true;
  6.             }
  7.             cur = cur.next;
  8.         }
  9.         return false;
  10.     }

删除第一次出现关键字key的节点

  1.     public void remove(int key) {
  2.         //判空
  3.         if(head == null) {
  4.             return;
  5.         }
  6.         //若头节点为key
  7.         while(head.val == key) {
  8.             head = head.next;
  9.             return;
  10.         }
  11.         ListNode cur = head;
  12.         //遍历找到值为key的节点
  13.         while(cur.next != null) {
  14.             if(cur.next.val == key) {
  15.                 cur.next = cur.next.next;
  16.                 return;
  17.             }
  18.             cur = cur.next;
  19.         }
  20.         System.out.println("没有找到要删除的数字！");
  21.     }

删除所有值为key的节点

  1.     public void removeAllKey(int key) {
  2.         //判空
  3.         if (this.head == null) {
  4.             return;
  5.         }
  6.         //快慢指针
  7.         ListNode prev = head;
  8.         ListNode cur = head.next;
  9.         while(cur != null) {
  10.             if(cur.val == key) {
  11.                 prev.next = cur.next;
  12.             }else {
  13.                 prev = cur;
  14.             }
  15.             cur = cur.next;
  16.         }
  17.         //处理头节点，当上述操作完成后，只剩下头节点没有判断
  18.         //该方法优于一上来就判断头节点
  19.         if(head.val == key) {
  20.             head =head.next;
  21.         }
  22.     }

清空链表

  1.     public void clear() {
  2.         ListNode cur = head;
  3.         while(cur != null) {
  4.             ListNode curN = cur.next;
  5.             cur.next = null;
  6.             cur = curN;
  7.         }
  8.         head = null;
  9.     }

1.3 模拟实现无头双向非循环链表

  1. public class MyLinkedList {
  2.     static class ListNode {
  3.         public int data;
  4.         public ListNode prev;//前驱节点
  5.         public ListNode next;//后继节点
  6.  
  7.         public ListNode(int data){
  8.             this.data = data;
  9.         }
  10.     }
  11.  
  12.     public ListNode head;//头节点
  13.     public ListNode last;//尾节点
  14.  
  15.     //得到单链表的长度
  16.     public int size(){
  17.         int count = 0;
  18.         ListNode cur = head;
  19.         while(cur != null) {
  20.             count++;
  21.             cur = cur.next;
  22.         }
  23.         return count;
  24.     }
  25.     public void display(){
  26.         ListNode cur = head;
  27.         while(cur != null) {
  28.             System.out.print(cur.data + " ");
  29.             cur = cur.next;
  30.         }
  31.         System.out.println();
  32.     }
  33.     //查找是否包含关键字key是否在单链表当中
  34.     public boolean contains(int key){
  35.         ListNode cur = head;
  36.         while(cur != null) {
  37.             if(cur.data == key) {
  38.                 return true;
  39.             }
  40.             cur = cur.next;
  41.         }
  42.         return false;
  43.     }
  44.     //头插法
  45.     public void addFirst(int data){
  46.         ListNode node = new ListNode(data);
  47.         if(head == null) {
  48.             head = last = node;
  49.         }else {
  50.             head.prev = node;
  51.             node.next = head;
  52.             head = node;
  53.         }
  54.     }
  55.     //尾插法
  56.     public void addLast(int data){
  57.         ListNode node = new ListNode(data);
  58.         if(head == null) {
  59.             head = last = node;
  60.         }else {
  61.             last.next = node;
  62.             node.prev = last;
  63.             last = node;
  64.         }
  65.     }
  66.     //任意位置插入,第一个数据节点为0号下标
  67.     public void addIndex(int index,int data){
  68.         try{
  69.             checkIndex(index);
  70.         }catch(IndexIllegalException e) {
  71.             e.printStackTrace();
  72.         }
  73.         if(index == 0) {
  74.             addFirst(data);
  75.             return;
  76.         }
  77.         if(index == size()) {
  78.             addLast(data);
  79.             return;
  80.         }
  81.         ListNode node = new ListNode(data);
  82.         ListNode cur = findIndex(index);
  83.         node.next = cur;
  84.         node.prev = cur.prev;
  85.         cur.prev.next = node;
  86.         cur.prev = node;
  87.     }
  88.     private ListNode findIndex(int index) {
  89.         ListNode cur = head;
  90.         while(index != 0) {
  91.             cur = cur.next;
  92.             index--;
  93.         }
  94.         return cur;
  95.     }
  96.     private void checkIndex(int index) throws IndexIllegalException{
  97.         if(index < 0 || index > size()) {
  98.             throw new IndexIllegalException("双向链表index不合法！");
  99.         }
  100.     }
  101.  
  102.     //删除第一次出现关键字为key的节点
  103.     public void remove(int key){
  104.         ListNode cur = head;
  105.         while(cur != null) {
  106.             if(cur.data == key) {
  107.                 if(cur == head) {
  108.                     head = head.next;
  109.                     if(head != null) {
  110.                         head.prev = null;
  111.                     }else {
  112.                         last = null;
  113.                     }
  114.                 }else if(cur == last) {
  115.                     cur.prev.next = null;
  116.                     last = cur.prev;
  117.                 }else {
  118.                     cur.prev.next = cur.next;
  119.                     cur.next.prev = cur.prev;
  120.                 }
  121.                 return;
  122.  
  123.             }
  124.             cur = cur.next;
  125.         }
  126.     }
  127.     //删除所有值为key的节点
  128.     public void removeAllKey(int key){
  129.         ListNode cur = head;
  130.         while(cur != null) {
  131.             if(cur.data == key) {
  132.                 if(cur == head) {
  133.                     head = head.next;
  134.                     if(head != null) {
  135.                         head.prev = null;
  136.                     }else {
  137.                         last = null;
  138.                     }
  139.                 }else if(cur == last) {
  140.                     cur.prev.next = null;
  141.                     last = cur.prev;
  142.                 }else {
  143.                     cur.prev.next = cur.next;
  144.                     cur.next.prev = cur.prev;
  145.                 }
  146.             }
  147.             cur = cur.next;
  148.         }
  149.     }
  150.  
  151.     public void clear(){
  152.         ListNode cur = head.next;
  153.         while(cur != null) {
  154.             cur = head.next;
  155.             head.prev = null;
  156.             head.next = null;
  157.             head = cur;
  158.         }
  159.         head = last = null;
  160.     }
  161. }

链表遍历方式：

  1.     public static void main(String[] args) {
  2.         LinkedList<Integer> list = new LinkedList<>();
  3.         list.add(1);
  4.         list.add(2);
  5.         list.add(3);
  6.  
  7.         //直接sout打印
  8.         System.out.println(list);
  9.         System.out.println("======");
  10.  
  11.         //foreatch循环打印
  12.         for(Integer x : list) {
  13.             System.out.print(x + " ");
  14.         }
  15.         System.out.println();
  16.         System.out.println("======");
  17.  
  18.         //for循环打印
  19.         for (int i = 0; i < list.size(); i++) {
  20.             System.out.print(list.get(i) + " ");
  21.         }
  22.         System.out.println();
  23.         System.out.println("======");
  24.  
  25.         //Iterator打印
  26.         Iterator<Integer> it = list.iterator();
  27.         while(it.hasNext()) {
  28.             System.out.print(it.next() + " ");
  29.         }
  30.         System.out.println();
  31.         System.out.println("======");
  32.  
  33.         //ListIterator可以倒着打印
  34.         ListIterator<Integer> it3 = list.listIterator(list.size());
  35.         while(it3.hasPrevious()) {
  36.             System.out.print(it3.previous() + " ");
  37.         }
  38.     }

运行结果：

2、ArrayList 和 LinkedList 的区别

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

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

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

  

闽ICP备14008679号