# Java集合之LinkedList

## 一、简介

LinkedList从名字就可以看出是用链表为数据结构实现的List，内部使用了一个双向链表，首先看一下LinkedList的Filed：

```java
transient int size = 0; //List的长度
transient Node<E> first; //指向头节点的指针
transient Node<E> last; //指向尾节点的指针
```

在LinkedList内部定义了链表节点的数据结构，很标准的双向链表数据结构，包含一个数据项，一个前驱节点，一个后驱节点。

```java
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;
    }
}
```

## 二、初始化

初始化很简单，啥也没做：

```java
public LinkedList() {
}
```

## 三、增加

因为是双向链表，所以可以头部和尾部都可以增加节点。

### 3.1 尾部增加add(E e)

```java
public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null); //创建一个节点，传入前驱，数据项和后驱
    last = newNode; //尾部添加，新节点就成了新的尾结点
    //将旧的尾结点的后驱指针指向新节点，如果是第一个节点就将头节点指向新节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
```

### 3.2 头部增加addFirst(E e)

```java
public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f); //创建一个节点，传入前驱，数据项和后驱
    first = newNode; //头部添加，新节点就成了新的头节点
    //将旧的头节点的前驱指针指向新节点，如果是第一个节点就将尾节点指向新节点
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
```

## 四、删除

删除分为删除头节点，删除尾结点和删除中间节点，实现类似，这里只说一下删除中间节点。、

```java
public E remove(int index) {
    //检查输入
    checkElementIndex(index);
    return unlink(node(index));
}

Node<E> node(int index) {
    //判断是正向查找还是反向查找，提高查询效率
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    //将节点从链表中移除
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}
```

## 五、查找

```java
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

//复用node方法
Node<E> node(int index) {

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
```

## 六、修改

```java
 public E set(int index, E element) {
     checkElementIndex(index);//校验
     Node<E> x = node(index);//查找
     E oldVal = x.item;
     x.item = element;//修改
     return oldVal;
 }
```

## 七、总结

因为使用了链表，增加和删除比ArrayList快，查找和修改比ArrayList慢。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jun-wang.gitbook.io/learnjava/ji-shu-xue-xi/java-xue-xi/java-ji-he-zhi-linkedlist.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.