Java 【数据结构】 LinkedList【神装】

 登神长阶 第二神装  LinkedList 

目录

🕶️一.LinkedList

🥼1.简介

 🦺2.LinkedList具体使用

👔2.1.构造方法

👕2.2.常见操作

👘2.3.遍历

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

🪖四.总结与反思

🕶️一.LinkedList

🥼1.简介

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

说明

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

注意

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

 🦺2.LinkedList具体使用

👔2.1.构造方法

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.常见操作

举例

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的优缺点的具体分析：

优点：

1. 高效的插入和删除操作： 由于LinkedList是双向链表，插入和删除元素的时间复杂度为O(1)，只需要修改相邻节点的指针，而不需要像数组那样移动元素。

2. 灵活性： LinkedList可以灵活地调整大小，而不像数组需要提前分配固定大小的内存空间。

3. 实现了多种接口： 除了List接口外，LinkedList还实现了Deque接口，因此可以用作队列或栈，支持先进先出（FIFO）和后进先出（LIFO）操作。

4. 无需连续的内存空间： 与数组不同，LinkedList的元素在内存中不需要连续的空间，这使得它更适合在内存分配方面较为有限的情况。

缺点：

1. 低效的随机访问： 要访问特定位置的元素，需要从链表的头部或尾部开始遍历，时间复杂度为O(n)，这使得LinkedList在随机访问元素时性能较差。

2. 占用更多的内存空间： 除了存储元素本身的空间外，每个节点还需要额外的空间来存储指向前后节点的指针，这使得LinkedList相比数组在存储相同数量的元素时占用更多的内存空间。

3. 缺乏数组的一些优点： 与数组相比，LinkedList不支持直接通过索引访问元素，也不能在常量时间内获取列表的大小，这在某些情况下可能会导致性能下降。

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

🪖三.总结与反思

💡努力是通往成功的钥匙，坚持是打开成功之门的手段。 ——奥巴马

        线性表的学习告一段落，我收获颇丰。

        学习了Java中的LinkedList，我深刻体会到了它作为一种数据结构的优缺点，以及在不同场景下的适用性。通过这次学习，我对链表这种数据结构有了更深入的理解，并从中汲取到了一些宝贵的经验和教训。

        首先，我认识到了LinkedList在插入和删除操作上的高效性。由于其采用了双向链表的结构，插入和删除元素的时间复杂度为O(1)，这使得它在需要频繁进行这些操作的场景下表现出色。与之相对比的是，对于ArrayList这种底层基于数组的实现，在插入和删除元素时需要移动大量元素，性能相对较低。

        其次，我也意识到了LinkedList在随机访问元素时的劣势。由于链表的特性，要访问特定位置的元素需要从头或尾开始遍历，时间复杂度为O(n)，这在大规模数据处理或需要频繁随机访问的场景下可能会导致性能下降。因此，在这些情况下，选择合适的数据结构显得尤为重要。

        另外，我也学会了如何灵活运用LinkedList。除了作为普通的列表外，它还可以用作队列或栈，支持先进先出和后进先出的操作，这使得它在不同的应用场景中都有着一定的灵活性。

        在反思这次学习的过程中，我意识到了数据结构的选择对程序性能和效率的影响是至关重要的。在实际开发中，需要根据具体的需求和场景选择合适的数据结构，不能一味追求某种数据结构的优势，而忽略了其劣势。同时，也要不断学习和积累经验，以便能够在面对不同的问题时做出更加明智的选择。

        综上所述，学习了Java中的LinkedList不仅增强了我的数据结构知识，还让我在实际编程中能够更加灵活地运用不同的数据结构，从而提高程序的性能和效率。这次学习不仅让我更加深入地了解了Java语言，也对编程能力的提升起到了积极的促进作用。

🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀

以上，就是本期的全部内容啦，若有错误疏忽希望各位大佬及时指出💐

  制作不易，希望能对各位提供微小的帮助，可否留下你免费的赞呢🌸