• 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 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 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 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)
    插入空间不够时需要扩容没有容量概念
    应用场景元素高效存储+频繁访问频繁在任意位置插入删除操作

  • 相关阅读:
    11 结构型模式- 代理模式
    【Linux operation 42】Linux 系统的时间
    IEDA refactor的用法
    【20221114】【每日一题】复原IP地址
    使用Webpack打包TS代码
    leetcode:126. 单词接龙 II
    Eolink征文活动---Eolink API文档服务的天才产品
    shell 学习笔记
    WSL2安装历程
    强化学习 补充笔记（TD算法、Q学习算法、SARSA算法、多步TD目标、经验回放、高估问题、对决网络、噪声网络）
  • 原文地址：https://blog.csdn.net/Yuan_o_/article/details/139603275