LinkedList源码理解
LinkedList源码
0.首先这个类中的两个变量
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
下面的这个size就不用说了,是大小,现在先着重看看 Entry<E> header,
Entry是一个内部类。
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
就是一个链表,有父节点和子节点,父子节点都是一个对象的引用。
还有就是这个类是LinkedList的内部类,所以变量自然能再外部直接调用了。
1.构造函数
这个对象在声明的时候已经new了一个对象,所以这里可以直接使用里面的方法
节点的子节点和父节点都自己。
//无参构造
public LinkedList() {
header.next = header.previous = header;
}
这里是无参构造后header的示意图,父子节点都指向自己。只是最初的header对象。
这里所指向的“一个对象”在初始化中为null 。并且没有改变过。
//有参构造
public LinkedList(Collection<? extends E> c) {
//这一句可不能忘,对头节点的初始化很重要。
this();
addAll(c);
}
在有了添加元素的操作后,entry的指针会指向不同地方。
2.add方法
这个方法主要是讲原来
返回是否成功
public boolean add(E e) {
addBefore(e, header);
return true;
}
private Entry<E> addBefore(E e, Entry<E> entry) {
//新建一个节点,子节点是头结点,这样看来它是环形链表。
//它的父节点在第一次添加的时候是头结点,以后会得到最后一次添加的节点,并且在下面会断开后重连。
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
//新节点的上一个节点的子节点设置为新的节点
newEntry.previous.next = newEntry;
//新节点的下一个节点的父节点设置为新的节点
newEntry.next.previous = newEntry;
//大小++
size++;
//这个不知道
modCount++;
//返回新的节点。
return newEntry;
}
//在第几个位置添加
public void add(int index, E element) {
//如果在最后的位置添加,直接和上面的添加一样,如果不是,则
addBefore(element, (index==size ? header : entry(index)));
}
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
//取得头结点
Entry<E> e = header;
//循环节点,从头节点开始循环,这个处理很聪明,先计算index的大小,小于一半的话正向遍历,大于一半的话反向遍历。
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
//最后返回节点。
return e;
}
//添加到第一个位置
public void addFirst(E e) {
//只是在header的下一个开始添加,不多看了。
addBefore(e, header.next);
}
public void addLast(E e) {
//这个和add方法一样,所以普通的添加方法也是添加到最后的位置。
addBefore(e, header);
}
这个是完整的情况,添加,删除都会断开相应的next和previous。同时注意header内部的element不会存储元素。他所指向的对象是null ,在前面也说过。
3.remove
主要是讲要删除元素的Entry调整父子节点就可实现删除。
public E remove() {
return removeFirst();
}
public E removeFirst() {
return remove(header.next);
}
private E remove(Entry<E> e) {
//不能删除头节点
if (e == header)
throw new NoSuchElementException();
//这个是用来返回的
E result = e.element;
//父节点的子节点指向e的子节点。
e.previous.next = e.next;
//子节点的父节点指向e的父节点
e.next.previous = e.previous;
//将e设为空。
e.next = e.previous = null;
e.element = null;
//大小--
size--;
modCount++;
return result;
}
删除元素。这里面的匹配和indexof方法很像。在indexof里面讲。
public boolean remove(Object o) {
if (o==null) {
for (Entry<E> e = header.next; e != header; e = e.next) {
if (e.element==null) {
remove(e);
return true;
}
}
} else {
for (Entry<E> e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
4.indexOf
//还是对equals比较
,都是正向循环。没什么新意,循环到头指针后结束。
public int indexOf(Object o) {
int index = 0;
if (o==null) {
for (Entry e = header.next; e != header; e = e.next) {
if (e.element==null)
return index;
index++;
}
} else {
for (Entry e = header.next; e != header; e = e.next) {
if (o.equals(e.element))
return index;
index++;
}
}
return -1;
}
还有一些找第几个元素,返回元素数量,找到头元素,找都最后元素。