LinkedList以双向链表实现,链表无容量限制,但是双向链表本身就使用了更多的空间,也需要额外的链表指针操作.
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;
}
}
先说一下Node节点,LinkedList是以双向链表的形式实现,每个节点都由Node组成,node包含有当前节点的元素,以及上一个元素和下一个元素的Node值
LinkedList#add(E e)
这里我们同样以add为切入点
LinkedList#add()
// LinkedList的成员变量 size 代表链表的长度,元素的数量
transient int size = 0;
// 链表的首个节点
transient Node<E> first;
// 链表的最后一个节点
transient Node<E> last;
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
主要是linkedLast(E e),首先得到链表的最后一个节点,并根据传入的元素创建一个新的节点,并将原先最后的节点作为新创建节点的上一个节点,新建创建的节点的下一个节点为设置为null,将新创建的节点赋值给last,即:新创建的节点作为最后一个节点,如果原始的尾节点为空,则将头结点first也赋值newNode即新创建的节点,如果原始的尾节点不为空,则将原始尾节点的下一个节点指针指向新创建的节点newNode,然后size自增1,修改次数modCount自增1。
set(int index,E element)
ArrayList#set():
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
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;
}
}
set()中首先根据指定的下标得到相应的Node值。来看node()中的判断,如果指定的指针小于链表长度的一半,则从头节点开始进行遍历,如果大于链表的一半,则从尾节点开始进行遍历,然后找到指定指针,并返回该指针所对应的node值。最后将遍历到的node中的元素值修改为指定的元素值,并返回原始元素值。
get(int index)
get()比较简单,这里不再多说
public E get(int index) {
checkElementIndex(index);
// 根据node()获取到指定下标的node值,并返回包含的元素值
return node(index).item;
}
add(int index, E element)插入方法
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
里面有一个判断条件,如果要插入的指针等于链表的长度,即在链表的尾部插入一个节点,则直接调用linkLast()即可,如果不等于,则调用linkBefore(),其中入参为指定的元素element和指定节点上的node;
LinkedList#linkBefore()
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
首先获取到指定节点succ的上一个节点pred,并根据传入的元素创建一个新的节点newNode,并将指定节点succ的上一个节点pred作为新创建节点newNode的上一个节点,查询到的指定节点succ为新创建节点newNode的下一个节点,并将获取到的指定节点succ的上一个节点的指针指向新创建的节点newNode,指定节点的上一个节点pred的下一个节点指针指向新创建的节点,最后链表长度加一,修改次数加一 (emmmmmmmmmm有点绕口)
remove(int index)
ArrayList#remove():
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> 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;
size--;
modCount++;
return element;
}
checkElementIndex()为检查index是否合法,这里不再多说,unlink的入参为指定指针所对应node值,获取到指定的node值之后,在获取该node多对应的元素值element,上一个节点prev,下一个节点next,然后再分别对上下节点做判断:(可能还是会有点绕口 )
如果上一个节点
prev等于null,说明此节点为头结点,赋值给first节点,如果上一个节点prev不为null,则将上一个节点prev的的下一个节点指针指向next节点,并将当前节点x的上一个节点指针指向null
如果下一个节点next为null,说明当前节点为尾节点,赋值给last,如果下一个节点next不为null,则将下一个节点next的上一个节点指针指向上一个节点prev,当前节点x的下一个节点指针指向null.
关于LinkedList的其他方法,这里就不在多说了。
Iterator
LinkedList间接继承了AbstractList,其中有默认实现的Itr迭代器,其实ArrayList同样继承了AbstractList,不知道为什么没有直接调用,用法通ArrayList一样(具体的可以看List(一):ArrayList源码浅析的Iteraotr小节):
LinkedList<String> arrayList = new LinkedList<>();
arrayList.add("chuan--0");
arrayList.add("chuan--1");
arrayList.add("chuan--2");
arrayList.add("chuan--3");
arrayList.add("chuan--4");
Iterator<String> iterator = arrayList.iterator();
while (iterator.hasNext()){
String str = iterator.next();
Log.i(TAG, "onResume: " + str);
AbstractList中的Itr类,有三个成员变量, 四个方法,以LinkedList为例
cursor 当前节点所对应的下一个节点的下标
lastRet 迭代的最后一次的节点所对应的下标
expectedModCount 根据此属性判断迭代期间是否有其他操作,如果有会抛出异常
hasNext() 判断是否有下一个节点
nex() 获取下一个节点
remove 删除当前节点
public boolean hasNext() {
// 获取到当前链表的总长度,即元素总数量
return cursor != size();
}
public E next() {
checkForComodification();
try {
// 注意 此时的cursor代表当前节点的指针,下面会有一个cursor+1的操作,那时的cursor代表的是下一个节点的指针
int i = cursor;
// 获取到下一个节点
E next = get(i);
// 将当前节点的指针下标赋值给lastRet
lastRet = i;
cursor = i + 1;
// 返回当前节点
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// 直接调用remove方法 进行操作
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
// 此时将lastRet赋值为-1,即每次next只能进行一次删除操作
lastRet = -1;
// 同步expectedModeCount,保证修改次数的一致性
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
ListItr
ListItr继承于Itr和ListIterator
Listerator有几个抽象方法
add() 插入节点
next() 当前节点的下一个节点
hasPrevious() 当前节点时候是否有前一个节点,即当前节点是否是头结点
hasNext() 当前节点是否有尾节点,即当前节点时候是尾节点
nextIndex() 当前节点的下一节点的下标
previousIndex() 当前节点的上一节点的下标
remove() 删除当前节点
set() 修改当前节点
Itr前面有说过,主要负责遍历链表和删除操作.
来看ListItr,其包含有四个成员变量和几个重写方法,主要是重写的ListIterator中的抽象方法
lastReturned 遍历的最后一次返回的node值,即当前节点的node值
next 当前节点的下一节点
nextIndex 当前节点的下一节点的下标
expectedModCount 集合修改的次数,用于判断遍历期间是否有发生修改链表的操作
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
这是ListItr的构造器,入参为节点的index值,并获取当前节点
LinkedList#ListItr#hasNext():
public boolean hasNext() {
return nextIndex < size;
}
判断当前节点是否有下一节点,表现为当前节点的下标是否小于链表的长度
LinkedList#ListItr#next()
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
获取当前节点的下一个节点值,并吧当前节点值赋值给lastReturned,next重新赋值为next的下一节点值,nextIndex自增1,并返回lastReturned的元素
// 获取当前节点的下一节点的下标值
public int nextIndex() {
return nextIndex;
}
// 获取当前节点的上一节点的下标值
public int previousIndex() {
return nextIndex - 1;
}
// 判断当前节点是否有上一节点,即当前节点是否为头结点
public boolean hasPrevious() {
return nextIndex > 0;
}
LinkedList#ListItr#previous()
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
此方法是为了获取当前节点的的上一节点值,并将下一节点下标值nextIndex减一
LinkedList#ListItr#remove
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
删除当前节点,首先获取到当前节点的下一节点值,并通过unlink()进行节点重新关联操作,然后将下一节点下标nextIndex减一,expectedModeCount进行操作次数加一.
LinkedList#ListItr#set():
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
修改操作比较简单这里不再多说
LinkedList#ListItr#add()
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
插入操作,如果当前节点为null,即插入为新增操作或者空链表进行插入操作,会通过linkLast()进行尾部节点插入操作,否则通过linkBefore()进行插入操作,下一节点下标值自增1,修改次数自增1
