这两天在看CS61A的同时，一直在反复翻阅SICP with Python, 关于编程理念最基本的东西真是怎么看也看不够。 特别是递归里边，如何用N种硬币来表示一个数字的这类问题，总是创建不出来对应的抽象。普通的处理一批数据的递归倒还可以。
CS61A现在听完了Python的部分，进入了第三章解释器，不过很多问题真的不想到头疼就写不出来。
另外就是抽象的问题，习惯了面向对象之后，像CS61A课程中直接采取list或者元组进行树的抽象，还是需要仔细品味一下的。对于一个问题，如何将其抽象成可以用计算机解决的问题，似乎也是一大壁垒，只能靠多算多练才行。
所以综合来看，CS61A讲的不是具体某种语言，而是程序设计的基本理念和如何跨越抽象壁垒的问题。至于使用什么语言，由于教学需要，Python可以将函数当成一等对象，所以用来学习这个理念很好。不过函数闭包实际上相当于面向对象，所以用面向对象也可以解决。
好了，不废话了，还是继续看Java的数据结构，数据结构也是抽象到极致的东西，只要搞明白了，用各种语言都能写出来。
另外昨晚我录制好了讲解递延所得税的视频，如果你或者你的朋友从事财务行业，或者要考CPA，可以推荐他们看看这个视频，一定会如醍醐灌顶般爽快。
线性表
从一开始，我们一直挥舞着两把兵器，右手一把弹簧刀一样的数组，左手一条金丝软鞭链表。用这两把武器硬生生砍下了包，栈，队列等数据结构。
回头仔细一想，不管是数组还是链表，看上去都是一串东西，是线性的。现在就来看看一个通用的数据结构，叫做线性表。
一个线性表，一般支持如下操作：
- 在任何位置添加一个项目
- 在任何位置删除一个项目
- 删除所有（清空）表
- 替换某一项
- 查看任意位置的项
- 查看全部项
- 检测是否包含某一项
- 检测计数
- 查看是不是空
实际上，线性表就像是一排东西，这些东西本身不一定有序，但是有序号。前边的队列，实际上并不是真的像现实中的队列。现实中的队列，会出现插队，换人，走人，队伍解散，在队伍里找人出来等等操作。
所以线性表，更像是一个非常通用的存放某种类型的容器，只要你按照某种线性表支持的操作来进行操作，线性表可以成为栈，包，双向队列等任何一个。
根据上边的功能，可以写出接口如下：
public interface ListInterface<；T> {
//在末尾添加元素
void add(T entry);
//在指定的位置添加元素
void add(int newPosition, T newEntry);
//删除某个位置的元素
T remove(int givenPosition);
//清空表
void clear();
//替换指定位置的元素
T replace(int givenPosition, T newEntry);
//获取指定位置的元素
T getEntry(int givenPosition);
//获取全部元素
T[] toArray();
//是否含有某个元素
boolean contains(T anEntry);
//获取其中的元素数量
int getLength();
//是否为空
boolean isEmpty();
}
因为有了可以获取其中数量的方法，以及可以从指定位置中获取内容的方法，不难想象，线性表的使用者只要按照规定的操作，就可以用线性表模拟出包，栈，队列的行为。所以线性表更加通用。
Java中的线性表
Java中的线性表的接口是java.util.List<T>接口，
查看JDK8的List文档可以看到除了抽象类之外，有如下几个类实现了接口：
ArrayList extends AbstractList<E> implements List<E>AttributeList extends ArrayList<Object>CopyOnWriteArrayList<E> extends Object implements List<E>LinkedList<E> extends AbstractSequentialList<E> implements List<E>RoleList extends ArrayList<Object>RoleUnresolvedList extends ArrayList<Object>RoleUnresolvedList extends ArrayList<Object>Vector<E> extends AbstractList<E> implements List<E>Stack<E> extends Vector<E>
可以看到最基础的东西就是List接口以及最基本的实现ArrayList和LinkedList, CopyOnWriteArrayList则是一个并发安全的版本.
这里要提一下,之前我们编写的所有数据结构, 都是线程不安全的, 只要多线程操作就会有危险. 解决方法可以将其在外边套一个安全的同步方法,也可以由使用数据结构的人自行编写线程安全的方法.这个以后等看到并发再讨论.
看来实现也不外乎两种, 一种是数组实现, 一种是链表实现. 那么就来干吧.ArrayList可以看到其文档中说支持null元素, 我们就以此为目标来先写一个数组实现的线性表.
数组实现线性表
数组实现线性表的方法, 其实我们在之前把核心的一些方法都写过了.这里首先创建一个类, 然后是基础设施, 其中最关键的,就是有一个记录线性表中已经有多少个元素的变量. 有了这个变量, 就可以快速的定位到数组的最末端.从而给很多操作带来便利.
public class MyArrayList<；T> implements ListInterface<；T> {
//内部数组
private T[] list;
private int numberOfEntries;
private boolean initialized;
private static int DEFAULT_CAPACITY = 16;
private static int MAX_CAPACITY = 10000;
private void checkInitialized() {
if (!initialized) {
throw new RuntimeException("类没有初始化成功.");
}
}
}
这几个变量都很熟悉了, 之前在编写变长数组的数据结构时候全都使用过. 然后编写构造器.
//根据传入的初始长度创建内部数组, 最小不短于默认长度
@SuppressWarnings("unchecked")
public MyArrayList(int size) {
if (size > MAX_CAPACITY) {
throw new RuntimeException("超过限制");
} else if (size < DEFAULT_CAPACITY) {
size = DEFAULT_CAPACITY;
}
System.out.println(size);
list = (T[]) new Object[size];
initialized = true;
}
public MyArrayList() {
this(DEFAULT_CAPACITY);
}
之后来逐个实现这些方法, 有很多实际上就是变长数组的方法. 然后来逐个实现该方法.
先要实现的方法就是判断数组是不是放满, 空, 以及扩展数组长度的内部私有方法, 这些方法在之后都会被用到.
@Override
public int getLength() {
checkInitialized();
return numberOfEntries;
}
@Override
public boolean isEmpty() {
checkInitialized();
return numberOfEntries == 0;
}
private boolean isFull() {
checkInitialized();
return numberOfEntries == list.length;
}
@SuppressWarnings("unchecked")
private void enlargeCapacity() {
int currentNumber = list.length;
if (currentNumber == MAX_CAPACITY) {
throw new RuntimeException("线性表无法继续扩大");
} else {
//创建一个最长不超过MAX_CAPACITY的数组, 然后将数组复制过去
T[] tempArray = (T[]) new Object[Math.min(currentNumber * 2, MAX_CAPACITY)];
if (numberOfEntries >= 0) System.arraycopy(list, 0, tempArray, 0, numberOfEntries);
list = tempArray;
}
}
判断线性表为空的方法自然是当前元素数量为0,判断满的方法则是当前元素的数量与数组的长度一样, 这时候不扩展就放不下了.
扩展数组的方法则是检测当前的长度, 如果已经最大就抛异常. 如果没有满, 则创建一个当前数组的2倍但不超过MAX_CAPACITY的数组, 并将数组元素复制到这个新数组中, 用新数组取代原来的数组.
扩展数组的过程中不涉及任何操作元素数量的操作.
有了上边这些方法辅助, 就可以来写一些核心的方法, 首先是add方法,默认向尾部添加. 向尾部添加之前, 需要检查数组是不是满了, 如果满了就扩展数组, 然后再添加. 我们的扩展数组方法可以保证只要不抛异常, 必定可以新添加一个元素.
@Override
public void add(T entry) {
checkInitialized();
if (isFull()) {
enlargeCapacity();
}
list[numberOfEntries] = entry;
numberOfEntries++;
}
然后是在指定位置添加的方法. 依然需要先判断数组是不是已经满了. 之后需要将指定位置索引开始的元素全部往后移动一个位置, 再将新元素放进去. 移动位置正好可以通过numberOfEntries来进行操作.
@Override
public void add(int newPosition, T newEntry) {
//要添加的位置最多也就是numberOfEntries的位置, 所以要检查一下参数
if (newPosition > numberOfEntries) {
throw new RuntimeException("索引不合法");
}
if (isFull()) {
enlargeCapacity();
}
//已经知道扩展后的数组必定至少还能放下一个元素. numberOfEntries指向的是数组最后一个元素之后的空白位置, 从这里反向往前循环即可.
int currentIndex = numberOfEntries;
while (currentIndex != newPosition) {
list[currentIndex] = list[currentIndex - 1];
currentIndex--;
}
//将元素全部向后移动一位之后再放入新元素
list[newPosition] = newEntry;
numberOfEntries++;
}
添加元素好了, 然后来编写删除指定位置元素的方法, 逻辑正好和添加反过来, 先获取这个元素, 再将其后的所有元素往后移动一个位置.
@Override
public T remove(int givenPosition) {
checkInitialized();
//检查指定的索引是否存在, 当有n个元素的时候, 最小只能是0, 最大的范围是n-1
if (givenPosition < 0 || givenPosition > numberOfEntries - 1) {
throw new RuntimeException("指定的索引超出范围");
}
T result = list[givenPosition];
//从指定的索引开始, 将之后的都往前移动一个位置
int currentIndex = givenPosition;
while (currentIndex != numberOfEntries - 1) {
list[currentIndex] = list[currentIndex + 1];
currentIndex++;
}
numberOfEntries--;
return result;
}
由于不用缩小数组, 这里方便了很多. 然后又可以编写一批小的方法:
@Override
public void clear() {
//clear只需要将numberOfEntries设置为1即可,无论是控制放入, 还是返回内部数组, 都是根据numberOfEntries来控制的. 不过最好还是将所有的位置都释放掉
checkInitialized();
for (int i = 0; i < numberOfEntries; i++) {
list[i] = null;
}
numberOfEntries = 0;
}
@Override
public T getEntry(int givenPosition) {
checkInitialized();
return list[givenPosition];
}
@Override
@SuppressWarnings("unchecked")
public T[] toArray() {
checkInitialized();
T[] result = (T[]) new Object[numberOfEntries];
System.arraycopy(list, 0, result, 0, numberOfEntries);
return result;
}
@Override
public T replace(int givenPosition, T newEntry) {
checkInitialized();
T result = list[givenPosition];
list[givenPosition] = newEntry;
return result;
}
由于内部是数组, 定位和查找都非常方便. 现在只剩最后一个方法了, 就是contains方法.
这个方法很显然, 需要遍历数组, 查找与给定对象相同的元素才可以, 一旦查找到, 就返回True,否则返回False.
@Override
public boolean contains(T anEntry) {
for (int i = 0; i < numberOfEntries; i++) {
if (list[i].equals(anEntry)) {
return true;
}
}
return false;
}
至此, 就写好了一个线性表, 其实仔细分析的话, 其相比原来的变长数组, 就多了从指定位置删除和添加元素的功能, 外加上查找, 就构成了线性表. 实现完了之后, 简单分析一下数组实现的性能:
add(T newEntry)方法,很显然, add方法会在某些时候涉及到扩大数组的操作, 这个操作是O(n)的, 如果不涉及扩大数组,则操作是常数级别. 线性表的使用者控制好数据量, 可以避免O(n)的操作add(int newPosition, T newEntry)方法, 这个方法在最坏的时候, 会先扩大一次数组, 然后从头开始移动数组的每一个元素, 因此其实际上是2n级别的复杂度, 也是O(n)级别.remove方法也需要调整元素的位置, 最好的是在末尾移除, 最坏的则是在头部移除. 不管怎么说, 也是O(n)级别的复杂度.contains(T anEntry)方法需要遍历, 不用说了, 也是O(n)级别的复杂度.- 其他辅助方法中, 为了隔离, toArray()返回一个新数组, 很显然也是O(n)复杂度的方法. 不过这个不能阻止修改引用, clear我们也采用了安全的O(n)级别方法. replace和getEntry则是常数级别的.
通过以上的分析可以看出, 为了获取线性表的灵活性, 我们所有添加和删除以及查找方法, 全部都提高到了O(n)级别的复杂度,几乎所有核心操作都是O(n)级别的复杂度. 这和之前的包,栈,队列都有所不同. 但显然, 线性表更加通用和灵活. 这就是以提高复杂度换来的灵活性.
链表实现线性表的思考
既然已经用数组编写好了线性表， 现在就要看一下如果改用链表会如何。列出来对应各个方法的思路：
- 在链表的尾部添加元素，在之前的队列可以知道，如果不维护一个尾引用，则添加的操作是O(n)，如果维护一个尾引用，则可以将其变成常数级别， 但是需要额外的逻辑来控制。
- 在指定的位置添加索引，这个就不像数组一样可以直接找到索引，而是必须从链表往后走指定的距离，而且插入链表还有一个问题，就是要获取之前的一个节点才可以。如果不想使用双向节点，仅使用普通链表，则需要注意编写逻辑。是O(n)复杂度。
- 从指定的位置删除节点， 这个和添加节点是类似的，也需要获取要删除的位置的前一个节点。因为要走到指定的位置， 所以也是O(n).
- 获取指定索引的元素， 这个由于不像数组，可以发现这个方法的复杂度要比数组实现的链表高，也是O(n)级别。
- 查找，需要遍历所有节点，和数组一样是O(n)级别
链表实现相比数组实现，可以实现改进的地方是添加元素永远不会发生像数组那样扩容数组的操作。但因为这种操作不是经常发生，所以提升不是非常大。其他的方法，都具有相同的时间复杂度。
所以整体来说，用链表实现和用数组实现差异不大，好处更在于链表不会浪费空间，但链表本身单个节点存储的数据更多，还依赖于具体的内存使用状况，所以差异不大。
链表实现线性表
依然使用之前的内部类Node,从之前的分析可以知道，我们维护三个域：首节点，尾节点和链表内的元素数量。基础设施如下：
public class MyLinkedList<；T> implements ListInterface<；T> {
private class Node {
private T data;
private Node next;
public Node(T data) {
this(data, null);
}
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}
private Node firstNode;
private Node lastNode;
private int numberOfEntries;
public MyLinkedList() {
initialize();
}
private void initialize() {
firstNode = null;
lastNode = null;
numberOfEntries = 0;
}
@Override
public void clear() {
initialize();
}
@Override
public int getLength() {
return numberOfEntries;
}
@Override
public boolean isEmpty() {
return numberOfEntries == 0 && firstNode == null && lastNode == null;
}
}
由于链表的特性，这里定义了一个initialize()方法,用于清空链表. 这个方法可以同时用于初始化线性表和作为clear()方法的实际执行方法.
isEmpty()方法可以仅仅检测元素数量是否为0, 如果我们的逻辑编写正确的话, 是可以的, 在开发过程中可以加上其他检测以保证实现没出错, 比如firstNode和lastNode是不是同时为null.
下边先来编写add系列方法. 有点类似于之前编写的双端队列. 我们规定, 添加元素都是从链表的尾部添加.
@Override
public void add(T entry) {
//创建新节点
Node newNode = new Node(entry);
//如果线性表为空,要添加的节点同时是头节点和尾节点
if (isEmpty()) {
firstNode = newNode;
lastNode = newNode;
//如果不为空, lastNode一定不为空, 添加在尾部
} else {
lastNode.next = newNode;
lastNode = lastNode.next;
}
numberOfEntries++;
}
@Override
public void add(int newPosition, T newEntry) {
//添加在指定位置,显然需要先检查索引.
//思考最简单的例子,一个长度1的链表, 只可能添加在0或者1号位置, 所以newPosition <= numberOfEntries
if (newPosition > numberOfEntries) {
throw new RuntimeException("插入位置的索引不合法: " + newPosition);
}
//然后需要从头开始遍历链表, 遍历到要插入的位置之前一个位置
//这里需要考虑两种情况, 如果从0号位置插入,表示插入在链表头部. 如果从nubmerOfEntries位置插入, 表示从尾部插入, 剩下的就需要手工拼接一下
//0号位置插入的时候如果数组为空, 和普通插入一样
if (newPosition == 0) {
if (isEmpty()) {
add(newEntry);
//如果不为空, 则就是在链表头部添加节点
} else {
Node newNode = new Node(newEntry);
newNode.next = firstNode;
firstNode = newNode;
numberOfEntries++;
}
//如果索引和当前的元素数量相等,说明是从尾部插入, 也调用add方法即可
} else if (newPosition == numberOfEntries) {
add(newEntry);
//剩下的情况表示不是头也不是尾,那么就需要找到要插入的节点的前一个元素.
//简单分析一下,如果数组只有一个元素,插入点不是0就是1,会掉入上边两种情况.
//如果数组长度为2,符合条件的是1,在1号位置插入需要获取0号位置的节点. 如果数组长度是3,符合条件的是1,2号位置, 要获取的节点位置是0,1 所以可见,从开头循环到newPosition - 1的位置即可
} else {
Node currentNode = firstNode;
for (int i = 0; i < newPosition - 1; i++) {
currentNode = currentNode.next;
}
//循环结束后, currentNode指向要插入的位置的上一个节点, 然后插入新节点
Node newNode = new Node(newEntry);
newNode.next = currentNode.next;
currentNode.next = newNode;
numberOfEntries++;
}
}
有了插入方法之后, 再来编写remove方法. 这个方法要特别注意, 因为会存在删除之后数组为空, 或者删除数组的最后一个元素的情况.
@Override
public T remove(int givenPosition) {
T result = null;
//像检查数组索引一样检查给出的位置是否正确.
if (givenPosition < 0 || givenPosition > numberOfEntries - 1) {
throw new RuntimeException("指定的索引超出范围");
}
//然后需要处理几个特例: 线性表长度为1的情况; 删除链表最后一个位置上的元素的情况
//如果删除线性表的唯一一个元素, 则直接清除即可
if (numberOfEntries == 1 && givenPosition == 0) {
result = firstNode.data;
initialize();
return result;
}
//numberOfEntries不为1的情况下, 删除第一个节点
if (givenPosition == 0) {
result = firstNode.data;
firstNode = firstNode.next;
numberOfEntries--;
return result;
}
//如果删除的是线性表的最后一个元素, 需要获取到上一个元素, 然后记得要把lastNode更改掉
if (givenPosition == numberOfEntries - 1) {
Node currentNode = firstNode;
while (currentNode.next != lastNode) {
currentNode = currentNode.next;
}
//循环结束之后, currentNode.next = lastNode, 即currentNode是lastNode的前一个节点
result = lastNode.data;
currentNode.next = null;
lastNode = currentNode;
numberOfEntries--;
return result;
//这种情况就是numberOfEntries大于1, 而且又没有删除尾节点的情况, 依然从头开始遍历到索引-1的位置, 就获取了上一个节点.
} else {
Node currentNode = firstNode;
for (int i = 0; i < givenPosition - 1; i++) {
currentNode = currentNode.next;
}
//循环结束之后, currentNode指向要删除的节点的上一个节点
result = currentNode.next.data;
currentNode.next = currentNode.next.next;
numberOfEntries--;
return result;
}
}
这个remove方法主要是考虑的特殊情况比较多一些,分为线性表只有一个元素的时候删除, 超过一个元素的时候删除首节点. 以及删除尾节点的操作. 处理了特殊情况之后, 一般情况的遍历与添加节点本质上操作是相同的.
剩下的方法就简单了, 都是遍历链表就行了, 挨个来实现一下:
@Override
public T replace(int givenPosition, T newEntry) {
T result = null;
//检查位置的正确性
if (givenPosition < 0 || givenPosition > numberOfEntries - 1) {
throw new RuntimeException("指定的索引超出范围");
}
Node currentNode = firstNode;
for (int i = 0; i < givenPosition; i++) {
currentNode = currentNode.next;
}
result = currentNode.data;
currentNode.data = newEntry;
return result;
}
@Override
public T getEntry(int givenPosition) {
T result;
//检查位置的正确性
if (givenPosition < 0 || givenPosition > numberOfEntries - 1) {
throw new RuntimeException("指定的索引超出范围");
}
Node currentNode = firstNode;
for (int i = 0; i < givenPosition; i++) {
currentNode = currentNode.next;
}
result = currentNode.data;
return result;
}
@Override
public boolean contains(T anEntry) {
Node currentNode = firstNode;
while (currentNode != null) {
if (currentNode.data.equals(anEntry)) {
return true;
}
currentNode = currentNode.next;
}
return false;
}
@Override
@SuppressWarnings("unchecked")
public T[] toArray() {
T[] result = (T[]) new Object[numberOfEntries];
Node currentNode = firstNode;
for (int i = 0; i < numberOfEntries; i++) {
result[i] = currentNode.data;
currentNode = currentNode.next;
}
return result;
}
这几个方法全部都是遍历数组,毫无技术含量.
实现完了之后再来看一下, 各个方法的复杂度确实如我们所分析的, 对于链表, 在尾部插入和在头部删除是常数时间, 其他的所有操作全部都需要遍历链表, 就连替换和获取指定位置的元素, 也需要遍历链表, 导致复杂度比数组实现要高一些.
比较之后可以得出结论:
- 如果经常使用在尾部添加和在头部删除(像一个对象),则可以考虑使用链表
- 如果经常需要快速替换和获取指定位置的元素, 则可以考虑数组实现.
所以究竟选择Java类库中的ArrayList还是LinkedList,要根据实际场景而定.
这样我们就实现了一个非常灵活而且通用的线性表, 适合以线性方式存放数据, 并且根据不同的操作方式, 可以模拟包, 栈, 队列这些线性数据结构的全部行为. 当然, 代价就是控制逻辑的复杂以及各个方法复杂度的提升.
有了通用的线性表之后, 一般经常与线性表搭配使用的, 就是线性表的迭代器, 之后就回忆一下设计模式, 来给我们的线性表配上迭代器.
