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

【数据结构】LinkedList与链表_headlist和linkedlist

作者：羊村懒王 | 2024-06-16 10:16:13

赞

踩

headlist和linkedlist

 【引言】

  • 上篇文章我们介绍了ArrayList的使用以及它的一些相关知识，还模拟实现了简单的顺序表
  • 我们在这个过程中，有了以下的思考：ArrayList的底层是使用数组来存储元素的
  • 这就导致当ArrayList的任意位置插入或删除元素时，就需要将后续元素整体向后移或者向前移，所以时间复杂度为O(N)
  • 因此ArrayList不适合做任意位置插入和删除比较多的场景
  • 所以，Java集合中又引入了LinkedList，即链表结构

目录

1.链表

1.1链表的概念和结构

 1.2单向非循环链表实现

单向非循环链表实现过程的分析 

1.创建链表

 2.如何遍历链表

3.头插

4.尾插

 5.任意位置插入

6.删除 

7.删除所有值为key的节点 

2.LinkedList的模拟实现

3.LinkedList的使用

3.1LinkedList的简单介绍 

3.2LinkedList的使用 

1.LinkedList的构造 

2.LinkedList的一些常用方法

3.LinkedList的遍历

4.LinkedList和ArrayList的区别

 

目录

1.链表

1.1链表的概念和结构

 1.2单向非循环链表实现

单向非循环链表实现过程的分析 

1.创建链表

 2.如何遍历链表

3.头插

4.尾插

5.任意位置插入

6.删除 

7.删除所有值为key的节点 

2.LinkedList的模拟实现

3.LinkedList的使用

3.1LinkedList的简单介绍 

3.2LinkedList的使用 

1.LinkedList的构造 

2.LinkedList的一些常用方法

3.LinkedList的遍历

4.LinkedList和ArrayList的区别

1.链表

1.1链表的概念和结构

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

 实际中链表的结构非常多样，有单向和双向、带头和不带头、循环和非循环

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

以上情况组合起来，就有8种链表结构

下面我们看一张图

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。这种结构在笔试面试中出现很多。
 

另一个用得较多的是无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表
 

下面我们介绍一下链表是如何实现的

首先简要介绍一下节点的概念

 如图便是一个简单的节点的示意图，它有两个域：数值域和next域

 1.2单向非循环链表实现

我们要实现哪些功能呢？

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

