public e get(int index) {
checkelementindex(index);//判断是否越界 [0,size)
return node(index).item; //调用node()方法 取出 node节点,
}
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;
}
public int lastindexof(object o) {
int index = size;
if (o == null) {
for (node<e> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (node<e> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
public iterator<e> iterator() {
return listiterator();
}
public listiterator<e> listiterator() {
return listiterator(0);
}
public listiterator<e> listiterator(final int index) {
rangecheckforadd(index);
return new listitr(index);
}
private class listitr extends itr implements listiterator<e> {
listitr(int index) {
cursor = index;
}
public boolean hasprevious() {
return cursor != 0;
}
public e previous() {
checkforcomodification();
try {
int i = cursor - 1;
e previous = get(i);
lastret = cursor = i;
return previous;
} catch (indexoutofboundsexception e) {
checkforcomodification();
throw new nosuchelementexception();
}
}
public int nextindex() {
return cursor;
}
public int previousindex() {
return cursor-1;
}
public void set(e e) {
if (lastret < 0)
throw new illegalstateexception();
checkforcomodification();
try {
abstractlist.this.set(lastret, e);
expectedmodcount = modcount;
} catch (indexoutofboundsexception ex) {
throw new concurrentmodificationexception();
}
}
public void add(e e) {
checkforcomodification();
try {
int i = cursor;
abstractlist.this.add(i, e);
lastret = -1;
cursor = i + 1;
expectedmodcount = modcount;
} catch (indexoutofboundsexception ex) {
throw new concurrentmodificationexception();
}
}
}
可以看到,其实最后使用的迭代器是使用的listiterator类,且集成自itr,而itr类就是我们昨天arraylist内部使用的类,hasnext()方法和我们之前的一样,判断不等于size大小,然后next()获取元素主要也是e next = get(i);这行代码,这样就又走到我们之前的获取元素的源码当中,获得元素值。
ok,这样我们上面的基本方法都看完了,再来看看我们上面遗留的问题,首先来看deque接口有什么作用,我们来一起看看
public interface deque<e> extends queue<e> {
void addfirst(e e);//插入头部,异常会报错
boolean offerfirst(e e);//插入头部,异常不报错
e getfirst();//获取头部,异常会报错
e peekfirst();//获取头部,异常不报错
e removefirst();//移除头部,异常会报错
e pollfirst();//移除头部,异常不报错
void addlast(e e);//插入尾部,异常会报错
boolean offerlast(e e);//插入尾部,异常不报错
e getlast();//获取尾部,异常会报错
e peeklast();//获取尾部,异常不报错
e removelast();//移除尾部,异常会报错
e polllast();//移除尾部,异常不报错
}
deque也就是一个接口,上面是接口里面的方法,然后了解deque就必须了解queue
public interface queue<e> extends collection<e> {
//往队列插入元素,如果出现异常会抛出异常
boolean add(e e);
//往队列插入元素,如果出现异常则返回false
boolean offer(e e);
//移除队列元素,如果出现异常会抛出异常
e remove();
//移除队列元素,如果出现异常则返回null
e poll();
//获取队列头部元素,如果出现异常会抛出异常
e element();
//获取队列头部元素,如果出现异常则返回null
e peek();
}
int indexedbinarysearch(list<? extends comparable<? super t>> list, t key) {
int low = 0;
int high = list.size()-1;
while (low <= high) {
int mid = (low + high) >>> 1;
comparable<? super t> midval = list.get(mid);
int cmp = midval.compareto(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}
int iteratorbinarysearch(list<? extends comparable<? super t>> list, t key)
{
int low = 0;
int high = list.size()-1;
listiterator<? extends comparable<? super t>> i = list.listiterator();
while (low <= high) {
int mid = (low + high) >>> 1;
comparable<? super t> midval = get(i, mid);
int cmp = midval.compareto(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}
linkedlist linkedlist = new linkedlist();
for(int i = 0; i < 100000; i++){
linkedlist.add(i);
}
// 迭代器遍历
long start = system.currenttimemillis();
iterator iterator = linkedlist.iterator();
while(iterator.hasnext()){
iterator.next();
}
long end = system.currenttimemillis();
system.out.println("iterator:"+ (end - start) +"ms");
打印结果:iterator:28ms for循环get遍历
// 顺序遍历(随机遍历)
long start = system.currenttimemillis();
for(int i = 0; i < linkedlist.size(); i++){
linkedlist.get(i);
}
long end = system.currenttimemillis();
system.out.println("for :"+ (end - start) +"ms");
打印结果 for :6295ms 使用增强for循环
long start = system.currenttimemillis();
for(object i : linkedlist);
long end = system.currenttimemillis();
system.out.println("增强for :"+ (end - start) +"ms");
输出结果 增强for :6ms removefirst来遍历
long start = system.currenttimemillis();
while(linkedlist.size() != 0){
linkedlist.removefirst();
}
long end = system.currenttimemillis();
system.out.println("removefirst :"+ (end - start) +"ms");
long start = system.currenttimemillis();
for (int i = 0; i < arraylist.size(); i++) {
arraylist.get(i);
}
long end = system.currenttimemillis();
system.out.println("for :"+ (end - start) +"ms");
输出结果 for :3ms arraylist的迭代遍历
long start = system.currenttimemillis();
iterator iterable = arraylist.iterator() ;
while (iterable.hasnext()){
iterable.next();
}
long end = system.currenttimemillis();
system.out.println("for :"+ (end - start) +"ms");