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

【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro_如果你需要频繁的在列表中插入或者删除元素,并且不关心随机访问的性能

作者：小惠珠哦 | 2024-08-17 06:42:02

赞

踩

如果你需要频繁的在列表中插入或者删除元素,并且不关心随机访问的性能

看到这句话的时候证明：此刻你我都在努力
加油陌生人
微信图片编辑_20240229212205.png

前言

今天给大家带来一篇有关Java顺序表和链表的文章，顺序表和链表我之前的专栏也是写过的，是用C语言实现的，也是模仿实现了顺序表和链表里的方法了。
下面是传送门：
顺序表：
你真的了解线性表中的顺序表了吗？（静态与动态顺序）-CSDN博客
链表：
数据结构对链表的初步认识（一）-CSDN博客
数据结构的带头，双向，循环链表来咯-CSDN博客
但是呢，学习了新语言Java那么就在用新语言在巩固一下了。

认识List

Java中的List是java.util包下的一个接口，它是Collection接口的一个子接口，表示一个有序的集合，可以包含重复的元素。List接口提供了一些独特的方法来插入、访问、删除元素以及搜索列表中的元素。以下是List接口的一些关键特性和常用实现：

特性
  1. 有序性：List中的元素按照添加的顺序进行排序。
  2. 允许重复：可以包含重复的元素。
  3. 动态数组：大多数List实现（如ArrayList）使用动态数组来存储元素，这使得随机访问非常高效。
常用方法
  • add(E e)：向列表末尾添加一个元素。
  • add(int index, E element)：在指定位置插入一个元素。
  • remove(int index)：移除指定位置的元素并返回被移除的元素。
  • remove(Object o)：移除列表中第一次出现的指定元素。
  • get(int index)：返回指定位置的元素。
  • set(int index, E element)：用指定元素替换列表中指定位置的元素。
  • size()：返回列表中的元素数量。
  • indexOf(Object o)：返回第一次出现的指定元素的索引。
  • lastIndexOf(Object o)：返回最后一次出现的指定元素的索引。
  • clear()：移除列表中的所有元素。
常用实现
  1. ArrayList：基于动态数组实现，支持快速随机访问。但插入和删除操作可能需要数组复制，效率较低。
  2. LinkedList：基于双向链表实现，适合频繁的插入和删除操作。但随机访问效率较低。
  3. Vector：和ArrayList类似，但它是同步的。
  4. Stack：继承自Vector，实现栈的功能，后进先出（LIFO）。
  5. CopyOnWriteArrayList：线程安全的变体，在读多写少的场景下性能较好。
泛型

从Java 5开始，List接口支持泛型，允许开发者指定列表中元素的类型，提高类型安全。

使用场景
  • 当你需要有序集合并且频繁进行随机访问时，选择ArrayList。
  • 当你需要频繁在列表中插入或删除元素，并且对随机访问的需求不高时，选择LinkedList。
注意事项
  • List的实现不是线程安全的。如果需要线程安全，可以使用Collections.synchronizedList()方法或CopyOnWriteArrayList。
  • 选择合适的List实现对于性能至关重要，因为不同的实现在不同的操作下表现不同。

List接口是Java集合框架中非常重要的一部分，合理选择和使用List可以提高程序的性能和可读性。

认识ArrayList（顺序表）

顺序表一个用数组实现的一个结构，他和数组不同的就是它是一个类，数组是一个引用类型，顺序表还扩展了一些方法
像增，删，查，改等是最基本的，还有一些其它方法，像List里的接口方法也实现了。
ArrayList是Java集合框架中的一种实现，属于List接口的实现类之一，同时也实现了RandomAccess接口，表明它支持快速的随机访问。

基本特性
  1. 基于数组：ArrayList内部使用一个动态数组（Object数组）来存储元素。
  2. 动态扩容：当添加元素导致数组容量不足时，ArrayList会自动扩容，通常是将现有容量增加到原来的1.5倍（或根据需要调整）。
  3. 允许空元素：可以包含null值。
  4. 非同步：ArrayList不是线程安全的。
性能特点
  1. 随机访问：由于基于数组实现，ArrayList提供了快速的随机访问能力，即get(int index)操作的时间复杂度为O(1)。
  2. 添加和删除：在列表末尾添加元素（add(E e)）是高效的，时间复杂度为O(1)。但是，如果需要在列表中间或开始位置添加或删除元素，可能需要移动其他元素以维持数组的连续性，这会导致时间复杂度为O(n)。
常用方法

代码演示：

import java.util.ArrayList;

public class T {

