1、数据结构
LinkedList是用双向链表的形式来保存数据的，也是一个有序结构。其中包含3个属性，int size(集合实际保存的元素个数)，Node<E> first(第一个节点)，Node<E> last(最后一个节点)。
2、线程安全
LinkedList是线程不安全的。
3、常用方法
～、节点Node<E>
Node<E>是构成双向链表的节点，是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;
}
}
// 在链表最前添加
private void linkFirst(E e) {
final Node<E> f =first;
final Node<E> newNode = new Node<>(null, e, f)
first = newNode;
if(f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
// 在链表最后添加元素
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++;
}
// 在某个节点之前添加
void linkBefor(E e, Node<E> succ) {
// 插入位置的前一个节点
final Node<E> pred = succ.prev;
// 用插入位置前一个节点pred、插入元素e、插入位置本来的节点succ，作为参数生成的新节点
// pred为新节点的前节点prev，succ为新节点的后节点next
final Node<E> newNode = new Node<>(pred, e, succ);
// 原插入位置的节点的前节点指向新节点
succ.prev = newNode;
if (pred == null)
first = newNode;
else
// 前节点的后节点指向新节点
pred.next = newNode;
size++;
modCount++;
}
～、add() // 在最后添加
public boolean add(E e) {
linkLast(e);
return true;
}
～、add(int index, E element) //在指定的index位置添加
public void add(int index, E element) {
// 保证index大于0，小于list.size()
checkPositionIndex(index);
if (index == size)
// 最后插入，同add()
linkLast(element);
else
// 中间插入，需要返回index位置的节点
linkBefor(element, node(index));
}
// 返回index位置节点
Node<E> node(int 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;
}
}
～、addFirst(E e) // 在最前面添加
public void addFirst(E e) {
linkFirst(e);
}
～、addLast(E e) // 在最后添加
public void addLast(E e) {
linkLast(e);
}
～、addAll(Collection<? extends E> c) //在链尾添加集合
先将c转为数组a，再将a中的元素一个一个按add()往后添加了
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c)
}
～、addAll(int index, Collection<? extends E> c) // 在指定位置添加集合
1、c转数组a
2、取原链表index位置元素succ和它的前一个元素pred
3、循环a取元素o，用pred、o、null生成新节点newNode。pred.next节点指向newNode，newNode赋给pred
4、将循环玩的最后一个节点pred.next指向第二步中的succ，succ.prev指向pred
～、get(int index) // 获取index位置存放的元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
～、getFirst()，getLast() // 获取第一、最后一个元素
判断first，last是否为空，不为空return first.item或last.item
～、set(int index, E element) 替换index位置的节点的元素item
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
～、删除节点-unlink
// 删除第一个节点
private E unlinkFirst(Node<E> f) {
// 取第一个节点的元素item和下一个节点next
final E element = f.item;
final Node<E> next = f.next;
// 将取出的第一个元素给null，使GC生效
f.item = null;
f.next = null;
// 第一个节点后移
first = next;
if ( next == null)
last = null;
else
next.prev = null;
size—;
modCount++;
return element;
}
// 删除最后一个节点
private E unlinkLast(Node<E> l) {
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null;
last = prev;
if(prev == null)
first == null;
else
prev.next = null;
size—;
modCount++;
return element;
}
// 删除节点
E unlink(Node<E> x) {
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;
}
～、remove() // 从头开始删除一个元素
public E remove() {
// unlinkFirst
return removeFirst();
}
～、removeFirst，removeLast //删除第一或最后一个元素
判断不为空后unlinkFirst或unlinkLast
～、remove(Object o) //删除第一次出现的与o相等的元素
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
～、remove(int index) //删除指定位置的元素
public E rmove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
网友评论