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

18258170717 发表于 2015-4-8 18:12
男神好屌！

别扯淡了，没人觉得难         

追赶进度 自我监督！！！！

因为自己犯二，Lab3也折腾了好一阵_(:зゝ∠)_
继续加油

交LAB~~~~~~~~~~~~

加油呀

先贴图：

题目意思好绕，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，然后不用分情况讨论了，略了；

为何明明简单的lab我还做得如此内牛满面。。。。心碎

链表恐惧症表示还是有难度的。。我来拉低本帖智商＝ ＝
最后确实是概念理解问题。。后面一直有错是因为我在insertFront里面非空时也写了tail＝ tail.next，确实无语。。。