- 一、底层数据结构
- 2.getFirst(), getLast()
- 3.removeFirst(), removeLast(), remove(e), remove(index)
- 4.add()
- 5.addAll()
- 6.clear()
- 7.常见方法
一、底层数据结构
LinkedList底层通过双向链表实现,双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。当链表为空的时候first和last都指向null。
transient int size = 0;
transient Node first;
transient Node last;
其中node是私有的内部类:
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } `` # 二、常见方法源码 ## 1.构造函数 ```java public LinkedList() { } public LinkedList(Collection extends E> c) { this(); addAll(c); }
1.参数为空时底层为一个空链表
2.参数为collection接口下的实现类时,获取实现类中的元素并加到链表中
获取第一个元素和最后一个元素
public E getFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
其中first和last分别代表底层链表的第一个节点和最后一个节点
3.removeFirst(), removeLast(), remove(e), remove(index)
public boolean remove(Object o) {
if (o == null) {
for (Node x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node x) {
// assert x != null;
final E element = x.item;
final Node next = x.next;
final Node prev = x.prev;
if (prev == null) {// 第一个元素
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {// 最后一个元素
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null; // GC
size--;
modCount++;
return element;
}
删除元素 - 指的是删除第一次出现的这个元素, 如果没有这个元素,则返回false;判断的依据是equals方法, 如果equals,则直接unlink这个node;由于LinkedList可存放null元素,故也可以删除第一次出现null的元素;
删除head元素:
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
remove(int index)使用的是下标计数, 只需要判断该index是否有元素即可,如果有则直接unlink这个node。
public E removeFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node f) {
// assert f == first && f != null;
final E element = f.item;
final Node 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;
}
删除last元素:
public E removeLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node l) {
// assert l == last && l != null;
final E element = l.item;
final Node 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;
}
4.add()
添加元素
在最后一个节点之后新建一个节点并且将节点的值赋值到数据域当中去
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
add(int index, E element), 当index==size时,等同于add(E e);如果不是,则分两步: 1.先根据index找到要插入的位置,即node(index)方法;2.修改引用,完成插入操作。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
5.addAll()
addAll():在链表之后新建节点来存放collection接口下实现类里面的元素
addAll():从指定索引处开始新建节点来存放collection中的元素
public boolean addAll(Collection extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node 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 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;
}
6.clear()
为了让GC更快可以回收放置的元素,需要将node之间的引用关系赋空。
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node x = first; x != null; ) {
Node next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
7.常见方法
通过index获取元素:获取指定下标节点处的节点的数据
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
将某个位置的元素重新赋值:直接修改
public E set(int index, E element) {
checkElementIndex(index);
Node x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
将元素插入到指定index位置:
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
删除指定位置的元素:
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}



