为什么使用迭代器iterator遍历Linkedlist要比普通for快

96 阅读 0 评论 64 点赞

我是靠谱客的博主失眠大侠，最近开发中收集的这篇文章主要介绍为什么使用迭代器iterator遍历Linkedlist要比普通for快，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

</pre><p></p><pre name="code" class="java">

大家可以搜索一下普通情况遍历linkedlist应该是O(n)但是使用iterator就是常数，这让我很好奇。于是我去查了源码。。

一路顺着找找到了Collection，确实有一个iterator但是是个interface还没有实现。

网上找list，有一个listiterator还是这样。

只能去linked找了，找到了如下源码

 	private static final class LinkIterator<ET> implements ListIterator<ET> {
61        int pos, expectedModCount;
62
63        final LinkedList<ET> list;
64
65        Link<ET> link, lastLink;
66
67        LinkIterator(LinkedList<ET> object, int location) {
68            list = object;
69            expectedModCount = list.modCount;
70            if (location >= 0 && location <= list.size) {
71                // pos ends up as -1 if list is empty, it ranges from -1 to
72                // list.size - 1
73                // if link == voidLink then pos must == -1
74                link = list.voidLink;
75                if (location < list.size / 2) {
76                    for (pos = -1; pos + 1 < location; pos++) {
77                        link = link.next;
78                    }
79                } else {
80                    for (pos = list.size; pos >= location; pos--) {
81                        link = link.previous;
82                    }
83                }
84            } else {
85                throw new IndexOutOfBoundsException();
86            }
87        }
88
89        public void add(ET object) {
90            if (expectedModCount == list.modCount) {
91                Link<ET> next = link.next;
92                Link<ET> newLink = new Link<ET>(object, link, next);
93                link.next = newLink;
94                next.previous = newLink;
95                link = newLink;
96                lastLink = null;
97                pos++;
98                expectedModCount++;
99                list.size++;
100                list.modCount++;
101            } else {
102                throw new ConcurrentModificationException();
103            }
104        }
105
106        public boolean hasNext() {
107            return link.next != list.voidLink;
108        }
109
110        public boolean hasPrevious() {
111            return link != list.voidLink;
112        }
113
114        public ET next() {
115            if (expectedModCount == list.modCount) {
116                LinkedList.Link<ET> next = link.next;
117                if (next != list.voidLink) {
118                    lastLink = link = next;
119                    pos++;
120                    return link.data;
121                }
122                throw new NoSuchElementException();
123            }
124            throw new ConcurrentModificationException();
125        }
126
127        public int nextIndex() {
128            return pos + 1;
129        }
130
131        public ET previous() {
132            if (expectedModCount == list.modCount) {
133                if (link != list.voidLink) {
134                    lastLink = link;
135                    link = link.previous;
136                    pos--;
137                    return lastLink.data;
138                }
139                throw new NoSuchElementException();
140            }
141            throw new ConcurrentModificationException();
142        }
143
144        public int previousIndex() {
145            return pos;
146        }
147
148        public void remove() {
149            if (expectedModCount == list.modCount) {
150                if (lastLink != null) {
151                    Link<ET> next = lastLink.next;
152                    Link<ET> previous = lastLink.previous;
153                    next.previous = previous;
154                    previous.next = next;
155                    if (lastLink == link) {
156                        pos--;
157                    }
158                    link = previous;
159                    lastLink = null;
160                    expectedModCount++;
161                    list.size--;
162                    list.modCount++;
163                } else {
164                    throw new IllegalStateException();
165                }
166            } else {
167                throw new ConcurrentModificationException();
168            }
169        }
170
171        public void set(ET object) {
172            if (expectedModCount == list.modCount) {
173                if (lastLink != null) {
174                    lastLink.data = object;
175                } else {
176                    throw new IllegalStateException();
177                }
178            } else {
179                throw new ConcurrentModificationException();
180            }
181        }
182    }
183

我们仔细察看next方法

public ET next() {
115            if (expectedModCount == list.modCount) {
116                LinkedList.Link<ET> next = link.next;
117                if (next != list.voidLink) {
118                    lastLink = link = next;
119                    pos++;
120                    return link.data;
121                }
122                throw new NoSuchElementException();
123            }
124            throw new ConcurrentModificationException();
125        }
126

这里里面有一个类是叫link，代码如下

private static final class Link<ET> {
49        ET data;
50
51        Link<ET> previous, next;
52
53        Link(ET o, Link<ET> p, Link<ET> n) {
54            data = o;
55            previous = p;
56            next = n;
57        }
58    }

可见list就是一个双向链表的link，没有什么特殊之处。到这里我彻底懵逼了，为什么呢为什么呢，为什么你遍历就是常数呢？

我们仔细对比一下for循环

for(int i =0;i<list.size();i++){
  list.get(i);
}

但是iterator和他对比起来少了一个list.get(i);其实就遍历而言它们两个差距并不大。但是其中调用了一次get(i).这个时间复杂度应该是O（n）所以嵌套一个for循环是O（n^2），但是在iterator中因为next的存在get当前项不需要时间所以循环下来应该是O（n），原来差距就在get和iterator这里了