круговой одиночный

Question

Я сделал несколько упражнений на Java, и теперь я застрял в такой проблеме - мой список работает неправильно.Я уверен, что remove работает некорректно, и, возможно, вы можете помочь мне (с советом или кодом) правильно реализовать круговой однократно связанный список.Я не уверен, работают ли другие функции должным образом, но я старался изо всех сил.

Вот мой код:

import java.util.*;


public class Node {
    private Object value;
    private Object nextValue;

    private Node next;


    public Node(int data) {
        this.value = data;
        this.next = null;
    }

    public Object getValue() {
        return this.value;
    }

    public Node nextItem() {
        return this.next;   
    }

    public void setNextItem(Node nextItem) {
        this.next = (Node) nextItem;
        this.next.setValue(nextItem.getValue());
    }


    public void setValue(Object arg0) {
        this.value = arg0;
    }

}

    -------------------------------------------------------------------

   import java.util.*;



public class CircularList  {
    private Object[] array;
    private int arrSize;
    private int index;
    private Node head;
    private Node tail;
    public CircularList() {
        head = null;
        tail = null;
    }



    public boolean add(Node item) {

        if (item == null) {
            throw new NullPointerException("the item is null!!!");
        }


        if (head == null) {
            head = item;
            head.setNextItem(head);
            arrSize++;

            return true;
        } 

        Node cur = head;
        while(cur.nextItem() != head) {
            if(cur.getValue() == item.getValue()) {
                throw new IllegalArgumentException("the element already " +
                        "exists!");
            }
            cur = cur.nextItem();
        }

            head.setNextItem(item);
            item.setNextItem(head);
            arrSize++;

            return true;

    }


    public Node getFirst() {
        return head;
    }


    public void insertAfter(Node item, Node nextItem) {

        if ((item == null) || (nextItem == null)) {
            throw new NullPointerException("the item is nul!!!");
        } else if (this.contains(nextItem) == true) {
            throw new IllegalArgumentException("the item already exists!");
        } 

        Node cur = head;
        while(cur.nextItem() != head) {
            if(cur.getValue() == item.getValue()) {
                nextItem.setNextItem(item.nextItem());
                item.setNextItem(nextItem);
            } else {
                cur = cur.nextItem();
            }
        }

    }


    public boolean remove(Node item) {

        if(item == head) {
            Node cur = head;
            for(int i = 0; i < arrSize-1; i++) {
                cur = cur.nextItem();
            }

            head = head.nextItem();

            for(int i = 0; i < arrSize; i++) {
                cur = cur.nextItem();
            }
            arrSize--;
            return true;
        }

        Node cur = head;
        int counter = 0;
        while(cur.nextItem() != head) {
            if(cur == item) {
                item = null;
                cur = cur.nextItem();
                while(cur.nextItem() != head) {
                    cur.setNextItem(cur.nextItem().nextItem());
                }
            return true;    
            }
            cur = cur.nextItem();
        }



        return false;
    }

    public int size() {

        return arrSize;
    }

    public boolean contains(Object o) {
        if ((o == null) && (arrSize == 0)) {
            return false;
        }
        Node cur = head;
        while(cur.nextItem() != head) {
            if(cur.getValue() == o) {
                return true;
            }
            cur = cur.nextItem();
    }


        return false;
    }



}

Answer 1

Здесь есть множество проблем за пределами списка.Вы, кажется, сравниваете свои узлы с ==.Этот код будет выводить 'no match'.

Node n1 = new Node(5);
Node n2 = new Node(5);
if (n1 == n2)
  System.out.println("objects match");
else
  System.out.println("no match");

В add () похоже, что в списке может быть только два элемента, поэтому

head.setNextItem(item);
item.setNextItem(head);

должно быть:

cur.setNextItem(item);
item.setNextItem(head);

Answer 2

В вашем коде много чего происходит, вот несколько советов для некоторых из них:

1. В вашем классе Node: соглашения об именах Java: так же, как сеттеры должны иметь префикс «set», геттеры должны иметь префикс «get:» nextItem() должно действительно быть getNextItem().

2. Также в вашем классе узлов: насколько я знаю, поле «следующее значение» узла связанного списка обычно является ссылкой на следующий узел в списке и поэтому должно иметь тип Node, а не просто какой-либо объект. Это должно работать так, как у вас, но использование явной типизации намного безопаснее. (Пожалуйста, исправьте меня, если использование «Объекта» действительно является распространенным способом построения следующего узла связанного списка.)

3. В первом случае remove() при удалении головки: вы перебираете список, чтобы достичь последнего значения, предположительно, чтобы сбросить его «следующее значение» на новую голову, но вы на самом деле не делает это. Вы хотите что-то вроде этого:

   if (item == head) {
   head = head.nextItem();
   for(int i = 0; i < arrSize-1; i++){
   cur = cur.nextItem();            
   }
   }
   cur.setNextItem(head);
   

   Я не уверен, что вы надеетесь достичь со вторым циклом.

4. Во втором случае remove(): я не уверен, что вы пытаетесь сделать со вторым циклом while - сбросить все ссылки во всем списке? Весь смысл связанного списка состоит в том, чтобы сделать это ненужным. Удаление узла в связанном списке фактически не избавляет от объекта (поэтому вам не нужно устанавливать item в null). Скорее, вы просто «обходите» нежелательный объект и «игнорируете» его, фактически удаляя его из списка, как в:

Оригинальный список:

[ Value: A; Next: B ] --> [ Value: B; Next: C ] --> [ Value C; Next: D ] ...

После удаления узла B:

  [ Value: A; Next: C ] --> [Value C; Next: D ] ...

[ Value: B; Next: C ] все еще существует в памяти, но ничто не указывает на это, поэтому оно будет удалено в следующем цикле сборки мусора.

Для реализации: при просмотре списка сохраняйте ссылку на предыдущий узел, который вы посетили. Затем, когда вы найдете искомый элемент (используя правильное сравнение, как заметил Томас), вы можете просто установить prev.setNextItem(cur.nextItem()); (предостережение: непроверенный код):

    Node prev = head;
    Node cur;
    while ((cur = prev.nextItem()) != head) {
    if (cur.equals(item)) {
    prev.setNextItem(cur.getNextItem());
    return true;
    }
    }

Надеюсь, эти советы помогут вам на правильном пути.

Answer 3

Многие из этих алгоритмов могут быть проще.

Пример:

  public boolean remove(Node item) {
     Node current = head;
     for(int i = 0; i < size; i++) {
       if (current.getNext() == item) {
          current.next = current.getNext().getNext();
          size --;
          return true;
       }
       current = current.getNext()
     }
     return false;
  }