4.5 List 接口的实现类：LinkedList-Java语言基础10-Java中的集合

当前位置:　首页>> 技术小册>> Java语言基础10-Java中的集合

4.5.1 概述

- LinkedList 具备了 List 接口的特性（有序、重复、索引）。
- LinkedList 地城实现原理是双向链表。
- LinkedList 的增删速度快、查询慢。
- LinkedList 是线程不安全的集合，运行速度快。

4.5.2 LinkedList 集合特有方法

- 元素插入到链表开头：

```
public void addFirst(E e) {}
```
- 元素插入到列表结尾：

```
public void addLast(E e) {}
```
- 获取链表开头的元素：

```
public E getFirst() {}
```
- 获取链表结尾的元素：

```
public E getLast() {}
```
- 移除链表开头的元素：

```
public E removeFirst() {}
```
- 移除链表结尾的元素：

```
public E removeLast() {}
```
- 示例：

```
package com.github.linkedlist.demo1;

import java.util.LinkedList;

/**
 * @author maxiaoke.com
 * @version 1.0
 */
public class Test {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

linkedList.add("aa");
        linkedList.add("bb");
        linkedList.add("cc");
        linkedList.add("dd");

System.out.println("linkedList = " + linkedList); // linkedList = [aa, bb, cc, dd]

linkedList.addFirst("你好啊");

System.out.println("linkedList = " + linkedList); // linkedList = [你好啊, aa, bb, cc, dd]

linkedList.addLast("你好呢");

System.out.println("linkedList = " + linkedList); // linkedList = [你好啊, aa, bb, cc, dd, 你好呢]

System.out.println(linkedList.getFirst()); // 你好啊

System.out.println(linkedList.getLast()); // 你好呢

linkedList.removeFirst();

System.out.println("linkedList = " + linkedList); // linkedList = [aa, bb, cc, dd, 你好呢]

linkedList.removeLast();

System.out.println("linkedList = " + linkedList); // linkedList = [aa, bb, cc, dd]
    }
}
```
4.5.3 LinkedList 的类成员变量

- 集合中存储元素个数的计数器：

```
transient int size = 0;
```
- 第一个元素：

```
transient Node<E> first;
```
- 最后一个元素：

```
transient Node<E> last;
```
4.5.4 LinkedList 的成员内部类 Node
```
// 节点
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;
    }
}
```
4.5.5 LinkedList 类的 add 方法
```
public boolean add(E e) {
    linkLast(e);
    return true;
}
```

```
void linkLast(E e) {
    // 声明新的节点对象 = last
    final Node<E> l = last; // l = null
    // 创建新的节点对象
    final Node<E> newNode = new Node<>(l, e, null);
    // 新的节点赋值给最后一个节点
    last = newNode;
    if (l == null)
        // 将新的节点赋值给first
        first = newNode;
    else
        // 将新的节点赋值给最后一个节点的最后
        l.next = newNode;
    size++;
    modCount++;
}
```
4.5.6 LinkedList 类的 get 方法
```
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

```

```
Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}
```

该分类下的相关小册推荐：

Mybatis合辑2-Mybatis映射文件

Java高并发秒杀入门与实战

SpringBoot合辑-高级篇

java源码学习笔记

Java语言基础15-单元测试和日志技术

Java语言基础4-数组详解

Java面试指南

Java并发编程

Java语言基础3-流程控制

Java语言基础16-JDK8 新特性

Java语言基础7-Java中的异常

Mybatis合辑3-Mybatis动态SQL