    public static void main(String[] args) {
        ArrayList<Integer> arrayList1=new ArrayList<>();  //创建一个存储整数的顺序表
        ArrayList<Character> arrayList2=new ArrayList<>();  //创建一个存储字符的顺序表
        ArrayList<String> arrayList3=new ArrayList<>();   //创建一个存储字符串的顺序表

        //给整形顺序表添加数据
        arrayList1.add(1);
        arrayList1.add(2);
        arrayList1.add(3);

        //给字符顺序表添加数据
        arrayList2.add('a');
        arrayList2.add('b');
        arrayList2.add('c');

        //给字符串顺序表添加数据
        arrayList3.add("abc");
        arrayList3.add("abcd");
        arrayList3.add("abcde");

        //分别打印三个顺序表
        System.out.println(arrayList1.toString());
        System.out.println(arrayList2.toString());
        System.out.println(arrayList3.toString());

        //也可以单独取其中的元素进行打印
        //如下取每个顺序表第一个元素进行打印
        System.out.println(arrayList1.get(0));
        System.out.println(arrayList2.get(0));
        System.out.println(arrayList3.get(0));


    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

image.png
注：使用ArrayList前需先导入对应的包 ：import java.util.ArrayList;

上面代码中我只是简单使用了其中的几个方法，但是顺序表即：ArrayList类还自带许多方法呢。
image.pngimage.png
这张图的方法仅仅只是ArrayList中2/3的方法呢，所以ArrayList功能还是很强大的。

顺序表之类的集合方法都有个非常厉害的功能，就是可以将另一个顺序表，一次性直接加入另一个顺序表。
代码演示：

public class T {
    public static void main(String[] args) {

        ArrayList<Integer> arrayList1=new ArrayList<>();
        ArrayList<Integer> arrayList2=new ArrayList<>();

        //给arrayList1添加数据
        arrayList1.add(1);
        arrayList1.add(2);
        arrayList1.add(3);

        //给arrayList2添加数据
        arrayList2.add(4);
        arrayList2.add(5);
        arrayList2.add(6);


        arrayList1.addAll(arrayList2);
        System.out.println(arrayList1.toString());
        

    }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

image.png
这样是否见识到ArrayList的强大呢。
除了继承自Collection和List接口的方法外，ArrayList还提供了一些特定方法：

  1. ensureCapacity(int minCapacity)：增加内部数组的容量至少为指定的最小容量，有助于减少扩容操作。
  2. trimToSize()：将内部数组的大小调整为当前元素的数量，释放多余的内存。
  3. 扩容机制

当ArrayList中的元素数量达到当前数组容量时，会进行扩容操作：

  1. 创建一个新的数组，容量为原数组的1.5倍（加上原数组容量）。
  2. 将原数组中的所有元素复制到新数组中。
  3. 用新数组替换原数组。
使用场景
  • 当你需要一个可以快速随机访问元素的集合时，ArrayList是一个好选择。
  • 当元素的添加主要集中在列表末尾时，ArrayList的性能较好。

认识LinkedList（链表）

链表也是一个实现了List的一个类。它的功能和ArrayList比较相似，不同的是LinkedList是没有扩容机制的。
且他们在某些地方插入数据的时间复杂度是不一样的。
LinkedList 在 Java 中是一种实现了 List 和 Deque 接口的双向链表。
基本特性
双向链表：LinkedList 中的每个元素都是一个节点，包含数据和两个指针，分别指向前一个和后一个节点。
动态数组：链表的长度可以根据需要动态增长或缩小。
非线程安全：LinkedList 默认不是线程安全的。如果需要线程安全，可以使用 Collections.synchronizedList() 方法或 CopyOnWriteArrayList。

内部结构
LinkedList 的内部结构由 Node 内部类实现，每个 Node 对象包含：
item：存储数据。
next：指向下一个节点的引用。
prev：指向前一个节点的引用。

性能特点
插入和删除：在列表的头部或尾部进行插入和删除操作非常高效（O(1)），因为不需要移动其他元素。在列表中间进行这些操作需要 O(n) 时间复杂度，因为需要遍历到特定位置。
随机访问：由于链表的非连续性，随机访问（通过索引获取元素）的时间复杂度为 O(n)，因为需要从头开始遍历链表。

常用方法

代码演示：

import java.util.LinkedList;

public class T {

    public static void main(String[] args) {
        LinkedList<Integer> linkedList1=new LinkedList<>();//创建一个存储整数的链表
        LinkedList<Character> linkedList2=new LinkedList<>();//创建一个存储字符的链表
        LinkedList<String> linkedList3=new LinkedList<>();//创建一个存储字符串的链表


        //给整形顺序表添加数据
        linkedList1.add(1);
        linkedList1.add(2);
        linkedList1.add(3);


        //给字符顺序表添加数据
        linkedList2.add('a');
        linkedList2.add('b');
        linkedList2.add('c');


        //给字符串顺序表添加数据
        linkedList3.add("abc");
        linkedList3.add("abcd");
        linkedList3.add("abcde");

        //分别打印三个顺序表
        System.out.println(linkedList1.toString());
        System.out.println(linkedList2.toString());
        System.out.println(linkedList3.toString());

        //也可以单独取其中的元素进行打印
        //如下取每个顺序表第一个元素进行打印
        System.out.println(linkedList1.get(0));
        System.out.println(linkedList2.get(0));
        System.out.println(linkedList3.get(0));

    }

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

image.png
链表也是支持addall（）方法的，也是可以将一个链表添加到另一个链表。

import java.util.LinkedList;

public class T {

    public static void main(String[] args) {
        LinkedList<Integer> linkedList1=new LinkedList<>();
        LinkedList<Integer> linkedList2=new LinkedList<>();


        linkedList1.add(1);
        linkedList1.add(2);
        linkedList1.add(3);

        linkedList2.add(4);
        linkedList2.add(5);
        linkedList2.add(6);

        linkedList1.addAll(linkedList2);

        System.out.println(linkedList1.toString());
    }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

image.png

除了继承自 List 的方法外，LinkedList 还提供了以下特有方法：

  1. addFirst(E e) 和 addLast(E e)：在链表头部和尾部添加元素。
  2. getFirst() 和 getLast()：获取链表头部和尾部的元素。
  3. removeFirst() 和 removeLast()：移除链表头部和尾部的元素。
  4. offerFirst(E e)、offerLast(E e)、pollFirst() 和 pollLast()：这些方法提供了双端队列的功能。
使用场景
  1. 当需要频繁地在列表的头部或尾部添加或删除元素时，LinkedList 是一个很好的选择。
  2. 当不需要频繁地进行随机访问时，LinkedList 可以提供比 ArrayList 更好的性能。

总结：

顺序表（如ArrayList）
  1. 基于数组：顺序表使用数组来存储元素，元素在内存中连续存放。
  2. 随机访问：支持快速的随机访问，即可以直接通过索引访问任意位置的元素（时间复杂度O(1)）。
  3. 动态扩容：当元素数量超过数组容量时，需要进行扩容操作，这通常涉及到创建更大的数组并复制现有元素。
  4. 插入和删除：在数组末尾添加元素非常快（时间复杂度O(1)），但在中间或开始位置插入或删除元素可能较慢，因为需要移动后续元素以维持连续性（时间复杂度O(n)）。
  5. 内存使用：通常比链表更紧凑，因为不需要额外存储指向其他元素的引用。
  6. 适用场景：适合于随机访问频繁的场景，以及在列表末尾添加元素的操作。
链表（如LinkedList）
  1. 基于节点：链表由一系列节点组成，每个节点包含数据和指向下一个（及前一个，对于双向链表）节点的指针。
  2. 非连续存储：元素在内存中可以是不连续的，通过指针连接。
  3. 动态大小：大小可以动态变化，不需要预先分配大量内存。
  4. 插入和删除：在已知前一个节点的情况下，可以在O(1)时间内完成，因为只需要改变几个指针。但在中间位置进行操作可能需要O(n)时间来找到前一个节点。
  5. 随机访问：不支持高效的随机访问，访问特定位置的元素需要从头开始遍历（时间复杂度O(n)）。
  6. 内存使用：每个节点需要额外存储至少一个（单向链表）或两个（双向链表）指针，因此内存使用相对较高。
  7. 适用场景：适合于插入和删除操作频繁的场景，尤其是在列表中间，以及不需要频繁随机访问元素的应用。

总结

  • 顺序表适合于需要快速随机访问元素的场景，以及主要在列表末尾添加元素的情况。
  • 链表适合于插入和删除操作频繁，尤其是在列表中间，且不经常进行随机访问的场景。

选择使用顺序表还是链表，取决于具体的应用需求和操作模式。理解它们的特点可以帮助开发者选择最合适的数据结构，以优化程序的性能。

. - 力扣（LeetCode）：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
. - 力扣（LeetCode）：逆置单链表
. - 力扣（LeetCode）：给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
. - 力扣（LeetCode）：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
. - 力扣（LeetCode）：合并两个有序链表
. - 力扣（LeetCode）：求环的路口
. - 力扣（LeetCode）：判断链表是否为环
. - 力扣（LeetCode）：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
链表的回文结构_牛客题霸_牛客网：判断链表是否回文

需要答案可私聊我，当然官方也有题解唔。

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

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

  

闽ICP备14008679号