• LinkedList与链表

    目录

    1.链表

    2.链表的模拟实现

    3.LinkedList的模拟实现

    4.LinkedList的使用

    4.1 什么是LinkedList

    4.2 LinkedList的使用

    5.ArrayList和LinkedList的区别

    我的GitHub：Powerveil · GitHub

    我的Gitee：Powercs12 (powercs12) - Gitee.com

    皮卡丘每天学Java

    1.链表

    链表也是线性表的一种。

    链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

    注意：

    1. 从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续

    2. 现实中的结点一般都是从堆上申请出来

    3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

    实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

    1. 单向或者双向

    2. 带头或者不带头

    3. 循环或者非循环 

    虽然有这么多的链表的结构，但是我们重点掌握两种:

    • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
    • 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

    2.链表的模拟实现

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

    3.LinkedList的模拟实现

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

    4.LinkedList的使用

    4.1 什么是LinkedList

    官方文档

    LinkedList (Java Platform SE 8 )

    LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

     下面是类图

    1. LinkedList实现了List接口
    2. LinkedList的底层使用了双向链表
    3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问

    注意：插入和删除的时间复杂度都为O(n)，因为找到节点需要遍历。

    4.2 LinkedList的使用

    LinkedList的构造

    方法解释
    LinkedList()无参构造
    public LinkedList(Collection c)使用其他集合容器中元素构造List
    1. @SuppressWarnings({"all"})
    2. public class Test {
    3.     public static void main(String[] args) {
    4.         // 构造一个空的LinkedList
    5.         LinkedList linkedList1 = new LinkedList<>();
    6.         List list = new ArrayList<>();
    7.  
    8.         list.add("Hello world!");
    9.         list.add("每天学Java");
    10.         list.add("逐渐提升");
    11.         list.add("...");
    12.         // 使用ArrayList构造LinkedList
    13.         LinkedList linkedList2 = new LinkedList<>(list);
    14.  
    15.     }
    16. }

    LinkedList的其他常用方法介绍

    方法解释
    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 lastIndexOf(Object o)返回最后一个 o 的下标
    List subList(int fromIndex, int toIndex)截取部分 list
    1.     public static void main(String[] args) {
    2.         LinkedList list = new LinkedList<>();
    3.         list.add(1); // add(elem): 表示尾插
    4.         list.add(2);
    5.         list.add(3);
    6.         list.add(4);
    7.         list.add(5);
    8.         list.add(6);
    9.         list.add(7);
    10.         System.out.println(list.size());
    11.         System.out.println(list);
    12.         // 在起始位置插入0
    13.         list.add(0, 0); // add(index, elem): 在index位置插入元素elem
    14.         System.out.println(list);
    15.         list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
    16.         list.removeFirst(); // removeFirst(): 删除第一个元素
    17.         list.removeLast(); // removeLast(): 删除最后元素
    18.         list.remove(1); // remove(index): 删除index位置的元素
    19.         System.out.println(list);
    20.         // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
    21.         if (!list.contains(1)) {
    22.             list.add(0, 1);
    23.         }
    24.         list.add(1);
    25.         System.out.println(list);
    26.         System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
    27.         System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
    28.         int elem = list.get(0); // get(index): 获取指定位置元素
    29.         list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
    30.         System.out.println(list);
    31.         // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
    32.         List copy = list.subList(0, 3);
    33.         System.out.println(list);
    34.         System.out.println(copy);
    35.         list.clear(); // 将list中元素清空
    36.         System.out.println(list.size());
    37.     }

    LinkedList的遍历

    1.     public static void main(String[] args) {
    2.         LinkedList list = new LinkedList<>();
    3.         list.add(1); // add(elem): 表示尾插
    4.         list.add(2);
    5.         list.add(3);
    6.         list.add(4);
    7.         list.add(5);
    8.         list.add(6);
    9.         list.add(7);
    10.         System.out.println(list.size());
    11.         // foreach遍历
    12.         for (int e:list) {
    13.             System.out.print(e + " ");
    14.         }
    15.         System.out.println();
    16.         // 使用迭代器遍历---正向遍历
    17.         ListIterator it = list.listIterator();
    18.         while(it.hasNext()){
    19.             System.out.print(it.next()+ " ");
    20.         }
    21.         System.out.println();
    22.         // 使用反向迭代器---反向遍历
    23.         ListIterator rit = list.listIterator(list.size());
    24.         while (rit.hasPrevious()){
    25.             System.out.print(rit.previous() +" ");
    26.         }
    27.         System.out.println();
    28.     }

    5.ArrayList和LinkedList的区别

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

  • 相关阅读:
    eclipse配置tomcat详解（图文版）
    重要功能丨支持1688API接口接入一键跨境铺货及采购，解决跨境卖家货源烦恼！
    【数据结构】顺序表
    微信内置浏览器调试和调试微信内的H5页面汇总（持续更新...)
    whois人员信息python批处理读入与文本输出
    升级ios16后iphone无法识别SIM？一招解决这个问题！
    [附源码]计算机毕业设计Springboot电影推荐网站
    Linux操作系统~系统文件IO，什么是文件描述符fd？什么是vfs虚拟文件系统
    全局变量和局部变量（static,extern,volatile）
    神经网络硕士就业前景,神经网络就业怎么样
  • 原文地址：https://blog.csdn.net/qq_63918780/article/details/127548914