深圳百度公司地址在哪里_网站建设方案选择实现方式_适合seo的网站_商丘网站seo

LinkedList 和 ArrayDeque

LinkedList
- LinkedList 详细介绍
- 基本用法
- 实现原理
- 总结
ArrayDeque

LinkedList

LinkedList 是 Java 集合框架中的一个类，它实现了 List 接口和 Deque（双端队列）接口。与 ArrayList 不同，LinkedList 使用双向链表来存储元素，这意味着每个元素（节点）都包含指向前后相邻元素的引用。这种结构使得 LinkedList 在插入和删除操作上通常比基于数组的 ArrayList 更高效，但在随机访问方面则不如后者。

LinkedList 详细介绍

概述
定义：LinkedList 是一个可以动态调整大小的双向链表实现，允许在列表两端快速添加或移除元素，并且支持按位置插入和删除。
特点：

线程不安全：与 ArrayList 类似，LinkedList 也不是同步的，多线程环境下需要额外的同步机制。
允许重复元素：可以包含多个相同的元素。
允许空值：支持存储 null 值，甚至可以存储多个 null。
双端队列功能：除了作为普通列表使用外，LinkedList 还提供了双端队列的功能，如在头部或尾部添加/移除元素。

内部工作原理
LinkedList 内部维护了一个双向链表的数据结构，其中每个节点（Node）包含三个部分：

元素本身（item）
前驱节点（prev）
后继节点（next）

源码如下：

    private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}

基本用法

    void addFirst(E e);void addLast(E e);E getFirst();E getLast();boolean offerFirst(E e);boolean offerLast(E e);E peekFirst();E peekLast();E pollFirst();E pollLast();E removeFirst();E removeLast();

实现原理

    transient int size = 0;/*** Pointer to first node.*/transient Node<E> first;/*** Pointer to last node.*/transient Node<E> last;

我们去看LinkedList的源码，我们会发现，LinkedList由三个成员变量，一个是size代表list由多少元素；一个是头节点，一个是尾节点。
而Node的本身定义相当于一个元素存储数据，一个存储前序节点，一个存储后序节点。

        LinkedList<Integer> linkedList = new LinkedList<>();linkedList.add(1);linkedList.add(2);linkedList.add(3);

示例图：
这段代码对应的底层node的示例如下：
在这里插入图片描述

总结

用法上，LinkedList是一个List，但也实现了Deque接口，可以作为队列、栈和双端队列使用。实现原理上，LinkedList内部是一个双向链表，并维护了长度、头节点和尾节点，这决定了它有如下特点。

自由分配空间
不支持随机访问
查找对应内容都需要遍历列表
在两端添加、删除元素的效率很高，时间复杂度为O(1)。
在中间插入、删除元素，要先找到修改的位置，查找的时间复杂度为O(N)，但修改本身的效率很高，效率为O(1)。

知道了LinkedList的底层实现，我们就知道，如果经常需要添加删除元素，且经常需要从两端操作，就可以考虑使用LinkedList。

ArrayDeque

我们上面介绍了LinkedList，它实现了Queue接口与Deque接口。还有一个ArrayDeque也实现了Deques接口而且底层使用数组实现的，我们知道deque需要操作两端的数据，按照之前的数组操作的话，会频繁引动数据，但是ArrayDeque的效率却非常高。我们简单介绍一下它的原理。

public class ArrayDeque<E> extends AbstractCollection<E>implements Deque<E>, Cloneable, Serializable{transient Object[] elements;transient int head;transient int tail;private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;}

我们打开它的源码，会发现它的成员变量有一个head，另一个tail。elements是实际存储元素的数组。那么为什么它对两端操作的效率就那么高呢？
因为它通过使用head和tail 把一个数组编程逻辑上的循环数组，而且数组的长度一般设置为2的整数次幂，方便进行位操作