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

1
2

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 	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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
6
7
8
9
10
11
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    }

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