1.1 LinkedList介绍

List是接口,有两个常用实现类

• ArrayList

• LinkedList

---

List有的特点,LinkedList,例如 也是允许有序,且可以重复

且大部分方法与ArrayList相似,都是可以通过下标来操作集合数据的

但是也特殊提了操作开头和结尾的方法,getFirst,getLast等方法

---

基于双向链表实现

1.2 演示API

public class Demo2 {
​
    public static void main(String[] args) {
        // 创建对象
        LinkedList<Integer> list = new LinkedList<>( );
​
        // 添加元素
        list.add(3);
        list.add(3);
        list.add(1);
        list.add(4);
        list.add(2);
        System.out.println("list = " + list);
​
        // 在指定下标插入
        list.add(2,5);
        System.out.println("list = " + list);
​
        // E get(int i)
        Integer i = list.get(2);
        System.out.println("i = " + i);
​
        // 根据下标移除
        Integer old = list.remove(2);
        System.out.println("old = " + old);
        System.out.println("list = " + list);
​
        // 迭代
        for(int n:list){
            System.out.println(n );
        }
​
        // 相对arraylist有特殊方法,操作头和尾
        // 在开头添加
        list.addFirst(0);
        // 在结尾添加
        list.addLast(10);
        System.out.println("list = " + list);
​
        // list.removeFirst()
        // list.removeLast()
        // list.getFirst()
        // list.getLast()
​
    }
}

1.3 底层原理

LinkedList底层是通过双向链表实现的

双向链表在内存的特点

• 链表中每个存储数据的叫做节点(node)

• 每个节点(node)在空间上不是连续,但是节点内存储了上一个/下一个的位置信息

• 也有下标,但是因为内存空间上不连续,所以无法通过下标直接定位的,

  • 通过下标找到元素,是判断下标位置,举例开头近,就从头遍历,依次找到它

  • 如果离尾近,从尾倒着遍历,依次找到它

  • 无论怎样,是无法直接定位,只能挨个查找

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

• 这样解释了,LinkedList为什么提供了操作头xxFirst和尾xxxLast的方法

  • 因为直接操作头和尾不用遍历,直接取值