世界杯预选赛亚洲区_高达世界杯 - fzxzyy.com

引言在深度的学习LinkedList之前，我们先来想一个问题。如果排队的逻辑，那我们怎么样可以实现?

首先我们想到的应该是ArrayList ，这是一个最常见的数据结构了。

那么ArrayList能实现吗？答案是可以的。

使用ArrayList可以非常容易就实现排队的逻辑。但是有一个问题存在。因为ArrayList的底层是一段连续内存空间。所以:

第一个问题：我们需要有一个大的空间来排序，对于排队来说，可能有时候火爆人特别多，可能有时候人特别少。那就涉及到扩容的一个问题。

第二个问题: 在排队期间，可能会有人临时有事需要离开，那么后面的人就需要向前进1，这样的话，如果说第二个人有事，那后面所有的人都需要向前进1，这样的话对于存储来说，就需要做大量的工作了，效率就相对很低下了。同样的对于有那些不要脸的人过来插队也是同样的，插队后续的人都需要向后退1，也是需要大量的工作量，同样效率低下。

所以对于 ArrayList来说，能实现队列，但是确不是最合适的，在插入和删除的场景下，效率很低。这也就引入了我们今天的主角：LinkedList 。

要了解LinkedList我们需要先了解一下，什么是链表。

链表链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。

上面是一个基础的概述哈。用实际的案例通俗点讲：

班主任今天对班级的学生进行一对一沟通对话，首先叫了张三，沟通完了后，跟张三说，你把李四叫过来一下。(为什么张三能直接叫到李四呢？因为张三知道李四坐在哪)。

也就是说。在链表中。每一个节点元素都会保存下一个节点的位置，这个位置就是指针。

每一个节点用Node表示，每一个Node对象中都至少包含了数据和指针。

同时，会有一个根节点指向第一个节点，这样的话是不是就可以根据这个根节点找到所有的节点了。

单链表单链表就是上面我们介绍的基础的链表。看上面这张图，就是一个单链表。其实我们理解字面意思也能明白，单链表就是单向链表。只能从前往后不能从后往前的链表。

双向链表当我们理解了单链表后，其实很容易理解双向链表。比如我们有时候需要从后面往前查多少位。这样只用单链表就不能实现了。因为后面的节点不知道前面节点的位置。那怎么办呢？

很简单，给每一个节点增加一个前指针(存前一个节点的位置)就可以了。只要我们知道位置就可以找到节点了。

这样的话：在整个链表中，一个头指针指向第一个节点，一个尾指针指向最后一个节点，那你想怎么找都可以找了。

如下图。

LinkedListLinkedList 就是基于双向循环链表来实现的，它针对ArrayList的两个弱项添加和删除来说，如何有改进呢？

试想一下，对于添加一个Temp来说，如果我们要插入在D点后面，那我们是不是只需要D点的后指针指向Temp即可，同时Temp的前指针指向D，后指针指向E。这样就实现了插入了。删除的原理一样。在插入和删除是不是不需要大量的动数据，只需要同关联的2个节点数据就可以了。

节点结构：LinkedList 内部定义了一个名为 Node 的静态内部类，用于表示链表中的节点。每个 Node 对象包含三个属性：

1、E item：存储节点的数据，E 是泛型类型参数，表示 LinkedList 可以存储任意类型的数据。

2、Node next：指向后一个节点的引用。

3、Node prev：指向前一个节点的引用。

双向循环特性LinkedList 的头节点（通过 first 属性引用）的 prev 指针指向尾节点，尾节点（通过 last 属性引用）的 next 指针指向头节点，形成一个循环结构。这样可以方便地从头节点或尾节点开始遍历整个链表。

添加元素：add(E e) 方法：在链表末尾添加元素。首先创建一个新的 Node 对象，将新节点的 item 设置为要添加的元素。然后，将新节点的 prev 指向原来的尾节点，将新节点的 next 指向头节点。接着，将原来的尾节点的 next 指向新节点，最后将尾节点引用更新为新节点。

addFirst(E e) 方法：在链表头部添加元素。创建新节点后，将新节点的 next 指向原来的头节点，将新节点的 prev 指向尾节点。然后，将原来的头节点的 prev 指向新节点，最后将头节点引用更新为新节点。

删除元素与添加元素原理类似

查找元素LinkedList 通过 get(int index) 方法来获取指定位置的元素。对于查找来说它没有很好的办法，只能对链表进行遍历。所以查找的时间复杂度是O(n).

一些小demo代码语言：txt复制import java.util.LinkedList;

public class LinkedListDemo {

public static void main(String[] args) {

// 创建一个LinkedList对象

LinkedList linkedList = new LinkedList<>();

// 添加元素

linkedList.add("Apple");

linkedList.add("Banana");

linkedList.add("Cherry");

System.out.println("After adding elements: " + linkedList);

// 在头部添加元素

linkedList.addFirst("Durian");

System.out.println("After adding an element at the beginning: " + linkedList);

// 获取元素

String secondElement = linkedList.get(1);

System.out.println("The second element is: " + secondElement);

// 删除元素

String removedElement = linkedList.removeFirst();

System.out.println("Removed the first element: " + removedElement);

System.out.println("LinkedList after removing the first element: " + linkedList);

// 遍历LinkedList

System.out.println("Traversing the LinkedList:");

for (String fruit : linkedList) {

System.out.println(fruit);

}

}

}

总结最后我在以一个日常生活中的例子来总结，防止上面的没太明白 。

我们以学生排队来说。

学生排队按从高到低排队，每一个学生都明确的知道自己前面的人(前指针)和后面的人(后指针)是谁。第一个学生则明确的知道自己这个队伍应该在哪个位置(也就是头指针)。

假如E今天请假了，则只需要D知道和F知道就ok.直接将D的后面的人变成F，F前面的人换成D就行。其他人则是不需要知道有变化。

假如班级有新同学E1，需要站在E的后面，那只需要E的后面（后指针）变成E1，F的前面的人(前指针)变成E1，而E1的前后指针分别指向E和F。这样整体就变化完成了。

这里着重说一下。链表的内存是不需要连续的。指针指向的人确定后，至于这个人在哪。是不需要关心的。