LinkedList 基本示例及源码解析

目录一、JavaDoc简介二、LinkedList继承接口和实现类介绍三、LinkedList基本方法介绍四、LinkedList基本方法使用五、LinkedList内部结构以及基本元素声明六、LinkedList具体源码分析一、JavaDoc简介LinkedList双向链表,实现了List的双向队列接口,实现了所有list可选择性操作,允许存储任何元素(包括null值)所有的操作都可以表现为双向...

LinkedList 基本示例及源码解析

目录

    • 一、JavaDoc 简介
    • 二、LinkedList 继承接口和实现类介绍
    • 三、LinkedList 基本方法介绍
    • 四、LinkedList 基本方法使用
    • 五、LinkedList 内部结构以及基本元素声明
    • 六、LinkedList 具体源码分析

一、JavaDoc 简介

  1. LinkedList双向链表,实现了List的 双向队列接口,实现了所有list可选择性操作,允许存储任何元素(包括null值)
  2. 所有的操作都可以表现为双向性的,遍历的时候会从首部到尾部进行遍历,直到找到最近的元素位置
  3. 注意这个实现不是线程安全的, 如果多个线程并发访问链表,并且至少其中的一个线程修改了链表的结构,那么这个链表必须进行外部加锁。(结构化的操作指的是任何添加或者删除至少一个元素的操作,仅仅对已有元素的值进行修改不是结构化的操作)。
  4. List list = Collections.synchronizedList(new LinkedList(…)),可以用这种链表做同步访问,但是最好在创建的时间就这样做,避免意外的非同步对链表的访问
  5. 迭代器返回的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的基本方法说明

添加 add(): ----> 1. add(E e) :  直接在'末尾'处添加元素  ----> 2. add(int index,E element) : 在'指定索引处添'加元素  ----> 3. addAll(Collections<? extends E> c) : 在'末尾'处添加一个collection集合  ----> 4. addAll(int index,Collections<? extends E> c):在'指定位置'添加一个collection集合  ----> 5. addFirst(E e): 在'头部'添加指定元素  ----> 6. addLast(E e): 在'尾部'添加指定元素    offer():  ----> 1. offer(E e): 在链表'末尾'添加元素  ----> 2. offerFirst(E e): 在'链表头'添加指定元素  ----> 3. offerLast(E e): 在'链表尾'添加指定元素    push(E e): 在'头部'压入元素  移除    poll():  ----> 1. poll(): 访问并移除'首部'元素  ----> 2. pollFirst(): 访问并移除'首部'元素  ----> 3. pollLast(): 访问并移除'尾部'元素    pop(): 从列表代表的堆栈中弹出元素,从'头部'弹出    remove():   ----> 1. remove(): 移除并返回'首部'元素  ----> 2. remove(int index) : 移除'指定索引'处的元素  ----> 3. remove(Object o): 移除指定元素  ----> 4. removeFirst(): 移除并返回'第一个'元素  ----> 5. removeFirstOccurrence(Object o): 从头到尾遍历,移除'第一次'出现的元素  ----> 6. removeLast(): 移除并返回'最后一个'元素  ----> 7. removeLastOccurrence(Object o): 从头到尾遍历,移除'最后一次'出现的元素    clear(): 清空所有元素  访问 peek():   ----> 1. peek(): 只访问,不移除'首部'元素  ----> 2. peekFirst(): 只访问,不移除'首部'元素,如果链表不包含任何元素,则返回null  ----> 3. peekLast(): 只访问,不移除'尾部'元素,如果链表不包含任何元素,返回null    element(): 只访问,不移除'头部'元素   get():  ----> 1. get(int index): 返回'指定索引'处的元素  ----> 2. getFirst(): 返回'第一个'元素  ----> 3. getLast(): 返回'最后一个'元素  indexOf(Object o): 检索某个元素'第一次'出现所在的位置  LastIndexOf(Object o): 检索某个元素'最后一次'出现的位置   其他  clone() : 返回一个链表的拷贝,返回值为Object 类型  contains(Object o): 判断链表是否包含某个元素  descendingIterator(): 返回一个迭代器,里面的元素是倒叙返回的  listIterator(int index) : 在指定索引处创建一个'双向遍历迭代器' set(int index, E element): 替换某个位置处的元素  size() : 返回链表的长度  spliterator(): 创建一个后期绑定并快速失败的元素  toArray(): 将链表转变为数组返回     

四、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(“-------
源文地址:https://www.guoxiongfei.cn/cntech/18390.html