美国世界杯_1978年世界杯 - gogolp.com

文章目录

LinkedList创建一个 `LinkedList`常用的 `LinkedList` 操作底层实现`Node` 类结构`LinkedList` 主要字段核心操作实现优缺点

LinkedList 是

java.util 包中的一个类，它实现了

List 接口，并且基于双向链表结构。与

ArrayList 不同，

LinkedList 适合在需要频繁插入和删除操作时使用，因为这些操作的时间复杂度为 O(1)。

LinkedList

创建一个 LinkedList

通过以下方式创建一个 LinkedList：

import java.util.LinkedList;

public class LinkedListExample {

public static void main(String[] args) {

// 创建一个 LinkedList

LinkedList list = new LinkedList<>();

// 添加元素

list.add("Apple");

list.add("Banana");

list.add("Cherry");

// 输出整个列表

System.out.println(list);

}

}

常用的 LinkedList 操作

添加元素:

add(E e)：将元素添加到链表的末尾。addFirst(E e)：将元素添加到链表的开头。addLast(E e)：将元素添加到链表的末尾。

LinkedList list = new LinkedList<>();

// 添加元素

list.add("Apple");

list.add("Banana");

list.add("Cherry");

// 在开头添加元素

list.addFirst("Mango");

// 在末尾添加元素

list.addLast("Grapes");

访问元素:

get(int index)：获取指定位置的元素。getFirst()：获取第一个元素。getLast()：获取最后一个元素。

LinkedList list = new LinkedList<>();

// 获取指定位置的元素

list.get(0);

// 获取第一个元素

list.getFirst();

// 获取最后一个元素

list.getLast();

删除元素:

remove()：删除并返回第一个元素。removeFirst()：删除并返回第一个元素。removeLast()：删除并返回最后一个元素。removeAt(int index)：删除指定位置的元素。

// 获取并删除第一个元素

String first = list.removeFirst();

System.out.println(first);

// 获取并删除最后一个元素

String last = list.removeLast();

System.out.println(last);

检查是否为空:

isEmpty()：检查链表是否为空。

// 检查链表是否为空

System.out.println(list.isEmpty());

其他常见方法:

size()：获取链表的大小。clear()：清空链表。

// 清空链表

list.clear()

// 获取链表的大小

System.out.println(list.size());

底层实现

LinkedList 类内部使用了一个双向链表结构，它包含了以下主要部分：

Node 类：每个节点包含 data（数据部分）、next（指向下一个节点的指针）、previous（指向前一个节点的指针）三个部分。头指针和尾指针：头指针用于指向链表的第一个节点，尾指针用于指向链表的最后一个节点。

Node 类结构

private static class Node {

E item;

Node next;

Node prev;

Node(Node prev, E element, Node next) {

this.item = element;

this.next = next;

this.prev = prev;

}

}

LinkedList 主要字段

private transient Node first; // 链表的头节点

private transient Node last; // 链表的尾节点

private transient int size = 0; // 链表的大小

first 和 last 分别指向链表的第一个和最后一个节点。size 保存链表的元素个数。

核心操作实现

添加元素（add 方法）

在链表的末尾添加元素：

创建一个新节点，并将其插入到尾节点之后。更新尾节点的 next 指针，指向新节点，并更新新节点的 previous 指针指向原尾节点。将 last 指针指向新节点。 public boolean add(E e) {

linkLast(e);

return true;

}

private void linkLast(E e) {

final Node l = last;

final Node newNode = new Node<>(l, e, null);

last = newNode;

if (l == null)

first = newNode;

else

l.next = newNode;

size++;

}

删除元素（remove 方法）

删除链表中的元素：

找到要删除的节点，调整前后节点的指针使得其不再指向该节点。更新头节点或尾节点（如果删除的是头节点或尾节点）。递减链表大小。 public E remove() {

return removeFirst();

}

public E removeFirst() {

final Node f = first;

if (f == null)

throw new NoSuchElementException();

final E element = f.item;

final Node next = f.next;

first = next;

if (next == null)

last = null;

else

next.previous = null;

f.item = null;

size--;

return element;

}

优缺点

优点：

插入和删除操作：在链表的头部或尾部插入或删除元素非常高效，时间复杂度为 O(1)。内存利用：由于链表不需要连续的内存空间，可以更好地利用内存，尤其是在内存碎片较多的情况下。 缺点：访问速度慢：链表的元素需要通过遍历来访问，因此访问某个元素的时间复杂度为 O(n)，相比数组的 O(1) 更慢。额外的内存消耗：每个节点除了存储数据，还需要存储 next 和 previous 指针，因此每个元素的内存消耗要比数组大。