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

【数据结构】链表与LinkedList

作者：Cpp五条 | 2024-02-25 03:44:05

赞

踩

【数据结构】链表与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<Integer> list = new LinkedList<>();

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

public LinkedList(Collection<? extends E> c)

栗子：

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

LinkedList的基本方法：

  1. public static void main(String[] args) {
  2. LinkedList<Integer> 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<Integer> 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<Integer> 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<Integer> it = list.listIterator();
  2.         while(it.hasNext()) {
  3.             System.out.println(it.next() + " ");
  4.         }
  5.     }

ArrayList与LinkedList的区别

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

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

  

闽ICP备14008679号