LinkedList类

• 链表结构实现，增删快，查询慢。

1. LinkedList

LinkedList<Student> linkedList = new LinkedList<>();
Student s1 = new Student("唐", 21);
Student s2 = new Student("何", 22);
Student s3 = new Student("余", 21);
// 1.添加元素
linkedList.add(s1);
linkedList.add(s2);
linkedList.add(s3);
linkedList.add(s3);
System.out.println("元素个数：" + linkedList.size());
System.out.println(linkedList.toString());
// 2.删除元素
/*
         * linkedList.remove(new Student("唐", 21));
         * System.out.println(linkedList.toString());
         */
// 3.遍历
// 3.1 使用for
for (int i = 0; i < linkedList.size(); ++i) {
  System.out.println(linkedList.get(i));
}
//3.2 使用增强for
for (Student student : linkedList) {
  System.out.println(student.toString());
}
// 3.3 使用迭代器
Iterator<Student> iterator = linkedList.iterator();
while (iterator.hasNext()) {
  System.out.println(iterator.toString());
}
// 3.4 使用列表迭代器（略）
// 4. 判断
System.out.println(linkedList.contains(s1));
System.out.println(linkedList.isEmpty());
System.out.println(linkedList.indexOf(s3));

2. LinkedList源码分析

LinkedList首先有三个属性：

• 链表大小：transient int size = 0;
• （指向）第一个结点/头结点：transient Node<E> first;
• （指向）最后一个结点/尾结点：transient Node<E> last;

关于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;
    }
}

首先item存放的是实际数据；next指向下一个结点而prev指向上一个结点。

Node带参构造方法的三个参数分别是前一个结点、存储的数据、后一个结点，调用这个构造方法时将它们赋值给当前对象。

LinkedList是如何添加元素的呢？先看看add方法：

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

进入到linkLast方法：

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++;
}