метод addLast для deque только с одним дозорным узлом - PullRequest
Новая
       35

метод addLast для deque только с одним дозорным узлом

0 голосов
/ 10 декабря 2018

Этот вопрос взят из бесплатного онлайн-курса Беркли по структурам данных (CS61B). Ссылку можно найти здесь: https://joshhug.gitbooks.io/hug61b/content/chap2/chap23.html

Реализуйте список так, чтобы он был круглым, с указателями спереди и сзадиразделяя тот же самый дозорный узел.Операции добавления и удаления не должны включать зацикливание или рекурсию.Одна такая операция должна занимать «постоянное время», то есть время выполнения не должно зависеть от размера deque.

[Рамка и диаграмма указателя для назначенной задачи] [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 полностью ссылается на первый узел?Кроме того, мой конструктор правильный для целей этого класса?Должна ли реализация быть разной, если размер равен 0, а размер> = 1?

Ответы [ 2 ]

0 голосов
/ 10 декабря 2018

Сделать указатель на последний узел: он будет нулевым, если список пуст, в противном случае 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++;
    }
0 голосов
/ 10 декабря 2018

Во-первых, вы должны проверить, является ли Связанный список пустым или нет. Если он пуст, то ссылка prev, next и sentinel на текущий узел. 

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

В противном случае найдите последний узел иприсвойте его следующий узел первому узлу. Аналогично, присвойте узел prev последнему узлу. Вы можете отслеживать следующий узел часового в качестве головного узла. 

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;

Я не думаю, что есть какая-либо ошибкас вашим классом конструктора.

...