• 【数据结构】链表与LinkedList

    作者主页：paper jie 的博客

    本文作者：大家好，我是paper jie，感谢你阅读本文，欢迎一建三连哦。

    本文录入于《JAVA数据结构》专栏，本专栏是针对于大学生，编程小白精心打造的。笔者用重金(时间和精力)打造，将javaSE基础知识一网打尽，希望可以帮到读者们哦。

    其他专栏：《算法详解》《C语言》《javaSE》等

    内容分享：本期将会分享数据结构中的链表知识

    目录

    链表

    链表的概念与结构

    单向链表的模拟实现

    具体实现代码

    MyLinkedList

     indexillgality

    LinkedList

    LinkedList的模拟实现

    MyLinkedList

    Indexexception

    java中的LinkedList

    LinkedList的使用

    LinkedList的多种遍历

    ArrayList与LinkedList的区别

    链表

    链表的概念与结构

    链表是一种物理存储结构上非连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。大家可以把它理解为现实中的绿皮火车

    这里要注意：

    链式在逻辑上是连续的，但是在物理上不一定是连续的

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

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

    链表中的结构是多样的，根据情况来使用，一般使用一下结构：

    单向或双向

    带头和不带头

    循环和非循环

    这些结构中，我们需要重点掌握两种：

    无头单向非循环链表：结构简单，一般不会单独来存数据，实际上更多的是作为其他数据结构的子结构，如哈希桶，图的邻接表等。

    无头双向链表：在我们java的集合框架中LinkedList低层实现的就是无头双向循环链表。

    单向链表的模拟实现

    下面是单向链表需要实现的一些基本功能：

    1. // 1、无头单向非循环链表实现
    2. public class SingleLinkedList {
    3. //头插法
    4. public void addFirst(int data){
    5. } 
    6. //尾插法
    7. public void addLast(int data){
    8. } 
    9. //任意位置插入,第一个数据节点为0号下标
    10. public void addIndex(int index,int data){
    11. } 
    12. //查找是否包含关键字key是否在单链表当中
    13. public boolean contains(int key){
    14. return false;
    15. } 
    16. //删除第一次出现关键字为key的节点
    17. public void remove(int key){
    18. }
    19. //删除所有值为key的节点
    20. public void removeAllKey(int key){
    21. } 
    22. //得到单链表的长度
    23. public int size(){
    24. return -1;
    25. }
    26. public void clear() {
    27. }
    28. public void display() {}
    29. }

    具体实现代码

    MyLinkedList
    1. package myLinkedList;
    2.  
    3. import sun.awt.image.ImageWatched;
    4.  
    5. import java.util.List;
    6.  
    7. /**
    8.  * Created with IntelliJ IDEA.
    9.  * Description:
    10.  * User: sun杰
    11.  * Date: 2023-09-14
    12.  * Time: 10:38
    13.  */
    14. public class MyLinkedList implements IList{
    15.  
    16.     static class LinkNode {
    17.         public int value;
    18.         public LinkNode next;
    19.         public LinkNode(int data) {
    20.             this.value = data;
    21.         }
    22.     }
    23.     LinkNode head;
    24.     public void createNode() {
    25.         LinkNode linkNode1 = new LinkNode(12);
    26.         LinkNode linkNode2 = new LinkNode(23);
    27.         LinkNode linkNode3 = new LinkNode(34);
    28.         LinkNode linkNode4 = new LinkNode(56);
    29.         LinkNode linkNode5 = new LinkNode(78);
    30.         linkNode1.next = linkNode2;
    31.         linkNode2.next = linkNode3;
    32.         linkNode3.next = linkNode4;
    33.         linkNode4.next = linkNode5;
    34.         this.head = linkNode1;
    35.     }
    36.  
    37.  
    38.     @Override
    39.     public void addFirst(int data) {
    40.         //实例化一个节点
    41.         LinkNode firstNode = new LinkNode(data);
    42.         if(this.head == null) {
    43.             this.head = firstNode;
    44.             return;
    45.         }
    46.         //将原第一个对象的地址给新节点的next，也就是将head给新next
    47.         firstNode.next = this.head;
    48.         //将新的对象的地址给head头
    49.         this.head = firstNode;
    50.  
    51.     }
    52.  
    53.     @Override
    54.     public void addLast(int data) {
    55.         //实例化一个节点
    56.         LinkNode lastNode = new LinkNode(data);
    57.         //找到最后一个节点
    58.         LinkNode cur = this.head;
    59.         while(cur.next!= null) {
    60.             cur = cur.next;
    61.         }
    62.         cur.next = lastNode;
    63.         //将最后一个节点的next记录插入节点的地址
    64.     }
    65.  
    66.     @Override
    67.     public void addIndex(int index, int data) throws indexillgality {
    68.         if(index < 0 || index > size()) {
    69.             throw new indexillgality("index不合法");
    70.         }
    71.         LinkNode linkNode = new LinkNode(data);
    72.         if(this.head == null) {
    73.             addFirst(data);
    74.             return;
    75.         }
    76.         if(size() == index ) {
    77.             addLast(data);
    78.             return;
    79.         }
    80.         LinkNode cur = this.head;
    81.         int count = 0;
    82.         while(count != index - 1) {
    83.             cur = cur.next;
    84.             count++;
    85.         }
    86.         linkNode.next = cur.next;
    87.         cur.next = linkNode;
    88.     }
    89.  
    90.     @Override
    91.     public boolean contains(int key) {
    92.         LinkNode cur = this.head;
    93.         while(cur != null) {
    94.             if(cur.value == key) {
    95.                 return true;
    96.             }
    97.             cur = cur.next;
    98.         }
    99.         return false;
    100.  
    101.     }
    102.  
    103.     @Override
    104.     public void remove(int key) {
    105.         if(this.head.value == key) {
    106.             this.head = this.head.next;
    107.             return ;
    108.         }
    109.         //找前驱
    110.         LinkNode cur = findprev(key);
    111.         //判断返回值
    112.         if(cur != null) {
    113.             //删除
    114.             LinkNode del = cur.next;
    115.             cur.next = del.next;
    116.             //cur.next = cur.next.next;
    117.         }
    118.     }
    119.     //找删除的前驱
    120.     private LinkNode findprev(int key) {
    121.         LinkNode cur = head;
    122.             while(cur.next != null) {
    123.                 if(cur.next.value == key) {
    124.                     return cur;
    125.                 }
    126.                 cur = cur.next;
    127.             }
    128.         return null;
    129.     }
    130.  
    131.     @Override
    132.     public void removeAllKey(int key) {
    133.         if(size() == 0) {
    134.             return ;
    135.         }
    136.         if(head.value == key) {
    137.             head = head.next;
    138.         }
    139.         LinkNode cur = head.next;
    140.         LinkNode prev = head;
    141.         while(cur != null) {
    142.             if(cur.value == key) {
    143.                 prev.next = cur.next;
    144.             }
    145.             prev = cur;
    146.             cur = cur.next;
    147.         }
    148.  
    149.     }
    150.  
    151.     @Override
    152.     public int size() {
    153.         LinkNode cur = head;
    154.         int count = 0;
    155.         while(cur != null) {
    156.             count++;
    157.             cur = cur.next;
    158.         }
    159.         return count;
    160.     }
    161.  
    162.     @Override
    163.     public void display() {
    164.         LinkNode x = head;
    165.         while(x != null) {
    166.             System.out.print(x.value + " ");
    167.             x = x.next;
    168.         }
    169.         System.out.println();
    170.     }
    171.  
    172.     @Override
    173.     public void clear() {
    174.         LinkNode cur = head;
    175.         while(cur != null) {
    176.             LinkNode curNext = cur.next;
    177.             cur.next = null;
    178.             cur = curNext;
    179.         }
    180.         head = null;
    181.     }
    182. }
     indexillgality

    这时一个自定义异常

    1. package myLinkedList;
    2.  
    3. /**
    4.  * Created with IntelliJ IDEA.
    5.  * Description:
    6.  * User: sun杰
    7.  * Date: 2023-09-14
    8.  * Time: 12:55
    9.  */
    10. public class indexillgality extends RuntimeException {
    11.     public indexillgality(String message) {
    12.         super(message);
    13.     }
    14. }

    LinkedList

    LinkedList的模拟实现

    这相当于无头双向链表的实现，下面是它需要的基本功能：

    1. // 2、无头双向链表实现
    2. public class MyLinkedList {
    3. //头插法
    4. public void addFirst(int data){ }
    5. //尾插法
    6. public void addLast(int data){}
    7. //任意位置插入,第一个数据节点为0号下标
    8. public void addIndex(int index,int data){}
    9. //查找是否包含关键字key是否在单链表当中
    10. public boolean contains(int key){}
    11. //删除第一次出现关键字为key的节点
    12. public void remove(int key){}
    13. //删除所有值为key的节点
    14. public void removeAllKey(int key){}
    15. //得到单链表的长度
    16. public int size(){}
    17. public void display(){}
    18. public void clear(){}
    19. }

    MyLinkedList

    1. package myLinkedList;
    2.  
    3. import java.util.List;
    4.  
    5. /**
    6.  * Created with IntelliJ IDEA.
    7.  * Description:
    8.  * User: sun杰
    9.  * Date: 2023-09-20
    10.  * Time: 18:49
    11.  */
    12. public class MyLinkedList implements IList {
    13.  
    14.     //单个节点
    15.     public static class ListNode {
    16.         private int val;
    17.         private ListNode prev;
    18.         private ListNode next;
    19.  
    20.         public ListNode(int val) {
    21.             this.val = val;
    22.         }
    23.     }
    24.  
    25.     ListNode head;
    26.     ListNode last;
    27.     @Override
    28.     public void addFirst(int data) {
    29.         ListNode cur = new ListNode(data);
    30.         if(head == null) {
    31.             cur.next = head;
    32.             head = cur;
    33.             last = cur;
    34.         }else {
    35.             cur.next = head;
    36.             head.prev = cur;
    37.             head = cur;
    38.         }
    39.  
    40.     }
    41.  
    42.     @Override
    43.     public void addLast(int data) {
    44.         ListNode cur = new ListNode(data);
    45.         if(head == null) {
    46.             head = cur;
    47.             last = cur;
    48.         } else {
    49.             last.next = cur;
    50.             cur.prev = last;
    51.             last = cur;
    52.         }
    53.     }
    54.  
    55.     @Override
    56.     public void addIndex(int index, int data) throws Indexexception {
    57.         ListNode cur = new ListNode(data);
    58.         if(index < 0 || index > size()) {
    59.             throw new Indexexception("下标越界");
    60.         }
    61.  
    62.         //数组为空时
    63.         if(head == null) {
    64.             head = cur;
    65.             last = cur;
    66.             return ;
    67.         }
    68.  
    69.         //数组只有一个节点的时候
    70.         if(head.next == null || index == 0) {
    71.             head.prev = cur;
    72.             cur.next = head;
    73.             head = cur;
    74.             return;
    75.         }
    76.  
    77.         if(index == size()) {
    78.             last.next = cur;
    79.             cur.prev = last;
    80.             return ;
    81.         }
    82.  
    83.         //找到对应下标的节点
    84.         ListNode x = head;
    85.         while(index != 0) {
    86.             x = x.next;
    87.             index--;
    88.         }
    89.  
    90.         //头插法
    91.         cur.next = x;
    92.         cur.prev = x.prev;
    93.         x.prev.next = cur;
    94.         x.prev = cur;
    95.  
    96.     }
    97.  
    98.     @Override
    99.     public boolean contains(int key) {
    100.         ListNode cur = head;
    101.         while(cur != null) {
    102.             if(cur.val == key) {
    103.                 return true;
    104.             }
    105.             cur = cur.next;
    106.         }
    107.         return false;
    108.     }
    109.  
    110.     @Override
    111.     public void remove(int key) {
    112.         if(head == null) {
    113.             return;
    114.         }
    115.         ListNode cur = head;
    116.         while(cur != null) {
    117.             if(cur.val == key) {
    118.                 if(cur.next == null && cur.prev == null) {
    119.                     head = null;
    120.                     last = null;
    121.                     return;
    122.                 }else if(cur.next == null){
    123.                     cur.prev.next = null;
    124.                     last = cur.prev;
    125.                     return;
    126.                 }else if(cur.prev == null) {
    127.                     head = cur.next;
    128.                     cur.next.prev = null;
    129.                     return ;
    130.                 }else {
    131.                     ListNode frone = cur.prev;
    132.                     ListNode curnext = cur.next;
    133.                     frone.next = curnext;
    134.                     curnext.prev = frone;
    135.                     return ;
    136.                 }
    137.  
    138.             }
    139.             cur = cur.next;
    140.         }
    141.  
    142.     }
    143.  
    144.     @Override
    145.     public void removeAllKey(int key) {
    146.         if(head == null) {
    147.             return;
    148.         }
    149.         ListNode cur = head;
    150.         while(cur != null) {
    151.             if(cur.val == key) {
    152.                 if(cur.next == null && cur.prev == null) {
    153.                     head = null;
    154.                     last = null;
    155.                 } else if(cur.next == null){
    156.                     cur.prev.next = null;
    157.                     last = cur.prev;
    158.                 }else if(cur.prev == null) {
    159.                     head = cur.next;
    160.                     cur.next.prev = null;
    161.  
    162.                 }else {
    163.                     ListNode frone = cur.prev;
    164.                     ListNode curnext = cur.next;
    165.                     frone.next = curnext;
    166.                     curnext.prev = frone;
    167.                 }
    168.             }
    169.             cur = cur.next;
    170.         }
    171.  
    172.     }
    173.  
    174.     @Override
    175.     public int size() {
    176.         int count = 0;
    177.         ListNode cur = head;
    178.         while(cur != null) {
    179.             count++;
    180.             cur = cur.next;
    181.         }
    182.         return count;
    183.     }
    184.  
    185.     @Override
    186.     public void display() {
    187.         ListNode cur = head;
    188.         while(cur != null) {
    189.             System.out.print(cur.val + " ");
    190.             cur = cur.next;
    191.         }
    192.         System.out.println();
    193.     }
    194.  
    195.     @Override
    196.     public void clear() {
    197.         if(head == null) {
    198.             return;
    199.         }
    200.         ListNode cur = head.next;
    201.         while(cur != null) {
    202.             head = null;
    203.             head = cur;
    204.             cur = cur.next;
    205.         }
    206.         head = null;
    207.     }
    208. }

    Indexexception

    这也是一个自定义异常

    1. package myLinkedList;
    2.  
    3. /**
    4.  * Created with IntelliJ IDEA.
    5.  * Description:
    6.  * User: sun杰
    7.  * Date: 2023-09-21
    8.  * Time: 9:47
    9.  */
    10. public class Indexexception extends RuntimeException{
    11.     public Indexexception(String message) {
    12.         super(message);
    13.     }
    14. }

    java中的LinkedList

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

    在集合框架中，LinkedList也实现了List接口：

    注意：

    LinkedList实现了List接口

    LinkedList的底层使用的是双向链表

    Linked没有实现RandomAccess接口，因此LinkedList不支持随机访问

    LinkedList的随机位置插入和删除元素时效率较高，复杂度为O(1)

    LinkedList比较适合任意位置插入的场景

    LinkedList的使用

    LinkedList的构造：

    一般来说有两种方法：

    无参构造：

    List list = new LinkedList<>();

    使用其他集合容器中的元素构造List：

    public LinkedList(Collection c)

    栗子：

    1. public static void main(String[] args) {
    2. // 构造一个空的LinkedList
    3.         List list1 = new LinkedList<>();
    4.         List list2 = new java.util.ArrayList<>();
    5.         list2.add("JavaSE");
    6.         list2.add("JavaWeb");
    7.         list2.add("JavaEE");
    8. // 使用ArrayList构造LinkedList
    9.         List list3 = new LinkedList<>(list2);
    10.     }

    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. 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的多种遍历

    foreach：

    1. public static void main(String[] args) {
    2.         List list = new LinkedList<>();
    3.         list.add(1);
    4.         list.add(3);
    5.         list.add(5);
    6.         list.add(2);
    7.         list.remove(1);
    8.         for (int x:list) {
    9.             System.out.print(x + " ");
    10.         }
    11.     }

    使用迭代器遍历：

    1. ListIterator it = list.listIterator();
    2.         while(it.hasNext()) {
    3.             System.out.println(it.next() + " ");
    4.         }
    5.     }

    ArrayList与LinkedList的区别

  • 相关阅读:
    19. 删除链表的倒数第 N 个结点 C++（快慢指针）
    (D卷,100分)- 最富裕的小家庭（Java & JS & Python & C）
    【行业动态】福建服装品牌如何完成差异化战略？
    13、文本框和单选框
    记录：移动设备软件开发（Android项目组织结构）
    【iOS 16升级必备】如何备份iPhone数据？
    动态分配的内存位置在哪里？
    Spring Boot-2.3.7.RELEASE整合activiti-6.0示例步骤
    Grafana离线安装部署以及插件安装
    MFC Windows 程序设计[152]之耍酷滑动滚动条
  • 原文地址：https://blog.csdn.net/paperjie/article/details/133240159