赞
踩
List是接口,有两个常用实现类
LinkedList
List有的特点,LinkedList,例如 也是允许有序,且可以重复
且大部分方法与ArrayList相似,都是可以通过下标来操作集合数据的
但是也特殊提了操作开头和结尾的方法,getFirst,getLast等方法
基于双向链表实现
- 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()
-
- }
- }
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的方法
因为直接操作头和尾不用遍历,直接取值
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。