2)add(E e) 方法默认将元素添加到链表末尾,所以时间复杂度为 。
public boolean add(E e) {linkLast(e);
return true;
}
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
3)add(int index, E element) 方法将新的元素插入到指定的位置,需要先通过遍历查找这个元素,然后再进行插入,所以时间复杂度为 。
public void add(int index, E element) {checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
如果下标为 0 或者 list.size() - 1 的话,时间复杂度为 。这种情况下,可以使用 addFirst() 和 addLast() 方法。
public void addFirst(E e) {linkFirst(e);
}
private void linkFirst(E e) {
final LinkedList.Node<E> f = first;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
linkFirst() 只需要对 first 进行更新即可。
public void addLast(E e) {linkLast(e);
}
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
linkLast() 只需要对 last 进行更新即可。
需要注意的是,有些文章里面说,LinkedList 插入元素的时间复杂度近似 ,其实是有问题的,因为 add(int index, E element) 方法在插入元素的时候会调用 node(index) 查找元素,该方法之前我们之间已经确认过了,时间复杂度为 ,即便随后调用 linkBefore() 方法进行插入的时间复杂度为 ,总体上的时间复杂度仍然为 才对。
void linkBefore(E e, LinkedList.Node<E> succ) {// assert succ != null;
final LinkedList.Node<E> pred = succ.prev;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}