一、LinkedList是一个双向链表,数据结构图如下(节点中的数字为节点存储的内容):
LinkedList结构
二、LinkedList内部有一个Node类,Node类有三个成员变量,分别是item(节点存储的内容)、prev(指向上一个Node)、next(指向下一个Node)
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
三、LinkedList实现了List、Queue、Deque(双端队列)接口,有List的特性(有顺序、不重复),支持Queue操作(先进后出),支持Deque操作(在队首队尾插入删除元素),此外,还提供了push、pop方法,因此还有栈的特性。
四、LinkedList常用API
- 在链表头添加元素的方法:addFirst、offerFirst、push,在链表尾添加元素的方法:add、addLast、offerLast、offer。
- 在链表头删除元素的方法:(删除元素的同时会返回所删除的元素,但有可能元素不存在,即链表为空,当遇到这种情况时LinkedList提供了两种处理方式,返回null或者抛出异常),返回null的方法有poll、pollFirst,抛出异常的方法有removeFirst、remove、pop。在链表末端删除元素的方法(末端元素同样可以不存在,即链表为空):返回null的方法有pollLast,抛出异常的方法有removeLast。
- 获取链表头元素的方法(获取元素同样会出现链表为空的情况):返回null的方法有peek、peekFirst、element,抛出异常的方法有getFirst。获取链表末端元素的方法:返回null的方法有peekLast,抛出异常的方法有getLast。
五、与ArrayList一样,有两个toArray方法,toArray()
和toArray(T[] a)
,toArray()
返回一个Object[]数组,toArray(T[] a)
返回一个特定类型的数组。
六、内部有3个迭代器类,ListItr、DescendingIterator、LLSpliterator。
- ListItr可以向前向后遍历,还可以增加元素、设置某个位置的元素。
- DescendingIterator是从链表末端向前(单向)遍历的迭代器,内部其实是封装了一个ListItr,next方法委托了ListItr的previous方法,hasNext委托了ListItr的hasPrevious方法。
- LLSpliterator是java8并行迭代器的一个实现,此实现通过trySplit返回一个Spliterators.ArraySpliterator对象,该对象再通过trySplit可把元素分割两半,然后可以交给多个线程处理。
网友评论