LinkList相关学习

介绍

LinkList也是工作中常见的集合, 底层使用双向链表结构
比较适合新增和删除, 查询和修改需要遍历相对ArrayList比较消耗性能

内部类 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;
    }
}

add 新增

通过代码可以看出, 在新增元素时只需要创建一个新节点 Node, 并将原始链表最后一个Node的next指向新Node

public boolean add(E e) {
    linkLast(e);
    return true;
}
/**
 * Links e as last element.
 */
void linkLast(E e) {
    // 声明 l 为最后一个节点
    final Node<E> l = last;
    // 创建新节点, 指向上一个节点, 下一个节点为空
    final Node<E> newNode = new Node<>(l, e, null);
    // 最后一个节点为新创建的节点
    last = newNode;
    // 判断是否为第一个元素, 否则将 新创建的 Node加入链表
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

remove 删除

1.删除操作需要遍历链表找到相应元素, 然后移动指针即可
2.删除首尾元素直接移动指针即可 removeFirst()/removeLast() 方法

public boolean remove(Object o) {
    if (o == null) {
        // 遍历链表
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

/**
 * 删除元素
 */
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    // 判断上一个Node是否为空
    if (prev == null) {
        // 空, 该节点为链表头, 将下一个节点设置为链表头
        first = next;
    } else {
        // 不为空, 将上一个节点的next 指向当前节点的 next, 并将当前节点的 prev置为空
        prev.next = next;
        x.prev = null;
    }
    // 判断下一个Node是否为空
    if (next == null) {
        // 空, 该节点为链表尾, 将链表尾设置为当前节点的上一个节点
        last = prev;
    } else {
        // 不为空, 将下一个节点的prev, 设置为上一个节点, 并将当前节点的 next置为空
        next.prev = prev;
        x.next = null;
    }

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

get/set

get/set时都需要获取指定索引的元素, 使用二分法查找, 然后进行遍历查找, 所以此处相较于ArrayList多了遍历查询, 虽然使用了二分法进行优化, 但是get/set操作相比ArrayList来说性能还是相对较差

public E get(int index) {
    // 校验索引
    checkElementIndex(index);
    // 二分法遍历查找节点
    return node(index).item;
}

public E set(int index, E element) {
    // 校验索引
    checkElementIndex(index);
    // 二分法遍历查找节点
    Node<E> x = node(index);
    // 修改Node节点的 item值
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

/**
 * 返回指定索引处非null节点.
 */
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;
    }
}