【LinkedList】集合

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的方法

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