Java基础之Collections框架List接口实现类LinkedList及其源码分析
- LinkedList简单使用
- LinkedList源码分析
-
- 构造函数
- 添加元素
- 添加指定集合中的元素到linkedList中
-
- 进行addAll操作
- 移除元素操作
-
- 移除所有的元素
- 移除元素(第一个)
- 移除元素(最后一个)
- 查询
-
- 设置值
- 降序迭代器
List和Deque接口的双链接列表实现。 实现所有可选的列表操作,并允许所有元素(包括null)。
所有操作都执行双链表所期望的操作。 索引到列表中的操作将从开头或结尾遍历列表,以更接近指定索引的位置为准。
LinkedList简单使用
List<String> linkedList = new LinkedList<String>();
//添加元素
linkedList.add("tony");
linkedList.add("shanghai");
System.out.println(linkedList.toString());
linkedList.add(1, "Hu Pudong");
System.out.println(linkedList.toString());
//移除元素
linkedList.remove("tony");
System.out.println(linkedList.toString());
//是否包含相关元素
System.out.println(linkedList.contains("shanghai"));
List<String> listemp = new ArrayList<String>();
listemp.add("tony");
listemp.add("nan ma tou");
//将指定集合中的元素添加到linkedList中
linkedList.addAll(listemp);
System.out.println(linkedList.toString());
LinkedList源码分析
上面对LinkedList简单使用,揭开添加,删除,包含等操作的内幕。
实例属性:
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 add(E e) {
linkLast(e);
return true;
}
//关联添加的用户
void linkLast(E e) {
//获取最后一个元素
final Node<E> l = last;
//l上一个元素,E当前元素 因为添加往后面追加,后面的元素为null
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
//如果没有最后一个元素,代表添加为第一个
if (l == null)
first = newNode;
else
//设置最后一个元素的后面一个为新的元素
l.next = newNode;
size++; //设置大小 + 1
modCount++;
}
//私有内部类 node,保存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;
}
}
添加指定集合中的元素到linkedList中
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
进行addAll操作
public boolean addAll(int index, Collection<? extends E> c) {
//检查索引的合法性,索引不能大于size和小于0
checkPositionIndex(index);
//将集合转为为数组
Object[] a = c.toArray();
int numNew = a.length; //获取集合的大小
if (numNew == 0)
return false;
Node<E> pred, succ;
//如果索引为链表的大小,设置相应的node
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index); //进行二分查找的方式获取node
pred = succ.prev; //获取查找到node的上一个节点
}
//通过遍历进行赋值
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;
}
//进行node赋值
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew; //扩大链表的大小
modCount++;
return true;
}
检索node:
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; //返回最后的值的下一个node
} else {
Node<E> x = last;
//如果大于的话,说明在链表的后半部分,后面开始遍历
for (int i = size - 1; i > index; i--)
x = x.prev;
return x; //返回最后的前一个元素
}
}
移除元素操作
移除所有的元素
public void clear() {
// 将节点设置为null,等待GC进行回收
//遍历获取一个一个的节点
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
移除元素(第一个)
public E remove() {
return removeFirst();
}
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;
f.next = null; // help GC
first = next; //将第一个元素设置为它的下一个元素 进行删除第一个node
if (next == null)
last = null;
else
next.prev = 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; //将最后一个元素元素设置为它的前一个元素 进行删除最后一个node
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
查询
//包含操作
public boolean contains(Object o) {
return indexOf(o) != -1;
}
public int indexOf(Object o) {
int index = 0;
if (o == null) {
//遍历node节点进行操作 每一个node都包含前一个节点和下一个节点
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; //查询不到返回-1
}
设置值
public E set(int index, E element) {
checkElementIndex(index); //检查元素的下标
Node<E> x = node(index); //进行二分查找进行下标索引,找到当前下标的node
E oldVal = x.item;
x.item = element;
return oldVal;
}
由于双向链表的还实现了Deque,所以还有相关的Deque的方法。
//添加元素
public void push(E e) {
addFirst(e); //push是从头进行添加
}
//移除元素
public E pop() {
return removeFirst(); //弹出元素,删除第一个元素
}
//返回第一个元素,但是不删除
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//删除第一个元素
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
还有一些队列的方法。相关的还有很多方法如迭代,比较等。这里会有一个迭代器为降序迭代器。
降序迭代器
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}