jdk链表笔记

LinkedList

LinkedList是双链表，并且有头尾指针

 

数据结构

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable
{
    transient int size = 0;
    transient Node first;
    transient Node last;
    public LinkedList() {
    }

他持有头节点和未节点，并且初始的时候，这两个节点都为null

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

这是节点的结构，有一个数据域和前后指针

功能实现

1.随机访问的优化node(index)

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

该方法是随机访问的基础实现，用于获取根据下标获取节点，亮点在于，先判断index是size的前半段还是后半段，来决定是用头节点遍历还是为节点来遍历,这样会提高随机访问的效率

2.要有解除引用的习惯

unlinkFirst、unlinkLast、unlink、clear，这种删除节点的方法，都会把该节点的所有引用以及其他对象对该节点的引用都设为null，这样可以help gc

    E unlink(Node x) {
        // assert x != null;
        final E element = x.item;
        final Node next = x.next;
        final Node 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;
    }

我非常喜欢这个方法，他非常灵活，他是remove操作的基础实现，他的亮点在于最大限度的help gc，减小了内存的损耗。在有些数据结构的书中，remove完，没有把相关舍弃的引用设为null，这给gc加大了难度

3.只在迭代器中持有游标

4.hasNext和next

习惯上，人们会先调用hasNext()，再调用next()，但是jdk中对于next()中的实现，也会调用一次hasNext()，如果false则会抛出NoSuchElementException,防止被意外调用（因为这个方法暴露了）

5.迭代器中remove和set是对最后一个从迭代器返回的元素进行操作

6.针对foreach

凡事实现了Iterator都可以使用foreach语句

因为foreach进过jvm编译了之后，其实就是调用了Iterator的hasNext()和next()

那么为什么foreach只能改变引用不能改变值呢？

因为next()返回的是一个Node中的数据域，而不是Node

7.toArray(T[] a)

如果a的容量不够的话，会创建一个泛型数组

具体方法：

    @SuppressWarnings("unchecked")
    public  T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (Node x = first; x != null; x = x.next)
            result[i++] = x.item;
        if (a.length > size)
            a[size] = null;
        return a;
    }

查看原文：http://blog.zswlib.com/2016/10/26/jdk%e4%b8%ad%e9%93%be%e8%a1%a8%e7%ac%94%e8%ae%b0/