简介
LinkedList是一种双向链表数据结构,每个节点维护了自身的数据及前后节点的指针。
链表
链表是由一系列非连续节点组成的数据结构。链表分为担心链表、双向链表。又可以分别循环链表和非循环链表。
- 单向链表。每个节点有一个指向下一个节点的指针next,最后一个节点next指向null。如图1所示
- 单向循环链表。单向循环链表和单向链表唯一不同的是最后一个节点的next指向head,形成一个“环”。如图2所示
- 双向链表。双向两边每个节点包含两个指针,prev指向前一个节点,next指向下一个节点,第一个节点的prev指向null,最后一个节点的next指向null。如图3所示
- 双向循环链表。双向循环链表与双向链表不同的是第一个节点的prev指针指向最后一个节点(tail),最后一个节点(tail)的next指针指向第一个节点(head),形成双向的“环”。如图4所示
LinkedListUML图
LinkedList 定义
1 | public class LinkedList<E> |
LinkedList属性
1 | transient int size = 0; |
内部类Node定义
1 | private static class Node<E> { |
构造方法
1 | public LinkedList() {} |
方法摘要
返回类型 | 方法名称 | 描述 |
---|---|---|
boolean | add(E e) | 增加指定的元素 |
void | add(int, index, E e) | 在指定位置元素 |
boolean | addAll(Collection<? extends E> c) | 增加指定集合的所有元素 |
boolean | addAll(int index, Collection<? extends E> c) | 在指定位置开始增加集合的所有元素 |
void | addFirst(E e) | 在表头插入 |
void | addLast(E e) | 在表尾插入 |
void | clear() | 清空所有元素 |
Object | clone() | 克隆副本 |
boolean | contains(Object o) | 判断是否包含指定的元素。如存在返回true,否则返回false |
Iterator |
descendingIterator() | 返回一个从队尾到队头的反向迭代器 |
E | get(int index) | 返回指定位置的元素 |
E | getFirst() | 返回第一个元素(队头) |
E | getLast() | 返回最后一个元素(队尾) |
int | indexOf(Object o) | 返回列表中首次出现指定元素的位置,不存在返回-1 |
int | lastIndexOf(Object o) | 返回列表中最后一次出现指定元素的位置,不存在返回-1 |
boolean | offer(E e) | 同add |
boolean | offerFirst(E e) | 同addFirst |
boolean | offerLast(E e) | 同addLast |
E | peek() | 和getFirst类似,唯一的区别是getFirst时first存在抛出NoSuchElementException,peek时first不存在返回null |
E | peekFirst() | |
E | peekLast() | |
E | poll() | 表头出队(返回表头元素并删除表头) |
E | pollFirst() | 同poll |
E | pollLast() | 表尾出队(返回表尾元素并删除表尾) |
E | pop() | 同removeFirst() |
void | push(E e) | 同addFirst(E e) |
E | remove() | 同removeFirst() |
E | remove(int index) | 删除指定位置元素 |
boolean | remove(Object o) | 删除指定的元素 |
E | removeFirst() | 表头出队(返回表头元素并删除表头),表头为空抛出NoSuchElementException |
E | removeLast() | 表尾出队(返回表尾元素并删除表尾).表尾为空抛出NoSuchElementException |
E | set(int index, E e) | 用指定的元素替换列表中指定位置的元素 |
int | size() | 返回集合元素大小 |
Object[] | toArray() | |
toArray(T []) | ||
void | trimToSize() | 容量调整为当前元素大小 |
核心源码(基于1.8)
增加元素
1 | public boolean add(E e) { |
获取元素
1 | public E get(int index) { |
删除元素
1 | public E remove() { |
查找
1 | public E get(int index) { |
更新
1 | public E set(int index, E element) { |
总结
- 顺序插入ArrayList较快(不涉及扩容的情况下)。因为LinkedList需要new节点,ArrayList是基于数组的,直接赋值即可
- LinkedList是一个双向链表,不仅维护元素本身,还维护了前置和后继,内存消耗上大于ArrayList
- ArrayList遍历速度高于LinkedList
- 插入/删除:在队头/队尾插入/删除删除较快,在中间插入因为需要整个列表寻找,所以较慢(越往后插入/删除需要寻址次数越多)
本系列文章是为团队内部分享参考网络资料及个人理解整理而成