先看一下整体的代码  

  1. package listdemo;
  2.  
  3. public class MySingleList {
  4.     //节点是链表的一个组成部分，一般情况下把节点作为内部类
  5.     static class ListNode{
  6.         public int val;//数值域
  7.         public ListNode next;//存储下一个节点的地址
  8.  
  9.         public ListNode(int val) {
  10.             this.val = val;
  11.         }
  12.     }
  13.     public ListNode head;//代表单链表的头节点的引用
  14.     /**
  15.      * 这里只是简单的进行链表的构造
  16.      */
  17.     public void createList(){
  18.         ListNode listNode1 = new ListNode(12);
  19.         ListNode listNode2 = new ListNode(23);
  20.         ListNode listNode3 = new ListNode(34);
  21.         ListNode listNode4 = new ListNode(45);
  22.         ListNode listNode5 = new ListNode(56);
  23.  
  24.         listNode1.next = listNode2;
  25.         listNode2.next = listNode3;
  26.         listNode3.next = listNode4;
  27.         listNode4.next = listNode5;
  28.  
  29.         this.head = listNode1;
  30.     }
  31.     public void display() {
  32.         ListNode cur = head;
  33.         while(cur != null){
  34.             System.out.print(cur.val+" ");
  35.             cur = cur.next;
  36.         }
  37.         System.out.println();
  38.     }
  39.  
  40.     /**
  41.      *头插法
  42.      * @param data
  43.      */
  44.     public void addFirst(int data){
  45.          ListNode node = new ListNode(data);
  46.          if(this.head == null){
  47.              this.head =node;
  48.          }else{
  49.              node.next = this.head;
  50.              this.head = node;
  51.          }
  52.         /*可以直接这样写
  53.         node.next = this.head;
  54.         this.head = node;*/
  55.     }
  56.     //尾插法
  57.     public void addLast(int data){
  58.         ListNode node = new ListNode(data);
  59.         if(this.head == null){
  60.             this.head = node;
  61.         }else{
  62.             ListNode cur = head;
  63.             while(cur.next != null){
  64.                 cur = cur.next;
  65.             }
  66.  
  67.             //cur.next==null时
  68.             cur.next = node;
  69.         }
  70.  
  71.     }
  72.     private void checkIndexAdd(int index){
  73.         if(index<0 || index>size()){
  74.             throw new MySingleListIndexOutOfException("任意插入位置的时候index不合法");
  75.         }
  76.     }
  77.  
  78.     /**
  79.      * 找到index位置的前一个位置处的节点
  80.      * @param index
  81.      * @return 该节点的地址
  82.      */
  83.     private ListNode findIndexSubOne(int index){
  84.         ListNode cur = this.head;
  85.         int count = index-1;
  86.         while(count!=0){
  87.             cur = cur.next;
  88.             count--;
  89.         }
  90.         return cur;
  91.     }
  92.  
  93.     /**
  94.      * 任意位置插入,第一个数据节点为0号下标
  95.      * @param index
  96.      * @param data
  97.      */
  98.     public void addIndex(int index,int data) throws MySingleListIndexOutOfException {
  99.         checkIndexAdd(index);
  100.         if(index == 0){
  101.             addFirst(data);//头插法
  102.             return ;
  103.         }
  104.         if(index == size()){
  105.             addLast(data);//尾插法
  106.             return;
  107.         }
  108.         ListNode node = new ListNode(data);
  109.         ListNode cur = findIndexSubOne(index);//找到index位置的前一个节点，记为cur
  110.         //插入
  111.         node.next = cur.next;
  112.         cur.next = node;
  113.     }
  114.  
  115.     //查找是否包含关键字key在单链表当中
  116.     public boolean contains(int key){
  117.         ListNode cur = this.head;
  118.         while(cur != null){
  119.             if(cur.val == key){
  120.                 return true;
  121.             }
  122.             cur = cur.next;
  123.         }
  124.         return false;
  125.     }
  126.  
  127.     /**
  128.      * 删除第一次出现关键字为key的节点
  129.      * @param key
  130.      */
  131.     public void remove(int key){
  132.         if(this.head == null){
  133.             System.out.println("此时链表为空，不能进行删除");
  134.             return ;
  135.         }
  136.         if(this.head.val == key){//判断第一个节点是不是我要删除的节点
  137.             this.head = this.head.next;
  138.             return ;
  139.         }
  140.         ListNode cur = this.head;
  141.         while(cur.next != null){
  142.             if(cur.next.val == key){
  143.                 //进行删除
  144.                 ListNode del = cur.next;
  145.                 cur.next = del.next;
  146.                 return ;
  147.             }
  148.             cur = cur.next;
  149.         }
  150.  
  151.     }
  152.  
  153.     /**
  154.      * 删除所有值为key的节点
  155.      * 1.要求时间复杂度为 O(N)
  156.      * 2.要求只遍历单链表一遍
  157.       * @param key
  158.      */
  159.     public void removeAllKey(int key){
  160.         //先判断 head 是否为空
  161.         if(this.head == null){
  162.             return ;
  163.         }
  164.         ListNode cur = this.head.next;
  165.         ListNode prev = this.head;
  166.  
  167.         while(cur != null){
  168.             if(cur.val == key){
  169.                 prev.next = cur.next;
  170.                 cur = cur.next;
  171.             }else{
  172.                 prev = cur;
  173.                 cur = cur.next;
  174.             }
  175.         }
  176.  
  177.         //单独处理头节点问题
  178.         if(this.head.val == key){
  179.             this.head = head.next;
  180.         }
  181.     }
  182.     //得到单链表的长度
  183.     public int size(){
  184.         int count = 0;
  185.         ListNode cur = this.head;
  186.         while(cur != null){
  187.             count++;
  188.             cur = cur.next;
  189.         }
  190.         return  count;
  191.     }
  192.  
  193.     /**
  194.      * 清空链表所有内容
  195.      * 当我们调用clear函数的时候，会将这个链表当中的所有的节点回收
  196.      */
  197.     public void clear(){
  198.         //做法一，简单粗暴
  199.         //this.head = null;
  200.  
  201.         //做法二，一个一个删除
  202.         ListNode cur = this.head;
  203.         ListNode curNext = null;
  204.         while(cur != null){
  205.             curNext = cur.next;
  206.             cur.next = null;
  207.             cur = curNext;
  208.         }
  209.         head = null;
  210.     }
  211. }

