Berkeley CS 61B Data Structures(in Java) Lab3 讨论帖

lab3 和lab4都是看完第八课 链表 就可以写的
实验室里要求2个小时完成的，所以都比较简单
作业链接：http://www.cs.berkeley.edu/~jrs/61b/lab/lab3/

lab就不加分了

大家还是可以上传作业 mark一下自己做过了
或者做作业有什么问题
可在此帖讨论

相关链接：      

       【公开课讨论+加分总贴】：UC Berkeley CS 61B Data Structures(in Java)
       【课程网站】： 【spring2014】【fall2006】
       【视频网站】:【Youtube（fall2006）】【Youtube(spring2014)】【Youku(fall 2006)】
        【教材】：Head First Java 【中文版】【英文版】
                      Data Structures and Algorithms in Java, 5th Edition. 【英文版】

先贴图：

题目意思好绕，constant time就好了，后面说了一堆record， representation之类的， 感觉不如直接说keep track of the tail。。。
要改的三个是：加一个instance variable (tail)，insertFront(),  insertEnd();

人认为有两种实现带tail的linkedlist的思路：
1. head和tail指向的都是首末的有意义的node：
    优点：代码简洁，节约了两个node；
    缺点：insertFront()和insertEnd()里都要把tail==0拎出来单独讨论；
2. head和tail分别指的首末的无意义的（不存item）node，专门作首尾节点：
    优点：是课堂上讲的标准linkedlist结构
    缺点：代码稍微复杂一点，又因为是单向linkedlist，没有prev，所以尾node的next要往回指，容易弄错。。（事实上1中的node本身也是往回指的。。）

贴一下1的代码：

1. public void insertFront(Object obj) {
   
2.   head = new SListNode(obj, head);
   
3.   if (tail == null){
   
4.     tail = head;
   
5.   }
   
6.   size++;
   
7. }
   
8. 
   
9. public void insertEnd(Object obj) {
   
10.   if (tail==null){
    
11.     insertFront(obj);
    
12.   } else {
    
13.     tail.next = new SListNode(obj, null);
    
14.     tail = tail.next;
    
15.     size++;
    
16.   }
    
17. }

复制代码

2的代码就是把一些head和tail改成head.next和tail.next，然后不用分情况讨论了，略了；

LAB3

第一个问题还ok ~

小小总结一下第二个问题：

insertEnd函数是增加了一个尾指针tail。

在insertFront函数中特别注意，当空链表插入第一个节点时，tail也得指向这个节点。

中途糊涂了，以为是最后一个节点指向tail呢，其实tail只是一个变量名，而不是节点，tail所指向的内容才是节点。

第一次忘了在insertFront()里面添加tail == null的情况，应该想到对称性的。

there is something wrong with youtube link?

老师讲的
public void removeBack(){
head.prev=head.prev.prev;
head.prev.next=head;
size--;
}
没有错误吗?第三句 head.prev.next不是本来就是head?
觉得应该是
head.prev.prev.next=head;

朝仓音梦 发表于 2014-6-3 01:48
老师讲的
public void removeBack(){
head.prev=head.prev.prev;

没有错误 因为已经把head.prev.prev 赋值给了 head.prev
第一句话是 从 后往前 建立链接
第二句话是 从 前往后 建立链接

字数字数字数字数！

lab3.png
                                

insertEnd()方法的修改是不是添加一个结点时刻指向尾结点就可以了？

回ls，
我是加了一个tail 然后在insertend和insertfront里做判断，为head == null时，tail = head = 新元素；当insertend不为null时候，把tail.next装上去，再更新tail；

希望能坚持跟上。。。。。

晒一下答案~