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

Lab不加分
但大家还是可以上传作业输出 保持进度
或者在相应lab贴里进行相关知识点的讨论

我看的是06年的视频
所以开始做06年的作业
看了一下  这次作业 14年和06年的要求是一样的
是关于双链表的作业
大家看完第8课视频就可以写了

作业链接：   http://www.cs.berkeley.edu/~jrs/61bf06/lab/lab4/

相关链接：      

       【公开课讨论+加分总贴】：UC Berkeley CS 61B Data Structures(in Java)
       【课程网站】：http://www.cs.berkeley.edu/~jrs/61b/
       【视频网站】:【Youtube】【Youku】
        【教材】：Head First Java 【中文版】【英文版】
                      Data Structures and Algorithms in Java, 5th Edition. 【英文版】

lab 4

似乎有sentinel比无sentinel的好处就是，insert的时候不用讨论链表为空的情况，remove的时候不用讨论链表为1的情况，因为有sentinel的链表可以将head的prev和next指向head本尊。但是remove还是需要讨论链表是否为空，因为不能把head删掉啊~





no sentinel:

sentinel:

1. /Library/Java/JavaVirtualMachines/jdk-9.0.4.jdk/Contents/Home/bin/java "-javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=52029:/Applications/IntelliJ IDEA CE.app/Contents/bin" -Dfile.encoding=UTF-8 -classpath /Users/Lim/@inbox/cs61b14/lab/lab4/out/production/lab4 DList1
   
2. ### TESTING insertFront ###
   
3. Empty list is [  ]
   
4. 
   
5. Inserting 9 at front.
   
6. List with 9 is [  9  ]
   
7. 
   
8. Inserting 8 at front.
   
9. List with 8 and 9 is [  8  9  ]
   
10. 
    
11. 
    
12. ### TESTING removeFront ###
    
13. List with 1 and 2 is [  1  2  ]
    
14. 
    
15. Removing front node.
    
16. List with 2 is [  2  ]
    
17. 
    
18. Removing front node.
    
19. Empty list is [  ]
    
20. 
    
21. Removing front node.
    
22. Empty list is [  ]
    
23. 
    
24. Process finished with exit code 0

复制代码

1. /Library/Java/JavaVirtualMachines/jdk-9.0.4.jdk/Contents/Home/bin/java "-javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=51938:/Applications/IntelliJ IDEA CE.app/Contents/bin" -Dfile.encoding=UTF-8 -classpath /Users/Lim/@inbox/cs61b14/lab/lab4/out/production/lab4 DList2
   
2. ### TESTING insertFront ###
   
3. Empty list is [  ]
   
4. 
   
5. Inserting 9 at front.
   
6. List with 9 is [  9  ]
   
7. 
   
8. Inserting 8 at front.
   
9. List with 8 and 9 is [  8  9  ]
   
10. 
    
11. 
    
12. ### TESTING removeFront ###
    
13. List with 1 and 2 is [  1  2  ]
    
14. 
    
15. List with 2 is [  2  ]
    
16. 
    
17. Empty list is [  ]
    
18. 
    
19. Empty list is [  ]
    
20. 
    
21. Process finished with exit code 0
    

复制代码

总结下：
（2）Dlist1的remove需要考虑size==1的情况，移除唯一的元素后，head = null， 这时候 head.prev 是不存在的，因为null既不是对象也不是一种类型，它仅是一种特殊的值。同时也必须对tail进行讨论，使得tail = null，不然java可能不能回收这个空间。
（1）Dlist2有了sentinel后可以避免上述的讨论

总结 下来就是 在 singly linked list里面如果要 remove，需要考虑size =1 的时候的特殊情况，在doubly linked list里面就不需要考虑这个情况。

字数字数！！

lab4.png
               

终于做完了！！

SList s=new TailList();
s.insertEnd(obj);
为啥就不能换成object了，insertEnd()不是用的tailList的method么？

所以是compiletime就不会通过，ok明白了

完成啦~~~ LAB4

LAB4的solution

晒一下答案~
希望自己能坚持下去

结果

但是对那个Insertfront size == 0 的代码不够简练。。。