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

Lab3
1. 创建linked list
（1）可以用SList中insertEnd method一个一个延长这个list
（2）可以一个一个创建node，用next连接起来，然后将第一个给head，最后一个给tail。
如果写成一句，head = new SListNode(new Integer(6), new SListNode(new Integer(9), new SListNode(new Integer(12))))
tail无法给到，必须得每一个node给到变量然后最后一个给tail。

2. constant-time insertEnd
在field，constructor，insertFront,insertEnd中针对tail进行相应添改即可。特别考虑isEmpty() = true的情况。
初始情况下，head = null, tail = null; 只有一个node时，head = tail =node;

结果如下：

电脑卡了重复回复了，麻烦删除这条回复吧。

刚开始犯糊涂想了半天才想明白，head和tail其实都不是节点，他们是SList类的对象，声明类就要声明类的属性及属性类型，head和tail都是SListNode类型。

另外我想请教各位几个问题：
1. 既然head和tail都是SListNode类型的，那么他们也都应该分别具有SListNode类具有的item和next属性。所以在insertFront()中，为什么可以直接“head = new SListNode(obj, head);”，我写成head.next = new SListNode(obj, head);好像就无法运行了诶？？
2. 在insertEnd()中，tail.next = new SListNode(obj); tail = tail.next; 这两句我都明白，但是我不知道 最新的最后一个节点 和 之前的最后一个节点之间是怎么联系起来的？
3. nth()我没看懂例子的实现过程。这个方法想要完成的不是返回第n个位置的item吗？那position应该是指定的呀，为什么还要position--；？？
谢谢宝贝们~ 这几个问题我很困惑！

运行结果：
[  6  9  12  ]
[  3  6  9  12  15  ]

Here is a list after construction: [  ]
isEmpty() should be true. It is: true
length() should be 0. It is: 0
Here is a list after insertFront(3) to an empty list: [  3  ]
Here is a list after insertEnd(5) on an empty list: [  5  ]

Here is a list after insertFront 3, 2, 1: [  1  2  3  ]
isEmpty() should be false. It is: false
length() should be 3. It is: 3
Here is the same list after insertEnd(4): [  1  2  3  4  ]

Here is a list after insertEnd 6, 7: [  6  7  ]
isEmpty() should be false. It is: false
length() should be 2. It is: 2
Here is the same list after insertFront(5): [  5  6  7  ]



补充内容 (2018-7-31 16:33):
然后我还有第四个问题... toString()方法我明白，但是我在完成part one的时候，先写了lst1.insertFront(12); 然后system.out.println(lst1); 发现打印出来的是[ 12 ]本身就带有中括号了，并不用写成lst1.toString诶

补充内容 (2018-7-31 16:37):
然后我还想写一下我对head和tail的理解，我怕我还是搞错了：最后一个节点并不指向tail，而是tail指向最后一个节点。而且tail.next也不是指向null。我个人认为tail.next里面装的应该是最后一个节点的地址，

补充内容 (2018-7-31 16:37):
可以想成最后节点的房间号，跟着房间号才能找到最后节点。最后节点.next 里面装的才是null。

Let's smoosh arrays!

smooshing [  3  7  7  7  4  5  5  2  0  8  8  8  8  5  ]:
[  3  7  4  5  2  0  8  5  -1  -1  -1  -1  -1  -1  ]
smooshing [  6  6  6  6  6  3  6  3  6  3  3  3  3  3  3  ]:
[  6  3  6  3  6  3  -1  -1  -1  -1  -1  -1  -1  -1  -1  ]
smooshing [  4  4  4  4  4  ]:
[  4  -1  -1  -1  -1  ]
smooshing [  0  1  2  3  4  5  6  ]:
[  0  1  2  3  4  5  6  ]

Let's squish linked lists!

squishing [  3  7  7  7  4  5  5  2  0  8  8  8  8  5  ]:
[  3  7  4  5  2  0  8  5  ]
squishing [  6  6  6  6  6  3  6  3  6  3  3  3  3  3  3  ]:
[  6  3  6  3  6  3  ]
squishing [  4  4  4  4  4  ]:
[  4  ]
squishing [  0  1  2  3  4  5  6  ]:
[  0  1  2  3  4  5  6  ]
squishing [  ]:
[  ]

Let's twin linked lists!

twinning [  6  3  6  3  6  3  ]:
[  6  6  3  3  6  6  3  3  6  6  3  3  ]
twinning [  4  ]:
[  4  4  ]
twinning [  ]:
[  ]

1. public void squish() {
   
2.     // Fill in your solution here.  (Ours is eleven lines long.)
   
3.   
   
4.           SListNode currentNode = this.head;
   
5.           if (head != null) {
   
6.                   SListNode nextNode = this.head.next;
   
7.                   while (nextNode != null) {
   
8.                           if (!currentNode.item.equals(nextNode.item)) {
   
9.                                   currentNode.next = nextNode;
   
10.                           currentNode = currentNode.next;          
    
11.                           }
    
12.                           nextNode = nextNode.next;
    
13.                     }
    
14.                  
    
15.                   currentNode.next = null ;
    
16.                   }
    
17.           }

复制代码

Lab3打卡

开心啊，小作业励志成效很快。

需要mark在这里的就是在insertFront和insertAfter都容易出现空指针NullPointerException问题，所以要在两个里都加上如果tail和head=null的情况

使用Java 9以上的同学需要把所有的new Integer(int)都改成int，因为旧的Integer(int)已经被废弃了，会出现deprecation error。

Here is a list after construction: [  ]
isEmpty() should be true. It is: true
length() should be 0. It is: 0
Here is a list after insertFront(3) to an empty list: [  3  ]
Here is a list after insertEnd(5) on an empty list: [  5  ]

Here is a list after insertFront 3, 2, 1: [  1  2  3  ]
isEmpty() should be false. It is: false
length() should be 3. It is: 3
Here is the same list after insertEnd(4): [  1  2  3  4  ]

Here is a list after insertEnd 6, 7: [  6  7  ]
isEmpty() should be false. It is: false
length() should be 2. It is: 2
Here is the same list after insertFront(5): [  5  6  7  ]

[  6  9  12  ]

[  3  6  9  12  15  ]



最后的问题出在size++，放错了位置，应该移到内层

一不小心还是很容易错的，容易有空指针问题