LinkedList实现
Android的LinkedList是通过双向列表实现的。链表元素除了含有自身的值以为,还含有上一个元素和下一个元素的引用。
private static final class Link<ET> {
ET data;//当前值
Link<ET> previous, next;//上一个,和下个链表对象的引用
Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
普通添加方法
真正是由该方法实现,新元素添加在链表的最后,addLast同样是这个方法实现
将上一个元素的head节点指向新元素
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;
//新元素的头指向上一个元素,尾指向链表的头部
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
//头元素的头指向新元素
voidLink.previous = newLink;
//上一个结尾元素的尾 指向新元素
oldLast.next = newLink;
size++;
modCount++;
return true;
}
2.在指定位置插入
1.插入的位置要下于link链表的长度
2.向前后移动元数据,空出当前位置给新元素,上一个元素的next和下一个元素的head分别指向这个元素。
public void add(int location, E object) {
if (location >= 0 && location <= size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> newLink = new Link<E>(object, previous, link);
previous.next = newLink;
link.previous = newLink;
size++;
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}
查询
从头开始遍历链表元素的每一个元素。
public boolean contains(Object object) {
Link<E> link = voidLink.next;
if (object != null) {
while (link != voidLink) {
if (object.equals(link.data)) {
return true;
}
link = link.next;
}
} else {
while (link != voidLink) {
if (link.data == null) {
return true;
}
link = link.next;
}
}
return false;
}
删除
同样会遍历元素 找到对应位置上前后的元素,将之前该位置前后的连个元素链接首位链接起来。
@Override
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}