Java программирование - Круговая LinkedList

Question

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

Answer 1

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

Answer 2

ОК, я не дам вам полной реализации класса, но вместо этого я дам вам несколько советов.

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

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 3

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

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

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

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

Просто заметил, что кто-то уже задавал один и тот же вопрос: Can I use java.util.LinkedList to construct a circular/cyclic linked list?

Answer 4

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