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

shi198 · 2017-11-20 04:35:29

总结一下就是有dummy node 的doubly linked list因为是一个circle 所以不用检验各种null pointer的情况了

dachou

无sentinel时，insertFront需要考虑链表是否为空，因为为空的时候，insertFront新的node之后tail和head都需要更新。removeFront的时候，需要考虑链表为空，和只有一个node和多个node三种情况。
有sentinel时候，insertFront不需要考虑链表是否为空的情况，因为一直都会有head节点，此时size=0。而removefront的时候需要考虑链表为空的情况，但是不需要考虑size=1的情况。

仙道彰 · 2017-12-25 22:55:24

花了一晚上才搞定了lab4……思路其实很简单，结果在用了sentinel的insertFront方法的几条语句的顺序上面晕了很久

keepgoing123

Lab4 对理解链表很有帮助
DList1

DList2

kaiwhu

Env: JDK 9.0.1

greatlim

/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
### TESTING insertFront ###
Empty list is [ ]
Inserting 9 at front.
List with 9 is [ 9 ]
Inserting 8 at front.
List with 8 and 9 is [ 8 9 ]
### TESTING removeFront ###
List with 1 and 2 is [ 1 2 ]
Removing front node.
List with 2 is [ 2 ]
Removing front node.
Empty list is [ ]
Removing front node.
Empty list is [ ]
Process finished with exit code 0

复制代码

/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
### TESTING insertFront ###
Empty list is [ ]
Inserting 9 at front.
List with 9 is [ 9 ]
Inserting 8 at front.
List with 8 and 9 is [ 8 9 ]
### TESTING removeFront ###
List with 1 and 2 is [ 1 2 ]
List with 2 is [ 2 ]
Empty list is [ ]
Empty list is [ ]
Process finished with exit code 0

复制代码

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

爱树上的兔子

本帖最后由爱树上的兔子于 2018-3-16 20:25 编辑

### TESTING insertFront ###
Empty list is [ ]
Inserting 9 at front.
List with 9 is [ 9 ]
Inserting 8 at front.
List with 8 and 9 is [ 8 9 ]
### TESTING removeFront ###
List with 1 and 2 is [ 1 2 ]
Removing front node.
List with 2 is [ 2 ]
Removing front node.
Empty list is [ ]
Removing front node.
Empty list is [ ]

复制代码

### TESTING insertFront ###
Empty list is [ ]
Inserting 9 at front.
List with 9 is [ 9 ]
Inserting 8 at front.
List with 8 and 9 is [ 8 9 ]
### TESTING removeFront ###
List with 1 and 2 is [ 1 2 ]
List with 2 is [ 2 ]
Empty list is [ ]
Empty list is [ ]

复制代码

Jason_Lee

本帖最后由 Jason_Lee 于 2018-3-22 16:25 编辑

Lab4
把DList1 & DList2放在一个lab里意思就是要对比分析分析吧。。
DList1是在SList上的一个拓展，Node增加了prev instance variable，head和tail的概念仍然没变，只是作为一个标签（变量），用来表征首尾两个node，方便对整个list进行access。
DList2是circularly linked list，存在sentinel，lab中用head作为变量名；与DList1不同，sentinel本身也是一个node处在list中，需要确定其next和prev。

简单来说，在DList1中，head是list中第一个node的变量名;DList2中，head自身是一个node对象，变量名是head。

算法上的区别：
DList2在insertFront和removeFront中都不需要讨论size==1的情况了。

结果图如下：
DList1

DList2

martinma

desperado721

DList2弄了好久，在网上找到的答案全部都是分了size=1和size>1的情况，而这是不符合要求的。最后强做，终于搞定了，其实只要两行代码，
1.把head.next指向head后面的后面的节点（head.next.next)
2.head后面的后面的节点的prev(head.next.prev，注意此时head.next已经是head后面的后面那个节点了，因为1已经把head.next重新定向了)指向head就可以了，因为是循环链表，当只有head和1时，head.next.next会指向她自己，结束

运行图

public void insertFront(int i) {
         // Your solution here.
         DListNode2 first = new DListNode2(i);
         head.next.prev = first;
         first.next = head.next;
         head.next = first;
         first.prev = head;
         size++;
      }

   public void removeFront() {
         // Your solution here.
         // finally, I did it
         if (size ==0){
            return;
         }else {
            head.next = head.next.next;
            head.next.prev = head;
            size--;
         }
      }

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

评分

浏览过的版块