|
参考资料：
《Java集合：LinkedList详解》
《Collection - LinkedList源码解析》
《LinkedList》
写在开头：本文为个人学习笔记，内容比较随意，夹杂个人理解，如有错误，欢迎指正。
目录
一、基础概念
? ? ? ? 1、基本属性
? ? ? ? 2、构造方法
二、修改
三、查找
? ? ? ? 1、node
????????2、get
? ? ? ? ?3、peek
? ? ? ? 4、element
四、增加
? ? ? ? 1、link
? ? ? ?2、add
? ? ?2.1、add
? ? ?2.2、addAll
? ? ? ? 3、offer
? ? ? ? 4、push
五、删除
? ? ? ? 1、unlink
? ? ?1.1、unlink
? ? ?1.2、unlinkFirst
? ? ?1.3、unlinkLast
? ? ? ? 2、remove
? ? ? ?3、poll
一、基础概念
?????????LinkedList是基于链表实现的数组，同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)。
? ? ? ? 1、基本属性
? ? ? ? 我们可以看到LinkedList每一个节点都会记录本节点信息，以及前后节点的指针，这也表明了其本质是一个双向链表。
// 链表长度
transient int size = 0;
// 链表头节点
transient Node<E> first;
// 链表尾节点
transient Node<E> last;
// 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;
}
}
? ? ? ? 2、构造方法
? ? ? ? LinkedList提供了2个，一个无参一个有参，无参构造方法不做任何操作，将创建工作延后到add时进行，而有参构造函数是其他集合类型转换而来。
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
二、修改
? ? ? ? 修改方法最简单，传入Index和修改后的值element即可
public E set(int index, E element) {
checkElementIndex(index);
// 首先使用node方法先找出index位置的元素并返回
Node<E> x = node(index);
// 修改旧元素的值并返回
E oldVal = x.item;
x.item = element;
return oldVal;
}
三、查找
? ? ? ? 1、node
? ? ? ? node方法是查找链表中元素的基本方法，后续几个方法中都会有用到。
? ? ? ? 这里在查找前先进行了位置判断，index < (size >> 1)，缩小查找范围为原先的一半。
Node<E> node(int index) {
// 这里右移一位然后判断index靠近左侧还是右侧，以此来虽小查找范围
if (index < (size >> 1)) {
// 如果是在左半侧，则从first元素开始查找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 如果是在右半侧，则从last元素开始查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
????????2、get
????????????????get方法有三个：???????
? ? ? ? ? ? ? ? get：调用上文中的node方法查找给定下标位置元素并返回
? ? ? ? ? ? ? ? getFirst：直接返回first位置的元素
????????????????getLast：直接返回last位置的元素? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
public E get(int index) {
// 索引下标校验
checkElementIndex(index);
// 调用node方法查找并返回结果
return node(index).item;
}
public E getFirst() {
// 直接返回first位置的元素
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
// 直接返回last位置的元素
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
? ? ? ? ?3、peek
? ? ? ? ? ? ? ? peek方法有三个：???????
? ? ? ? ? ? ? ? peek：直接返回first位置的元素
? ? ? ? ? ? ? ? getFirst：直接返回first位置的元素
????????????????getLast：直接返回last位置的元素?
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
? ? ??
? ? ? ? 4、element
? ? ? ? ? ? ? ? 直接调用getFirst方法返回first位置的元素
public E element() {
return getFirst();
}
四、增加
? ? ? ? 1、link
? ? ? ? ????????linkBefore：将参数e插入到succ前，调整prev与next节点指向的位置
????????????????linkFirst：头插法，将参数e作为新的first节点插入，原first调整为其next节点
????????????????linkLast：尾插法，直接作为新的last节点接到链表最后
void linkBefore(E e, Node<E> succ) {
// 获取succ的prev节点
final Node<E> pred = succ.prev;
// 使用prev,e,succ三个值new一个新的节点出来
final Node<E> newNode = new Node<>(pred, e, succ);
// 将new出的新节点置为succ的prev节点
succ.prev = newNode;
// 如果当前pred节点为空，说明是第一个元素，同时赋值为first节点
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
// 如果当前first节点为空，说明是第一个元素，同时赋值为last节点
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
void linkLast(E e) {
// new一个新的节点，接到last节点之后，并修改为新的Last节点
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
// 如果当前last节点为空，说明是第一个元素，同时赋值为first节点
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
? ? ? ?2、add
? ? ? ? ????????2.1、add
? ? ? ? ? ? ? ? add(E e)：调用linkLast在链表末尾插入元素
? ? ? ? ? ? ? ? add(int index,E element)：先找出index所对应的位置
? ? ? ? ? ? ? ? ? ? ? ?1：index为链表末尾
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??调用linkLast在链表末尾插入元素
? ? ? ? ? ? ? ? ? ? ? ?2：index不为链表末尾
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?调用linkBefore在Index位置前插入元素
? ? ? ? ? ? ? ? addFirst(E e)：调用linkFirst在链表末尾插入元素
? ? ? ? ? ? ? ? addLast(E e)：调用linkLast在链表末尾插入元素
public boolean add(E e) {
// 调用linkLast方法, 将节点添加到尾部
linkLast(e);
return true;
}
// 在index位置插入节点，节点值为element
public void add(int index, E element) {
checkPositionIndex(index);
// 如果索引为size，即将element插入链表尾部
if (index == size)
linkLast(element);
else
// 将element插入原index位置节点的前面
// 即：将element插入index位置，将原index位置节点移到index+1的位置
linkBefore(element, node(index));
}
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
? ? ? ? ????????2.2、addAll
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
// 使用toArray方法将集合转为数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
// 遍历数组并创建新节点，再加入到原链表中
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
? ? ? ? 3、offer
? ? ? ? ? ? ? ? offer：内部调用add(E e)方法
? ? ? ? ? ? ? ? offerFirst：内部调用addFirst(E e)方法
? ? ? ? ? ? ? ? offerLast：内部调用addLast(E e)方法
public boolean offer(E e) {
return add(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
? ? ? ? 4、push
? ? ? ? ? ? ? ? 内部调用addFirst方法实现
public void push(E e) {
addFirst(e);
}
五、删除
? ? ? ? 1、unlink
? ? ? ? ????????1.1、unlink
E unlink(Node<E> x) { // 移除链表上的x节点
// assert x != null;
final E element = x.item; // x节点的值
final Node<E> next = x.next; // x节点的下一个节点
final Node<E> prev = x.prev; // x节点的上一个节点
if (prev == null) { // 如果prev为空，则代表x节点为头结点，则将first指向next即可
first = next;
} else { // 否则，x节点不为头结点，
prev.next = next; // 将prev节点的next属性指向x节点的next属性
x.prev = null; // 将x的prev属性清空
}
if (next == null) { // 如果next为空，则代表x节点为尾节点，则将last指向prev即可
last = prev;
} else { // 否则，x节点不为尾节点
next.prev = prev; // 将next节点的prev属性指向x节点的prev属性
x.next = null; // 将x的next属性清空
}
x.item = null; // 将x的值清空，以便垃圾收集器回收x对象
size--;
modCount++;
return element;
}
? ? ? ????????? 1.2、unlinkFirst
? ? ? ? ????????????????删除first元素
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
? ? ? ? ????????1.3、unlinkLast
????????????????????????删除last元素
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
? ? ? ? 2、remove
????????????????remove()：内部调用removeFirst()方法删除first位置元素
????????????????remove(int index)：根据传入的index调用node找出对应的元素，调用unlink进行删除
????????????????remove(Object o)：根据传入的o，遍历链表找到对应的元素，调用unlink删除
????????????????removeFirst()：内部调用unlinkFirst方法删除first位置元素
????????????????removeLast()：内部调用unlinkLast方法删除last位置元素
public E remove() {
return removeFirst();
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
? ? ? ?3、poll
? ? ? ? ? ? ? ? poll：判断first元素是否为空，不为空则调用unlinkFirst(E e)删除
????????????????pollFirst：判断first元素是否为空，不为空则调用unlinkFirst(E e)删除
????????????????pollLast：判断last元素是否为空，不为空则调用unlinkLast(E e)删除
public E poll() {
// 判断first元素是否为空，不为空则调用unlinkFirst(E e)删除
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollFirst() {
// 判断first元素是否为空，不为空则调用unlinkFirst(E e)删除
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollLast() {
// 判断last元素是否为空，不为空则调用unlinkLast(E e)删除
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
|