Java 【数据结构】 LinkedList【神装】-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java 【数据结构】 LinkedList【神装】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Java 【数据结构】 LinkedList【神装】,【Java】登神长阶史诗般的Java成神之路,java,开发语言

登神长阶第二神装 LinkedList

🕶️一.LinkedList

🥼1.简介

🦺2.LinkedList具体使用

👔2.1.构造方法

👕2.2.常见操作

👘2.3.遍历

🧢三.LinkedList的优缺点与ArrayList的比较

🪖四.总结与反思

🕶️一.LinkedList

🥼1.简介

在集合框架中，LinkedList是一个普通的类，实现了List接口，具体框架图如下：

Java 【数据结构】 LinkedList【神装】,【Java】登神长阶史诗般的Java成神之路,java,开发语言

说明

LinkedList是Java中提供的双向链表实现的数据结构。它实现了List接口，因此可以像操作普通的列表一样对其进行操作，同时也支持队列和栈的操作。与ArrayList相比，LinkedList在插入和删除元素时具有更好的性能，因为它不需要移动其他元素。但是在访问特定位置的元素时，LinkedList的性能较差，因为需要从头或尾开始遍历链表。总的来说，LinkedList适合频繁进行插入和删除操作的场景。

注意

LinkedList实现了List接口
LinkedList的底层使用了双向链表
LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
LinkedList比较适合任意位置插入的场景

🦺2.LinkedList具体使用

👔2.1.构造方法

方法	解释
LinkedList()	无参构造
public LinkedList(Collection<? extends E> c)	利用其他 Collection 构建 LinkedList

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

👕2.2.常见操作

方法	解释
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

举例

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    list.add(1); // add(elem): 表示尾插
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);
    System.out.println(list.size());
    System.out.println(list);
    // 在起始位置插入0
    list.add(0, 0); // add(index, elem): 在index位置插入元素elem
    System.out.println(list);
    list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
    list.removeFirst(); // removeFirst(): 删除第一个元素
    list.removeLast(); // removeLast(): 删除最后元素
    list.remove(1); // remove(index): 删除index位置的元素
    System.out.println(list);
    // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
    if(!list.contains(1)){
        list.add(0, 1);
}
    list.add(1);
    System.out.println(list);
    System.out.println(list.indexOf(1)); /*indexOf(elem): 从前往
    后找到第一个elem的位置*/
    System.out.println(list.lastIndexOf(1)); /*lastIndexOf(elem): 从后
    往前找第一个1的位置*/
    int elem = list.get(0); // get(index): 获取指定位置元素
    list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
    System.out.println(list);
    /*subList(from, to): 用list中[from, to)之间
    的元素构造一个新的LinkedList返回*/
    List<Integer> copy = list.subList(0, 3); 
    System.out.println(list);
    System.out.println(copy);
    list.clear(); // 将list中元素清空
    System.out.println(list.size());
}

👘2.3.遍历

LinkedList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    list.add(1); // add(elem): 表示尾插
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);
    System.out.println(list.size());
    // foreach遍历
    for (int e:list) {
        System.out.print(e + " ");
    }
    System.out.println();
    // 使用迭代器遍历---正向遍历
    ListIterator<Integer> it = list.listIterator();
    while(it.hasNext()){
    System.out.print(it.next()+ " ");
    }
    System.out.println();
    // 使用反向迭代器---反向遍历
    ListIterator<Integer> rit = list.listIterator(list.size());
    while (rit.hasPrevious()){
    System.out.print(rit.previous() +" ");
    }
    System.out.println();
}

注意：

1. ArrayList最长使用的遍历方式是：for循环+下标以及 foreach

2. 迭代器是设计模式的一种，后序接触容器后再做详细讲解

🧢二.LinkedList的优缺点与ArrayList的比较

以下是对Java中LinkedList的优缺点的具体分析：

优点：

高效的插入和删除操作： 由于LinkedList是双向链表，插入和删除元素的时间复杂度为O(1)，只需要修改相邻节点的指针，而不需要像数组那样移动元素。
灵活性： LinkedList可以灵活地调整大小，而不像数组需要提前分配固定大小的内存空间。
实现了多种接口： 除了List接口外，LinkedList还实现了Deque接口，因此可以用作队列或栈，支持先进先出（FIFO）和后进先出（LIFO）操作。
无需连续的内存空间： 与数组不同，LinkedList的元素在内存中不需要连续的空间，这使得它更适合在内存分配方面较为有限的情况。

缺点：

低效的随机访问： 要访问特定位置的元素，需要从链表的头部或尾部开始遍历，时间复杂度为O(n)，这使得LinkedList在随机访问元素时性能较差。
占用更多的内存空间： 除了存储元素本身的空间外，每个节点还需要额外的空间来存储指向前后节点的指针，这使得LinkedList相比数组在存储相同数量的元素时占用更多的内存空间。
缺乏数组的一些优点： 与数组相比，LinkedList不支持直接通过索引访问元素，也不能在常量时间内获取列表的大小，这在某些情况下可能会导致性能下降。

综上所述，LinkedList适合于需要频繁执行插入和删除操作，而对随机访问性能要求不高的场景。在其他情况下，如需要频繁进行随机访问或需要节省内存空间时，可能更适合选择ArrayList或其他数据结构。

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