单向非循环链表实现过程的分析 

1.创建链表

注意：这只是简单意义上的创建链表 

 2.如何遍历链表

3.头插

4.尾插

 5.任意位置插入

6.删除 

一些问题

测试：

7.删除所有值为key的节点 

我们的要求是：

1.时间复杂度为 O(N)

2.最多遍历单链表一遍

首先我们需要清楚，这个删除的核心是：要找到需要删除的节点的上一个节点 

 由于在一开始就处理头节点就需要删除的特殊情况比较困难，所以我们最后再处理

  注：如果我们一开始就处理头节点的问题，那么我们需要用循环语句，直到头节点的值不等于key循环才停止，但是如果我们最后再处理头节点的问题，只需要一个 if 语句判断一下即可 

2.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 boolean 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. }

 下面我们来模拟实现一下

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

3.LinkedList的使用

3.1LinkedList的简单介绍 

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

想了解LinkedList的官方文档，点我！！

 这是LinkedList的部分源码

下面我们通过一张图加深一下对LinkedList的了解吧 

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

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

3.2LinkedList的使用 

1.LinkedList的构造 

方法解释
LinkedList()无参构造
public LinkedList(Collection<? extends E> c)使用其他集合容器中元素构造List

我们看一个例子

  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. }

2.LinkedList的一些常用方法

方法解释
boolean add(E e)尾插 e
void add(int index, E element)将 e 插入到 index 位置
boolean addAll(Collection<? extends E> 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<E> subList(int fromIndex, int toIndex)截取部分 list

几个注意事项：

add

 我们通过源码可以知道，add默认是用的尾插

3.LinkedList的遍历

我们以 LinkedList里放的是Int类型为例

  1.     public static void main(String[] args) {
  2.         LinkedList<Integer> linkedList = new LinkedList<>();
  3.         linkedList.add(1);
  4.         linkedList.add(2);
  5.         linkedList.add(3);
  6.         linkedList.add(4);
  7.         //for-each 遍历
  8.         for (int x:linkedList) {
  9.             System.out.print(x+" ");
  10.         }
  11.         System.out.println();
  12.         System.out.println("=================");
  13.         //使用迭代器遍历 1
  14.         Iterator<Integer> it = linkedList.iterator();
  15.         while(it.hasNext()){
  16.             System.out.print(it.next()+" ");
  17.             // it.next() 不仅会打印下一个 还会让it向后走一步
  18.         }
  19.         System.out.println();
  20.         System.out.println("==================");
  21.         //使用迭代器遍历 2
  22.         ListIterator<Integer> listIterator = linkedList.listIterator();
  23.         while (listIterator.hasNext()){
  24.             System.out.print(listIterator.next()+" ");
  25.         }
  26.         System.out.println();
  27.         System.out.println("===================");;
  28.  
  29.         //使用迭代器遍历（反向遍历）
  30.         ListIterator<Integer> listIterator1 = linkedList.listIterator(linkedList.size());
  31.         while(listIterator1.hasPrevious()){
  32.             System.out.print(listIterator1.previous()+" ");
  33.         }
  34.         System.out.println();
  35.     }

4.LinkedList和ArrayList的区别

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

我们简单来概括下：

1.存储方式上的不同：

ArrayList  是一块连续的内存，物理上和逻辑上都连续

LinkedList  物理上不一定连续，逻辑上是连续的

2.增删查改的区别

增加元素、删除元素比较频繁时，建议使用LinkedList，只需要修改指向就可以

如果要频繁地查找下标、修改，建议使用ArrayList


 


 

    

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

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

  

闽ICP备14008679号