只有一个哨兵节点的双端队列的 addLast 方法

Question

本题来自伯克利的数据结构免费在线课程（CS61B）link可以在这里找到：https://joshhug.gitbooks.io/hug61b/content/chap2/chap23.html

实现链表是循环的，前后指针共享同一个sentinel节点。添加和删除操作不得涉及任何循环或递归。单个这样的操作必须花费“恒定时间”，即执行时间不应取决于双端队列的大小。

[分配任务的方框和指针图] [1]: https://i.stack.imgur.com/pUgk3.png

例如，如果我的列表是 {1,2,3}，那么 sentinel.next.next.item 是 3，而 sentinel.next.next.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 link一路回到第一个节点？此外，我的构造函数是否适合此 class 的目的？当大小为 0 和大小 >= 1 时，实现应该有所不同吗？

Answer 1

首先，你必须检查链表是否为空或者not.If它是否为空，然后link prev,next 和sentinel 到当前节点。

if(head == null)
{
  Node a = new Node(item,a,a);
  sentinel.next = a; 
}

否则找到最后一个节点并将其下一个节点分配给第一个node.Similarly，将上一个节点分配给最后一个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;

我认为你的构造函数没有任何错误class。

Answer 2

使sentinel指向最后一个节点：如果链表为空则为null，否则sentinel.next为第一个节点（因为链表是循环的）。您不需要任何向后 link。所以 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++;
    }

¨ 更新：同时 links:

    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++;
    }

只有一个哨兵节点的双端队列的 addLast 方法

addLast method for a deque with only one sentinel node

java

data-structures

linked-list

deque