cs61b系列day2——Proj1A

概要

今天的主题是list(表)。

• Reading2.1中先是描述了一种递归定义的链表——IntList，并提供了一些单元测试以帮助我们完善IntList的实现，同时首次介绍了reference type（引用类型）的定义。
• Reading2.2中：
  • 为了解决IntList难以使用的特点，创造了新的类SLList，而IntList则作为Nested class，仅提供一些必要的接口供SSList使用。
  • 为了解决size方法效率低下的问题，采用了caching的方法。
  • 为了解决处理特殊情况（如删除第一个结点）时代码繁杂的问题，引入了Sentinel Nodes（DDList也同样能有Sentinel Nodes）。
  • 为了避免用户操作不当以及减小接口的复杂程度，介绍了private关键字。
  • 为了解决数据类型单一的问题，首次介绍了Generics（泛型）。
    最后，我们也应该关注书中构建数据结构并一步步改进的思维。
• Project1A中，要求我们实现Deque（双端队列）的链表实现，只提供了少量测试，更多的测试需要自己编写。

一些感受

我不想在文章中包含太多的细节，复习时对照着代码，不懂的就到官网查。

1. 指针的特点：p->next->prev与p的区别
2. 实现数据结构时一定一定要画图（很多次不信邪了）
3. 有关Sentinel node的重要作用。
4. Java中实现数据结构的特点
   1. 利用子类
   2. 利用this（在递归中）
   3. 继续强调static和private关键字的重要性
5. 如何做简单的单元测试
6. 代码风格

---

拓展

1. The Rise and Fall of Pointer Arithmetic in the Evolution of Memory Management
2. The Law of the Broken Futon