赞
踩
LinkList 和ArrayList的区别在于LinkList底层是以链表实现的,ArrayList是与数组数据结构存在
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;
}
}
transient int size = 0;//当前链表长度
transient Node<E> first;//链表的第一个元素
transient Node<E> last;//链表的最后一个元素
public LinkedList() {//空的构造方法
}
public LinkedList(Collection<? extends E> c) //插入集合的构造方法
this();
addAll(c);
}
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<E> 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<E> 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;
}
Node<E> node(int index) {//获取传入下标对应位置的元素
// assert isElementIndex(index);
if (index < (size >> 1)) {//当传入下标小于链表集合长度的1/2时,从第一个元素开始遍历找到对应下标元素
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {///当传入下标大于链表集合长度的1/2时,从第最后一个元素向上开始遍历找到对应下标元素
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
获取第一个元素方法
public E getFirst() {//获取第一个元素方法
final Node<E> f = first;//从全局变量中获取第一个节点
if (f == null)
throw new NoSuchElementException();
return f.item;// 获取节点的值
}
public E getLast() {//获取全局变量中最后一个节点
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;// 获取最后一个节点元素
}
public E removeFirst() {//删除第一个元素
final Node<E> f = first;// 从全局变量中获取第一个元素
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {// 解绑第一个节点
// assert f == first && f != null;
final E element = f.item;// 获取第一个元素
final Node<E> next = f.next;//获取第一个节点的下一个节点
f.item = null; //把第一个节点元素和指向下一个节点设为null,让垃圾自动回收
f.next = null; // help GC
first = next; //把第一个节点的下一个节点赋值给第一个节点
if (next == null)
last = null;
else
next.prev = null;//第一个节点的下一个节点指向的上一个节点设为null,因为它已经是第一个节点
size--;
modCount++;
return element;
}
public E removeLast() {// 删除链表的最后一个
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);//
}
private E unlinkLast(Node<E> l) {//删除链表最后一个节点
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;//获取最后一个节点的上一个节点
l.item = null;
l.prev = null; // help GC
last = prev; // 链表的最后个节点设置为当前最后一个节点的上一个节点
if (prev == null)
first = null;
else
prev.next = null;// 最后一个节点的指向下一个节点设为null
size--;//
modCount++;
return element;
}
public void addFirst(E e) {// 添加第一个节点
linkFirst(e);
}
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;//当在添加节点前链表为null的时候,最后一个节点也是设为当前节点
else
f.prev = newNode;//把原来第一个节点的上一个节点设置为当前节点
size++;
modCount++;
}
public boolean contains(Object o) {//链表中是否包含o元素
return indexOf(o) != -1;
}
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {//从第一个元素开始依次遍历查找是元素是否存在
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。