一、LinkedList基本原理
- 优点：插入数据特别的快，不像ArrayList数组那样子，挪动大量的元素的，他是直接在链表里加一个节点就可以了
- 缺点，不太适合在随机的位置，获取某个随机的位置的元素，比如LinkedList.get(10)，这种操作，性能就很低，因为他需要遍历这个链表，从头开始遍历这个链表，直到找到index = 10的这个元素为止
- LinkedList底层是基双向链表，而ArrayList底层基于数组。也就是底层结构不同，才影响着他们的优缺点
二、使用场景
- ArrayList：代表一个集合，只要别频繁的往里面插入和灌入大量的元素就可以了，遍历，或者随机查，都可以
- LinkedList：适合，频繁的在list中插入和删除某个元素,典型的就是用作队列
三、插入元素源码
我们还是从基本的方法作为入口，还有一点就是我们一定要清楚，LinkedList主要用作队列使用，最后只关注一下他的核心源码
代码片段一、
- 首先要看下，最主要的是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;
}
}
代码片段二、add方法
- addFirst方法其实和add方法一样的
/**
* 这里默认向链表的尾部插入
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 将当前元素放入队尾
linkLast(e);
return true;
}
代码片段二、
/**
* Links e as last element.
*/
void linkLast(E e) {
// 定义一个l元素，指向last尾元素
final Node<E> l = last;
// 新增一个Node，他的pre指针指向l，就是队尾的那个元素，next指向null
final Node<E> newNode = new Node<>(l, e, null);
// 让last指向新增的节点
last = newNode;
if (l == null)
// 如果l为空，说明这是一个新的链表，新怎的节点也是头结点
first = newNode;
else
// l.next的意思是原来的队尾节点的next指向当前新怎的节点
l.next = newNode;
// 链表长度+1
size++;
modCount++;
}
代码片段三、 addFirst方法
/**
* Inserts the specified element at the beginning of this list.
*
* @param e the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* Links e as first element.
*/
private void linkFirst(E e) {
// 定义一个f变量，指向队首
final Node<E> f = first;
// 新增一个新的节点，pre指针指向Null ,next指向队首元素
final Node<E> newNode = new Node<>(null, e, f);
// 将first指针指向新增节点
first = newNode;
if (f == null)
// 如果f为空，说明这是一个新的链表，新怎的节点也是头结点
last = newNode;
else
// y原来首节点的prev指向当前新增节点
f.prev = newNode;
size++;
modCount++;
}
代码片段四、
在指定位置插入元素
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
// 参数校验
checkPositionIndex(index);
// 如果是index==size，则直接插入尾部
if (index == size)
linkLast(element);
else
// node方法如下
linkBefore(element, node(index));
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// 如果index < size/2,说明index在队列的前半部分
if (index < (size >> 1)) {
// 拿到第一个元素，然后从头开始遍历，
Node<E> x = first;
//不停的遍历，直到找到index的位置，然后返回x
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 这里其实就是从尾部开始遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
//创建一个新的节点，前一个节点是index节点的前一个节点，next节点为succ节点
// 其实就是node方法遍历的时候找到的那个index对应的节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 让原来的节点的prev指向新创建的节点
succ.prev = newNode;
if (pred == null)
// pred如果为空的话，说明index对应是头结点
first = newNode;
else
// index节点原来对应的next指向创建的新节点
pred.next = newNode;
size++;
modCount++;
}
四、获取元素源码
代码片段一、getFirst peek
/**
* Returns the first element in this list.
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
//返回第一个元素，这里的first其实就是指向了链表的第一个元素
// 如果链表为空的话，则抛出异常
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
// 和getFirst区别就是如果链表为空的话，返回null
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Returns the element at the specified position in this list.
* 对于LinkedList而言，读取某个元素的时候，是通过node方法，遍历链表，判断index的位置，所以随机读取
* 是LinkedList的弱点
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
五、删除元素
代码片段一、
/**
* Retrieves and removes the head (first element) of this list.
* 删除头部元素
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
public E remove() {
return removeFirst();
}
/**
* Removes and returns the first element from this list.
*
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
// 首先。拿到链表的第一个元素
final Node<E> f = first;
// 如果队头的元素为null的话，这个队列也是空的
if (f == null)
throw new NoSuchElementException();
// 最后还是走到unlinkFirst，删除的核心逻辑
return unlinkFirst(f);
}
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* Unlinks non-null last node l.
* 这里和unlinkfirst几乎一个套路
*/
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;
}
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 1.先拿到队头的元素
// 2. 然后拿到队头的next元素
// 3. 队头的元素=null，
// 4. 队头的next指针指向null
// 5.将first指针指向next
// 6. 通过2、3、4、5步骤，其实就是将队头的元素释放掉了
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;
}
网友评论