[数据结构与算法]LinkedList常用方法探究

LinkedList底层是链表，所以有头指针和尾指针，在一个Node节点的头和尾需要指向下一个被链接的元素

流程图：

·new?LinkedList();

public LinkedList() {
}

·add(E e);

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

?将新增的节点添加到最后一个节点之后

void linkLast(E e) {
        //last是一个全局变量，指向最后一个节点，第一次新增的时候，last为null，所以l也为null
        final Node<E> l = last;
        // newNode    null<--"a1"-->null
        // 创建一个e的Node节点，前置指向原last节点，后置指向null
        final Node<E> newNode = new Node<>(l, e, null);
        // 将newNode节点赋值为last节点
        last = newNode;
        //  l=null
        if (l == null) {
            // first也是一个全局变量，指向头结点，如果是第一个添加的元素，则first指针指向该结点
            first = newNode; // first指向newNode
        } else {
            //如果不是第一个添加进来的元素，则更新l的后置结点指向新添加的元素结点newNode
            l.next = newNode;
        }
        size++; //记录长度
        modCount++; // 记录修改次数
    }

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

·remove(int index)

public E remove(int index) {
    // 校验传入的参数index是否超出了数组的最大下标且下标不为负数，如果超出，则抛出：IndexOutOfBoundsException异常
    checkElementIndex(index);
    // node(index)返回需要删除的结点
    return unlink(node(index)); // 断开待删除结点的链接 
}

private void checkElementIndex(int index) {
    if (!isElementIndex(index)) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

根据index查找Node

Node<E> node(int index) {
    // assert isElementIndex(index);
    // 如果需要获取的index小于总长度size的一半，则从头部开始向后遍历查找
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next; // 从first结点向后next查找，直到index下标node，返回node
        }
        return x;
    } else { // 从尾部开始向前遍历查找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) {
            x = x.prev; // 从last结点向前prev查找，直到index下标node，返回node
        }
        return x;
    }
}

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;
    /** x.prev为null，表示x结点为第一个元素*/
    if (prev == null) {
        first = next; // 更新first头指针为x结点的后置结点
    } else {
        prev.next = next; // 将x的前置结点与x的后置结点相连接
        x.prev = null; // 断开x的前置指针
    }
    /** x.next为null，表示x结点为最后一个元素*/
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev; // 将x的后置结点与x的前置结点相连接
        x.next = null; // 断开x的后置指针
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

**************此文章只是本人学习过程中的学习笔记，不做其他用途，如果有其他意见，欢迎一起讨论，谢谢，侵删*************************