Реализация кругового связанного списка в java

У меня возникла небольшая проблема с реализацией моего циклически связанного списка. Я работаю над проблемой, которая требует, чтобы вы самостоятельно реализовали любой ADT. Кажется, у меня все в порядке с добавлением узлов в список, однако я нахожусь на незнакомой территории, когда дело доходит до удаления. Я включил первые два метода удаления, чтобы дать вам представление о том, к чему я клоню: как мне удалить последний узел в списке?

public class LinkedList {
    private Node head;
    private Node tail;
    private int size = 0;
    LinkedList() {
        head = null;
        current = null;
        previous = null;
        tail = null;
        size = 0;
    }

    //checks if list is empty
    public boolean isEmpty() {
        return head == null;
    }
    //add new node to front of circularly linked list
    public void addToFront(E x) {
        if (head == null) {
            head = new Node(x);
        } else {
            Node n = new Node(x);
            x.next() = head;
            head = x;
        }
    }

    public void addtoMiddle(E x) {
        x.next = current.next();
        current.next = x;
        size = size + 1;
    }

    public void addToEnd(E x) {
        x.next = null;
        tail.next() = x;
        tail = x;
        size = size + 1;
    }

    public void removeFirst(E x) {
        if (head = null) {
            System.out.println("Error! List is empty!");
        } else {
            head = current.next();
            size = size + 1;
        }
    }

    public void removeMiddle(E x) {
        previous.next() = current.next();
        current.next() = null;
        size = size + 1;
    }

person pablokunta128    schedule 30.09.2015    source источник
comment
Можете ли вы также предоставить класс Node? Предполагая, что у вас есть ссылки в обоих направлениях, удаление последнего узла просто потребует от вас вернуться назад от головы. Не должно быть слишком большой головной боли. - Если у вас есть ссылки только в одном направлении, зацикливайте, пока не наткнетесь на узел, next которого указывает на голову. Тогда это ваш последний узел.   -  person Thomas    schedule 30.09.2015
comment
Можете ли вы объяснить, что вы подразумеваете под «циклически связанным списком»?   -  person DJClayworth    schedule 30.09.2015
comment
Это не циклический связанный список, а просто двусвязный список, который можно преобразовать в циклический связанный список. Циклический связанный список никогда не содержит null ни в одном из следующих и предыдущих полей узлов.   -  person laune    schedule 30.09.2015
comment
@Thomas - я новичок и пытаюсь впитывать как губка. Я знаю, что есть ошибки/отсутствующие утверждения, и я просто ищу толчок в правильном направлении. Спасибо. Какой класс узлов вы имеете в виду?   -  person pablokunta128    schedule 30.09.2015
comment
@ pablokunta128 Я добавлю ответ по причинам форматирования.   -  person Thomas    schedule 30.09.2015
comment
Конструктор LinkedList ссылается на текущий и предыдущий — где их объявления?   -  person laune    schedule 30.09.2015
comment
@laune Как бы вы превратили двусвязный список в круговой? Спасибо   -  person pablokunta128    schedule 30.09.2015
comment
@laune, где должны быть объявления? О, понятно, я объявил их в методе LinkedList, а не в классе. Это оно?   -  person pablokunta128    schedule 30.09.2015
comment
Вы нигде не объявляли их в этом классе, но я думаю, что они все равно избыточны.   -  person laune    schedule 30.09.2015
comment
@laune Как тогда можно было бы добавить / удалить из середины без тока?   -  person pablokunta128    schedule 30.09.2015
comment
addToFront не увеличивает размер. Оба метода удаления увеличивают размер.   -  person laune    schedule 30.09.2015
comment
Вы до сих пор не добавили код для Node, поэтому я не знаю, что делать с предыдущим и текущим в методе removeMiddle. Кроме того, меня интересует цель E x в методах удаления.   -  person laune    schedule 30.09.2015
comment
Прекратите редактировать вопрос - это обсуждение не будет иметь никакого смысла, если вы удалите причины для комментариев.   -  person laune    schedule 30.09.2015
comment
При всем уважении, x.next() = head; даже не является законным кодом Java, и он не будет компилироваться. Возможно, вам следует сначала изучить основные правила Java. (Я предполагаю, что это домашнее задание, но то, что люди на этом сайте пишут домашнее задание за вас, не поможет вам в долгосрочной перспективе.)   -  person cpurdy    schedule 30.09.2015
comment
@cpurdy ты прав. Я новичок, и я боролся с аспектом кодирования. Я написал, чтобы получить совет по реализации, а не для того, чтобы кто-то написал мою работу. Я планирую сделать карьеру в CS, поэтому я знаю, что было бы контрпродуктивно, если бы другие делали это за меня. Спасибо за совет   -  person pablokunta128    schedule 30.09.2015
comment
В этом случае начните с реализации CircularLinkedList‹T›, которая имеет только одно поле: Node head; .. и узел, который имеет только два поля: значение T; и узел рядом; .. это должно быть достаточным ограничением на дизайн, чтобы заставить вас реализовать правильный круговой связанный список. И наилучшие пожелания!   -  person cpurdy    schedule 30.09.2015


Ответы (2)


В круговом связанном списке последний узел next указывает на голову, поэтому вы перебираете узлы до node.next.equals( head ). Обратите внимание, что next никогда не должно быть нулевым, и если у вас есть только один узел, у вас есть head.next = head.

В циклическом двусвязном списке у вас также есть узел previous, то есть вы можете выполнять итерацию в обратном направлении. В этом случае ваш последний узел просто head.previous.

Небольшая ascii-картинка:

head -next---> node -next---> node -next---> last
 | ^  <---prev-      <---prev-      <---prev- | ^
 | |                                          | |
 | |_____________________________________next_| |
 |_prev_________________________________________|      
person Thomas    schedule 30.09.2015
comment
Итак, теоретически все, что мне нужно, это голова, хвост, и я смогу установить методы удаления/добавления середины/конца при использовании .next и .previous? - person pablokunta128; 30.09.2015
comment
Очень хороший способ реализации кругового двусвязного списка — сделать List extends Node так, чтобы объект списка имел те же указатели, что и узел. Таким образом, нет необходимости отличать пустой список от списка с узлами. - person laune; 30.09.2015
comment
@laune есть ли способ продолжить это в чате? Однако у меня недостаточно репутации, чтобы инициализировать convo. Мне любопытно выбрать ваш мозг и узнать немного больше. Спасибо - person pablokunta128; 30.09.2015
comment
@ pablokunta128 вам, вероятно, понадобится только голова, но в определенных ситуациях может пригодиться отслеживание хвоста. В качестве примечания: addtoMiddle и т. д. кажется немного странным, потому что вы просто добавляете в любом месте (добавление спереди и сзади - это просто особые случаи для этого), поэтому термин средний может вводить в заблуждение. - person Thomas; 30.09.2015

Я знаю, что это не прямой ответ на ваш вопрос, но я чувствую, что Томас дал здесь необходимое объяснение.

Поскольку в примере много синтаксических ошибок или ошибок неполноты, я бы порекомендовал закомментировать все функции, чтобы в нем больше не было ошибок. Затем прокомментируйте их снова, одну за другой, исправляя каждую ошибку.

Некоторые советы:

Вы используете члены класса, которые не определены, например. current, previous.

Решите, должен ли next быть членом или функцией.

Вам нужно определить класс для Node (содержащий его члены и функции), как вы сделали для LinkedList.

person RonaldFindling    schedule 30.09.2015