Data Structures and Algorithm Analysis in Java的学习笔记

Chapter2 算法分析

2.4.4 运行时间中的对数

欧几里得算法

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（greatest common divisor）缩写为gcd。

gcd(a, b) = gcd(b, a mod b)(不妨设a > b且r = a mod b, r≠0)

证明

Chapter 3 表、栈和队列

关于for循环里增删的思考

Effective Java Item58 推荐多使用for-each循环

for-each循环底层还是用的迭代器，通过反编译也可以看出。

不管是增强for循环还是普通for循环都不要在内部进行增删操作，前者会触发fast-fail机制，后者add操作内存会爆掉，remove操作索引会乱。

推荐使用显示迭代器的remove方法或者Java8增加的Collection的removeIf方法（底层也是迭代器）在循环中进行删除操作。

LinkedList源码解读

An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list. A ListIterator has no current element; its cursor position always lies between the element that would be returned by a call to previous() and the element that would be returned by a call to next(). An iterator for a list of length n has n+1 possible cursor positions, as illustrated by the carets (^) below:
                        Element(0)   Element(1)   Element(2)   ... Element(n-1)
   cursor positions:  ^            ^            ^            ^                  ^

Note that the remove and set(Object) methods are not defined in terms of the cursor position; they are defined to operate on the last element returned by a call to next or previous().

以上注释出自ListIterator源码

私有类ListItr实现了ListIterator双向迭代器，其中的remove方法line 927是针对previous的情形，另一分支则是next的情形。

队列的数组实现

循环数组（circular array）解决front或back在数组边界时对应dequeue或enqueue的情况。

zystrivego

Data Structures and Algorithm Analysis in Java