Berkeley CS 61B Data Structures(in Java) Homework4 加分+讨论帖

DList:

file:\\D:\cs61b\hw4\DList.png
LockDlist:

file:\\D:\cs61b\hw4\LockDlist.png

放假太颓废了，惭愧惭愧 >_<.
现在开学了，补回来

本来打算寒假期间学晚的。。。
结果连java都没完。。开学恶补
【另外感谢楼主的test】

求加分~~

hw4DList1

DList2

LockDList

终于写好了 碰到了两个问题
一是 head construct 之后没有指向自己QAQ
二是 一开始没有理解LockDList的模式
override时parameter时LockDListNode（wrong）应该是DListNode（right）同理，LockDlstNode的constructor中也是。

1. Now we are testing DList.
   
2. Here is a list after insertBack 6, 9, 12: [  6  9  12  ]
   
3. 
   
4. Here is the same list after insertBack(15) and insertFront(3): [  3  6  9  12  15  ]
   
5. 
   
6. front() should be 3. It is: 3
   
7. front's next should be 6. It is: 6
   
8. front's next's prev should be 3. It is: 3
   
9. After remove the front, the front() should be 6. It is: 6
   
10. After insertBefore() and insertAfter(), The first 3 nodes should be 5,6,8. The list is: [  5  6  8  9  12  15  ]
    
11. 
    
12. Here is a list after construction: [  ]
    
13. isEmpty() should be true. It is: true
    
14. length() should be 0. It is: 0
    
15. Here is a list after insertFront(3) to an empty list: [  3  ]
    
16. Here is a list after insertBack(5) on an empty list: [  5  ]
    
17. 
    
18. Here is a list after insertFront 3, 2, 1: [  1  2  3  ]
    
19. isEmpty() should be false. It is: false
    
20. length() should be 3. It is: 3
    
21. Here is the same list after insertBack(4): [  1  2  3  4  ]
    
22. 
    
23. Here is a list after insertBack 6, 7: [  6  7  ]
    
24. isEmpty() should be false. It is: false
    
25. length() should be 2. It is: 2
    
26. Here is the same list after insertFront(5): [  5  6  7  ]
    
27. Now we are testing LockDList.
    
28. Here is a list after insertBack 6, 9, 12: [  6  9  12  ]
    
29. 
    
30. Here is the same list after insertBack(15) and insertFront(3): [  3  6  9  12  15  ]
    
31. 
    
32. front() should be 3. It is: 3
    
33. front's next should be 6. It is: 6
    
34. front's next's prev should be 3. It is: 3
    
35. We lockNode front()= 3
    
36. After remove the locked front, the front() should still be 3. It is: 3
    
37. After remove the back, the back() should be 12. It is: 12
    
38. After insertBefore(3) and insertAfter(3), The first 3 nodes should be 5,3,8. The list is: [  5  3  8  6  9  12  ]
    
39. 
    
40. Here is a list after construction: [  ]
    
41. isEmpty() should be true. It is: true
    
42. length() should be 0. It is: 0
    
43. Here is a list after insertFront(3) to an empty list: [  3  ]
    
44. Here is a list after insertBack(5) on an empty list: [  5  ]
    
45. 
    
46. Here is a list after insertFront 3, 2, 1: [  1  2  3  ]
    
47. isEmpty() should be false. It is: false
    
48. length() should be 3. It is: 3
    
49. Here is the same list after insertBack(4): [  1  2  3  4  ]
    
50. 
    
51. Here is a list after insertBack 6, 7: [  6  7  ]
    
52. isEmpty() should be false. It is: false
    
53. length() should be 2. It is: 2
    
54. Here is the same list after insertFront(5): [  5  6  7  ]
    
55. [code]Now we are testing LockDList.
    
56. Here is a list after insertBack 6, 9, 12: [  6  9  12  ]
    
57. 
    
58. Here is the same list after insertBack(15) and insertFront(3): [  3  6  9  12  15  ]
    
59. 
    
60. front() should be 3. It is: 3
    
61. front's next should be 6. It is: 6
    
62. front's next's prev should be 3. It is: 3
    
63. We lockNode front()= 3
    
64. After remove the locked front, the front() should still be 3. It is: 3
    
65. After remove the back, the back() should be 12. It is: 12
    
66. After insertBefore(3) and insertAfter(3), The first 3 nodes should be 5,3,8. The list is: [  5  3  8  6  9  12  ]
    
67. 
    
68. Here is a list after construction: [  ]
    
69. isEmpty() should be true. It is: true
    
70. length() should be 0. It is: 0
    
71. Here is a list after insertFront(3) to an empty list: [  3  ]
    
72. Here is a list after insertBack(5) on an empty list: [  5  ]
    
73. 
    
74. Here is a list after insertFront 3, 2, 1: [  1  2  3  ]
    
75. isEmpty() should be false. It is: false
    
76. length() should be 3. It is: 3
    
77. Here is the same list after insertBack(4): [  1  2  3  4  ]
    
78. 
    
79. Here is a list after insertBack 6, 7: [  6  7  ]
    
80. isEmpty() should be false. It is: false
    
81. length() should be 2. It is: 2
    
82. Here is the same list after insertFront(5): [  5  6  7  ]
    

复制代码

[/code]
个人理解 LockDListNode中是可以连着DListNode的 不知道对不对

交作业了！ 这次的作业让我对override 有了更深的认识，一开始还小看了这次作业呢。
LockDList 中的LockNode和Remove方法实现的关键就在于LockDList中每个元素的static type 都是LockDListNode而不是其父类DListNode。这样才能保证将接口穿来的DListNode 能cast成LockDListNode且拥有isLocked field。
最简单的方法就是重写newNode方法，使其生成一个LockDListNode。这样的话其他所有能添加新node的方法最终都要调用newNode方法，从而保证了LockDList中每个元素的static type都是LockDListNode。

vincentli1 发表于 2018-3-20 17:37
交作业了！ 这次的作业让我对override 有了更深的认识，一开始还小看了这次作业呢。
LockDList 中的Lock ...

同学，想请教一下part 2. 不知道我这样理解对不对：当用Dlist实例化出一个list对象后，例如调用了list.remove(node)函数，这时并不能保证node是在list内的，所以这时仅仅把list的size减一，而list包含的node数量并没有改变。同理 其他函数也类似的可能只会改变list的size，而不会增加或减少list内node数量。

请问我的理解对吗？或者你能说说你的想法吗？多谢！

part2我也没想到太靠谱的只通过调用方法就搞乱整个链表的办法。不过我感觉你的想法站得住脚，程序不会遍历整个链表来确认node是否在表中。

交作业～