LinkedList 基本示例及源码解析(一)
一、JavaDoc 简介二、LinkedList 继承接口和实现类介绍三、LinkedList 基本方法介绍四、LinkedList 基本方法使用五、LinkedList 内部结构以及基本元素声明六、LinkedList 具体源码分析
一、JavaDoc 简介
- LinkedList双向链表，实现了List的 双向队列接口，实现了所有list可选择性操作，允许存储任何元素(包括null值)
- 所有的操作都可以表现为双向性的，遍历的时候会从首部到尾部进行遍历，直到找到最近的元素位置
- 注意这个实现不是线程安全的, 如果多个线程并发访问链表，并且至少其中的一个线程修改了链表的结构，那么这个链表必须进行外部加锁。(结构化的操作指的是任何添加或者删除至少一个元素的操作，仅仅对已有元素的值进行修改不是结构化的操作)。
- List list = Collections.synchronizedList(new LinkedList(…)),可以用这种链表做同步访问，但是最好在创建的时间就这样做，避免意外的非同步对链表的访问
- 迭代器返回的iterators 和 listIterator方法会造成fail-fast机制：如果链表在生成迭代器之后被结构化的修改了，除了使用iterator独有的remove方法外，都会抛出并发修改的异常。因此，在面对并发修改的时候，这个迭代器能够快速失败，从而避免非确定性的问题
二、LinkedList 继承接口和实现类介绍
java.util.LinkedList 继承了 AbstractSequentialList 并实现了List , Deque , Cloneable 接口，以及Serializable 接口
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}
类之间的继承体系如下：
下面就对继承树中的部分节点进行大致介绍：
AbstractSequentialList 介绍：
这个接口是List一系列子类接口的核心接口，以求最大限度的减少实现此接口的工作量，由顺序访问数据存储(例如链接链表)支持。对于随机访问的数据(像是数组)，AbstractList 应该优先被使用这个接口可以说是与AbstractList类相反的，它实现了随机访问方法，提供了get(int index),set(int index,E element), add(int index,E element) and remove(int index)方法
对于程序员来说：
要实现一个列表，程序员只需要扩展这个类并且提供listIterator 和 size方法即可。
对于不可修改的列表来说， 程序员需要实现列表迭代器的 hasNext(), next(), hasPrevious(),
previous 和 index 方法
AbstractList 介绍：
这个接口也是List继承类层次的核心接口，以求最大限度的减少实现此接口的工作量，由顺序访问
数据存储(例如链接链表)支持。对于顺序访问的数据(像是链表)，AbstractSequentialList 应该优先被使用，
如果需要实现不可修改的list，程序员需要扩展这个类，list需要实现get(int) 方法和List.size()方法
如果需要实现可修改的list，程序员必须额外重写set(int,Object) set(int,E)方法(否则会抛出
UnsupportedOperationException的异常)，如果list是可变大小的，程序员必须额外重写add(int,Object) , add(int, E) and remove(int) 方法
AbstractCollection 介绍：
这个接口是Collection接口的一个核心实现，尽量减少实现此接口所需的工作量
为了实现不可修改的collection，程序员应该继承这个类并提供呢iterator和size 方法
为了实现可修改的collection，程序团需要额外重写类的add方法，iterator方法返回的Iterator迭代器也必须实现remove方法
三、LinkedList 基本方法介绍
上面看完了LinkedList 的继承体系之后，来看看LinkedList的基本方法说明
上面图片的文字比较小，可能有些不清晰，下面我就来对上面图片做一个大致介绍：
四、LinkedList 基本方法使用
学以致用，熟悉了上面基本方法之后，来简单做一个demo测试一下上面的方法：
/** * 此方法描述 * LinedList 集合的基本使用 */ public class LinkedListTest { public static void main(String[] args) { LinkedList<String> list = new LinkedList<>(); list.add("111"); list.add("222"); list.add("333"); list.add(1,"123"); // 分别在头部和尾部添加元素 list.addFirst("top"); list.addLast("bottom"); System.out.println(list); // 数组克隆 Object listClone = list.clone(); System.out.println(listClone); // 创建一个首尾互换的迭代器 Iterator<String> it = list.descendingIterator(); while (it.hasNext()){ System.out.print(it.next() + " "); } System.out.println(); list.clear(); System.out.println("list.contains('111') ? " + list.contains("111")); Collection<String> collec = Arrays.asList("123","213","321"); list.addAll(collec); System.out.println(list); System.out.println("list.element = " + list.element()); System.out.println("list.get(2) = " + list.get(2)); System.out.println("list.getFirst() = " + list.getFirst()); System.out.println("list.getLast() = " + list.getLast()); // 检索指定元素出现的位置 System.out.println("list.indexOf(213) = " + list.indexOf("213")); list.add("123"); System.out.println("list.lastIndexOf(123) = " + list.lastIndexOf("123")); // 在首部和尾部添加元素 list.offerFirst("first"); list.offerLast("999"); System.out.println("list = " + list); list.offer("last"); // 只访问，不移除指定元素 System.out.println("list.peek() = " + list.peek()); System.out.println("list.peekFirst() = " + list.peekFirst()); System.out.println("list.peekLast() = " + list.peekLast()); // 访问并移除元素 System.out.println("list.poll() = " + list.poll()); System.out.println("list.pollFirst() = " + list.pollFirst()); System.out.println("list.pollLast() = " + list.pollLast()); System.out.println("list = " + list); // 从首部弹出元素 list.pop(); // 压入元素 list.push("123"); System.out.println("list.size() = " + list.size()); System.out.println("list = " + list); // remove操作 System.out.println(list.remove()); System.out.println(list.remove(1)); System.out.println(list.remove("999")); System.out.println(list.removeFirst()); System.out.println("list = " + list); list.addAll(collec); list.addFirst("123"); list.addLast("123"); System.out.println("list = " + list); list.removeFirstOccurrence("123"); list.removeLastOccurrence("123"); list.removeLast(); System.out.println("list = " + list); list.addFirst("top"); list.addLast("bottom"); list.set(2,"321"); System.out.println("list = " + list); System.out.println("--------------------------"); // 创建一个list的双向链表 ListIterator<String> listIterator = list.listIterator(); while(listIterator.hasNext()){ // 移到list的末端 System.out.println(listIterator.next()); } System.out.println("--------------------------"); while (listIterator.hasPrevious()){ // 移到list的首端 System.out.println(listIterator.previous()); } } }输出： -------1------- [top, 111, 123, 222, 333, bottom] -------2-------[top, 111, 123, 222, 333, bottom] bottom 333 222 123 111 top list.contains('111') ? false [123, 213, 321] list.element = 123 list.get(2) = 321 list.getFirst() = 123 list.getLast() = 321 list.indexOf(213) = 1 list.lastIndexOf(123) = 3 -------4------- [first, 123, 213, 321, 123, 999] list.peek() = first list.peekFirst() = first list.peekLast() = last list.poll() = first list.pollFirst() = 123 list.pollLast() = last -------5------- [213, 321, 123, 999] list.size() = 4 -------6------- [123, 321, 123, 999] 123 123 true 321 -------7------- [] -------8------- [123, 123, 213, 321, 123] list = [123, 213] -------9------- [top, 123, 321, bottom] -------------------------- top 123 321 bottom -------------------------- bottom 321 123 top
