Java集合框架(二)-LinkedList

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

// LinkedList包含首尾操作的特有方法，在list接口中没有定义，不推荐多态创建集合对象
// List<String> strList = new LinkedList<>();
// strList.addFirst();
LinkedList<String> linkedList = new LinkedList<>();

添加元素的普通方法：add(元素)，将元素自动添加到链表的末尾

addFirst(E e)添加到链表首部

addLast(E e)添加到链表首部

getFirst() 获取第一个元素

getLast() 获取最后一个元素

removeFirst() 删除第一个元素

removeLast() 删除最后一个元素

size() 获取集合中元素个数方法

 1）获取的下标值必须是在有效的范围内：从0到元素个数-1之间，否则报错：IndexOutOfBoundsException;
 2）如果下标值在可以有效的范围内，自动进行二分法移动指针，先判断目标下标值在元素个数一半的前半段还是后半段;
    如果在前半段，自动从第一个节点开始，依次向后移动指针，直到找到下标位置，返回对应元素;
    如果在后半段，自动从最后一个节点，依次向前移动指针，直到找到指定下标位置，返回对应元素;
 所以：当下标位置越接近元素个数一半值（越靠近中间位置），效率是最低的，可以看出：遍历和随机访问的效率低;

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