круговой единый связанный список

Я сделал некоторые упражнения на 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;
    }



}

person thomson    schedule 05.03.2012    source источник
comment
@ Томас, ты можешь называть это как хочешь   -  person thomson    schedule 05.03.2012
comment
Написание такого класса, в частности, требует тщательного тестирования. Почему вы говорите, что remove(), в частности, не работает? Что происходит неправильно?   -  person DNA    schedule 05.03.2012
comment
Вырежьте и вставьте код непосредственно из вашей IDE, предварительно убедившись, что он по крайней мере компилируется. В этом коде много синтаксических ошибок.   -  person Alex D    schedule 05.03.2012
comment
@DNA вызывает нарушение порядка элементов после вызова метода remove(). вы можете попробовать. но я не гарантирую, что другие методы на 100% верны. я оставил код, потому что может быть проще посоветовать что-то изменить, чем писать код с самого начала   -  person thomson    schedule 05.03.2012
comment
Я бы посоветовал вам сначала написать набор тестов для вашего списка, тогда у вас будет более четкое представление о том, как его кодировать.   -  person Timoteo Ponce    schedule 05.03.2012
comment
@TimoteoPonce, я не думаю, что это очень хорошая идея, потому что мне потребуется много времени, чтобы написать такие тесты.   -  person thomson    schedule 06.03.2012
comment
@thomson Хотя написание тестов может занять некоторое время, вы будете рады, что сделали это в долгосрочной перспективе, поскольку это значительно сократит время отладки.   -  person dj18    schedule 06.03.2012
comment
Кстати, метод contains не обязателен, но упрощает выполнение других методов. и на данный момент тоже работает некорректно   -  person thomson    schedule 06.03.2012
comment
я умею описывать алгоритмы, так будет проще понять мой образ мыслей и, возможно, найти ошибку (в построении алгоритма) :)   -  person thomson    schedule 06.03.2012


Ответы (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;
  }
person Garrett Hall    schedule 05.03.2012
comment
спасибо за пост. но мне нужен односвязный список. с добавлением предыдущего элемента я изменю идею моего узла и методов добавления, удаления, вставки элементов и т. д. - person thomson; 06.03.2012

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

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);
person Thomas    schedule 05.03.2012
comment
Спасибо за ответ. единственное, что мне нужно проверить, сопоставляя объекты при добавлении или удалении их из моего связанного списка, поэтому я реализовал метод contains(). но поправка на add() полезна. Благодарность! - person thomson; 06.03.2012

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

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

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

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

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

person dj18    schedule 05.03.2012
comment
Спасибо. я рассмотрю это и дам ответ, когда объединим его с моим кодом - person thomson; 06.03.2012