一个只带一个前哨节点的缺陷的addLast方法
这个问题来自伯克利的数据结构免费在线课程(CS61B)，链接可以在这里找到：https://joshhug.gitbooks.io/hug61b/content/chap2/chap23.html
实现该列表，使其是循环的，前后指针共享相同的前哨节点。添加和删除操作不得涉及任何循环或递归。单个此类操作必须占用“固定时间”，即执行时间不应取决于deque.的大小。
分配任务的方框和指针图：https://i.stack.imgur.com/pUgk3.png
如果我的列表是{1,2,3}，那么sentinel.next.next.item是3，sentinel.next.item是1
public class DLList<T> {
private class Node {
public T item;
public Node next;
public Node prev;
public Node(T item, Node next, Node prev) {
this.item = item;
this.next = next;
this.prev = prev;
}
@Override
public String toString() {
return item.toString();
}
}
public Node sentinel ;
private int size;
public DLList() {
this.sentinel = null;
this.size = 0;
}
public void addLast(T item) {
sentinel.next = new Node(item, null, sentinel);
sentinel = sentinel.next; // updatedSentinel
size++;
}
}我只想问一问，如何确保updatedSentinel.next链接一路返回到第一个节点？另外，就这个类而言，我的构造函数正确吗？当大小为0和大小>= 1时，实现应该是不同的吗？
回答 2
Stack Overflow用户
发布于 2018-12-10 14:48:36
让哨兵指向最后一个节点:如果列表是空的，它将为null，否则，sentinel.next是第一个节点(因为列表是循环的)。你不需要任何反向链接。所以addLast应该是：
public void addLast(T item) {
if (sentinel == null) {
sentinel = new Node(item, null);
sentinel.next = sentinel;
} else {
sentinel.next = new Node(item, sentinel.nex);
sentinel = sentinel.next; // updatedSentinel
}
size++;
}更新:两个链接：
public void addLast(T item) {
if (sentinel == null) {
sentinel = new Node(item, null, null);
sentinel.next = sentinel;
sentinel.prev = sentinet;
} else {
Node next = sentinel.next;
sentinel.next = next.prev = new Node(item, next, sentinel);
sentinel = sentinel.next;
}
size++;
}Stack Overflow用户
发布于 2018-12-10 14:32:11
首先，您必须检查链接列表是空的还是not.If是空的，然后链接prev，next和哨兵到当前节点。
if(head == null)
{
Node a = new Node(item,a,a);
sentinel.next = a;
}否则，查找最后一个节点并将其下一个节点分配给第一个node.Similarly，将prev节点分配给最后一个node.You可以跟踪哨兵的下一个节点作为头节点。
Node head = sentinel.next;
Node last = head;
while(last.next != head)
{
last = last.next;
}
Node a = new Node(item,head,last);
head.prev = a;
last.next = a;我认为构造函数类没有任何错误。
https://stackoverflow.com/questions/53707360
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号