Внедрение Circular LinkedList в Java

Это назначение. Я должен создать круговой связанный список и удалить каждый третий номер в списке. Когда моя программа дойдет до конца списка, она вернется к голове и продолжит процесс, пока не останется только одно число.

Я искал онлайн и некоторые другие справочники, но не смог решить мою проблему. Большинство ссылок, которые я нашел, говорят такие вещи, как:

Помимо того, что круговые списки не имеют конца, они полностью совпадают с регулярными списками

или (взято из моего учебника):

Односвязный список циклически связан, если преемником последнего node является первый

Но они не говорят, как это сделать. Я также попытался использовать код, который я нашел на этом сайте, но ничего не понял.

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

если список имеет 6 номеров, список будет 1,6,5,4,3,2.
если список содержит 8 номеров, список будет 1,8,7,6,5,4,3,2.

Не получив правильный список, я могу сделать удаление правильно. Что не так со следующим кодом:

public class LastNumberDemo {
    public static void main(String[] args) {
        LastNumberNode ll=new LastNumberNode();
        System.out.println("how long is the list: ");
        Scanner keyboard = new Scanner(System.in);
        int input = keyboard.nextInt();

        if(input<=0) {
            System.out.println("no number to creat list");
        }
        if(input==1) {
            System.out.println("The Last number is 1.");
        }
        else {
            String[] n=new String[input];
            for(int index=0; index<n.length; index++)
                n[index]=Integer.toString(index+1);
            for(String e:n)
                ll.add(e);
            System.out.print("The list contains: \n");
            ll.print();
            System.out.print("\nThe last number is: ");
            ll.remove();
            ll.print();
        }
    }
}

//The circular linked list class
class LastNumberNode{
    private class Node{
        String value;  
        Node next;     

        Node(String val, Node n){
            value = val;
            next = n;
        }

        Node(String val){
            value=val;
            next=null;
        }
    } //This brace was missing - Edd

    private Node first;

    public LastNumberNode(){
      first = null;
    }

    public boolean isEmpty(){        
       return first == null;
    }

    public int size(){
        int count = 0;
        Node p = first.next;   
        while (p != first){
            count ++;
            p = p.next;
        }
        return count;
    }

    public void add(String e) {
        Node p=new Node(e);
        if(first==null){
            first=p;
            first.next=first;
        }
        else{
            first.next=new Node(e,first.next);
        }
    }

    public void remove(){
        while(size()>0){
            Node target=first.next.next;   
            Node temp=first;               
            target=target.next;          
            last.next=temp;
            first=target;
        }
    }

    public void print(){
        Node ref=first;
        for(int index=-1; index<size();index++)
            System.out.print(ref.value+" ");
        ref=ref.next;
    }
} //Extra brace removed - Edd

Ответ 1

Когда вы добавляете новый Node в свой список, вы добавляете новый Node во вторую позицию (first.next указывает на недавно добавленный node), но этот недавно добавленный node имеет first в качестве следующего node, оставив остальную часть списка без ссылок (и, таким образом, сбор и уничтожение мусора). С помощью вашего метода add, так как он не может содержать ваш список, кроме 0, 1 или 2 Node s. Немного странно добавить новый Node в середину списка; либо добавьте его в начало (newnode.next = first; first = newnode; last.next = first;), либо сохраните ссылку на заднюю часть списка (как предложили другие) и добавьте его там.

Лично я бы реструктурировал класс LastNumberNode, чтобы он имел следующие методы для управления связанным списком:

private void addNode(Node node)
private void removeNode(Node node)
private Node findNode(Node nextNode)

Если вы сохраняете ссылку на последний node в списке, то ваш метод addNode(Node node) может выглядеть примерно так:

if(isEmpty()) {
    first = node;
    last = node;
}
else {
    Node tail = last;
    tail.next = node;
    node.next = first;
    last = node;
}

removeNode(Node node) основывается на следующем:

Node prevNode = findNode(node);

if(node == first) {
    first = node.next;
    last.next = first;
}
else if(node == last) {
    prevNode.next = first;
    last = prevNode;
}
else {
    prevNode.next = node.next;
}

Если бы я был реализован, я бы, вероятно, сделал сокращение списка до одного Node с помощью такого подхода:

public String reduceList() {
    Node curNode = first;
    while(first != last) {
        removeNode(curNode.getNext().getNext());
        curNode = curNode.getNext().getNext();
    }

    return first.getValue();
}

В качестве конечной точки я не стал бы заполнять массив последовательными числами, а затем прокладывать его, чтобы добавить элементы в ваш список. Я бы просто пошел прямо к чему-то вроде следующего:

for(int i = 1; i <= input; i++) {
    linkedlist.add(new Integer(i).toString());
}

Ответ 2

Ваш метод add вставляет элементы непосредственно после first, если первый уже установлен:

first.next = new Node(e, first.next);

Это приводит к наблюдаемому поведению.

Вам нужно отслеживать элемент last в списке и добавить новый элемент как last.next, если вы хотите добавить новый элемент в конце списка. Один из способов сделать это - просто сохранить ссылку на последний элемент в переменной-члене класса списка, другой - пересечь список, пока не найдете ссылку node на first, которая будет последней node.