circle single linkedList

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

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

Пример:

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

Answer 2

Есть целый ряд вопросов здесь за список. Кажется, вы сравниваете свои узлы с ==. Этот код выводит «нет совпадения».

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

В оных(), это выглядит, как вы можете только когда-либо два элемента в списке, так

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

должен быть таким:

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

Answer 3

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

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

2. Также в вашем классе Node: насколько я знаю, поле «следующего значения» узла связанного списка обычно является ссылкой на следующий узел в списке и поэтому должно быть типа 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 ] до сих пор существует в памяти, но ничего не указывает на него, так что он будет удален в следующем цикле сбора мусора.

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

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

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