插队的关系户太多,影响了正常排队的人,被人投诉,大卫哥只好想办法删除一些。
func (list *List) Remove(i uint, node *Node) bool { if i >= (*list).size { return false } if i == 0 { // 删除头部 node = (*list).head (*list).head = (*node).next if (*list).size == 1 { // 如果只有一个元素,那尾部也要调整 (*list).tail = nil } } else { preItem := (*list).head for j := 1; j < i; j++ { preItem = (*preItem).next } node = (*preItem).next (*preItem).next = (*node).next if i == ((*list).size - 1) { // 若删除的尾部,尾部指针需要调整 (*list).tail = preItem } } (*list).size-- return true }(5)获取
为了获取某个位置的元素,我们需要一个方法。
func (list *List) Get(i uint) *Node { if i >= (*list).size { return nil } item := (*list).head for j := 0; j < i ; j++ { // 从head数i个 item = (*item).next } return item }到这里基本框架已经出来了,不过还有几个接口还没实现,作为课后作业。
三、小结
单链表就和列车类似,一个接着一个,所以本节从列车类比介绍了单链表的Go语言实现。在接口实现部分大卫哥以序号作为链表中每个节点的操作关键字。在实际应用中,我们往往以data中的某一个字段作为操作关键字。所以这也衍生出链表的不同接口,大家可以参考大卫哥留的链接中的代码实现作为理解。同时有些实现将表头独立出来并不存放数据,这在一定程度上简化了代码的实现。
代码下载
四、习题
(1)补全GetSize,RemoveAll,GetHead和GetTail的定义和实现。
(2)以data作为参数,考虑单链表的实现。
(3)将单链表的head独立出来,此时的head是独立的,不存放data,如下图,考虑单链表的实现,并比较这种实现。
(4)如果将head和tail都独立出来,都不存放data,此时的单链表如何实现?这样实现的代码在插入删除操作时候是不是更容易点?