Java программирование - круговой LinkedList

Question

Я пытаюсь написать Java-класс CircularList, который содержит обычный внутренний класс Node и переменные экземпляра:

Answer 1

Хорошо, я не буду давать вам полную реализацию класса, но вместо этого я дам вам несколько советов.

1. Вам не нужно хранить ссылку на последний элемент. Поместите ссылку Prev и Next на ваши узлы, и ваш последний узел будет первым. Предыдущая

2. Помимо того, что круговые списки не имеют конца, они почти такие же, как обычные списки, но где вы найдете последний элемент, подобный этому:

   Узел tmp = первый;

   while (tmp.Next! = Null) tmp = tmp.Next;

В круговом списке идея выглядит так:

Node tmp = first;

while ( tmp.Next != first )
   tmp = tmp.Next;

Потому что вы никогда не найдете узел, указывающий на ноль, если список не пуст. И последний совет: если вам нужно реализовать индексатор, помните, что в циклическом списке нет такой вещи, как индекс вне диапазона, потому что

list[count] = list[0] = list[count * k]

Имейте это в виду, поэтому вычисление индекса для этих методов может быть довольно сложным. Для положительных показателей основная идея:

index = index % count;

Для отрицательных немного отличается. Я надеюсь, что смогу помочь вам с моими словами. Если вы хотите реализации, я считаю, что их должно быть несколько, если вы вежливо спросите Google:)

Удачи!

Answer 2

Я не уверен, в чем твоя проблема, у тебя, кажется, есть все необходимое.Единственная разница между этим связанным списком и обычным списком состоит в добавлении в конец.

В обычном связанном списке вы создадите новый узел и сделаете так, чтобы последний элемент указывал на этот узел.В этом случае вы изменяете указатель в • Последнем узле, чтобы он указывал на новый узел, а новый узел указывает на • Первый.

Удаление работает так же, как обычный связанный список.Всякий раз, когда вы хотите удалить узел, вы обнаруживаете, какой другой узел указывает на этот (либо предыдущий, либо в случае удаления первого, установите флажок • Последний) и укажите, куда указывал удаленный узел.

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

Только что заметил, что кто-то уже задавал точно такой же вопрос: Могу ли я использовать java.util.LinkedList для построениякруговой / циклический связанный список?

Answer 3

class Node    {
    int value;
    Node next;
    Node prev;
    Node(int initialValue)    {
        value = initialValue;
        next =  null;
        prev = null;
    }
    public int getValue()    {
        return this.value;
    }
}

class NodeList    {
    Node pointer;
    NodeList()    {
        pointer = null;
    }
    public void insertNode(int nodeValue)    {
        Node newNode = new Node(nodeValue);
        if( pointer == null )    {
            newNode.next = newNode;
            newNode.prev = newNode;
        }else if( pointer.next == null && pointer.prev == null && pointer != null )    {
            newNode.next = pointer;
            newNode.prev = pointer;
            pointer.prev = newNode;
            pointer.next = newNode;
        }
        else if( pointer != null )    {
            newNode.next = pointer.next;
            newNode.prev = pointer;
            pointer.next.prev = newNode;
            pointer.next = newNode;
        }
        pointer = newNode;
        System.out.println(“Successfully inserted : ” + pointer.getValue());
    }
    public void printRing( boolean direction )    {
        Node tempNode = pointer;
        do    {
            System.out.println( “Value = ” + tempNode.getValue() );
            tempNode = direction ? tempNode.next : tempNode.prev;
        } while( tempNode.value != pointer.value );    
    }    
}

Answer 4

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