Могу ли я использовать java.util.LinkedList для создания кругового / циклического связанного списка?

Question

Я хотел бы создать круговой / циклический связанный список, где хвост списка будет указывать на начало списка.Так можно ли использовать java.util.LinkedList и изменить хвостовой узел после создания списка, чтобы он был циклическим / циклическим?Если да, можете ли вы показать мне некоторый код того, как это могло бы произойти?

Если я не могу использовать java.util.LinkedList, как мне создать собственную реализацию циклического / циклического связанного списка?Можете ли вы показать мне скелеты того, как будет выглядеть эта реализация?

Дайте мне знать, если вам понадобится больше деталей, и я устраню любую путаницу.

Answer 1

class ListNode {
    public ListNode next;
    public Object data;

    public ListNode(Object data, ListNode next) {
        this.next = next;
        this.data = data;
    }
}

class CircularLinkedList {
    private ListNode head = null;
    private int numberOfElements = 0;
    private ListNode actualElement = null;
    private int index = 0;

    public boolean isEmpty() {
        return (numberOfElements == 0);
    }

    public int getNumberOfElements() {
        return numberOfElements;
    }

    public void insertFirst(Object data) {
        if (!(isEmpty())) {
            index++;
        }
        ListNode listNode = new ListNode(data, head);
        head = listNode;
        numberOfElements++;
    }

    public void insertAfterActual(Object data) {
        ListNode listNode = new ListNode(data, actualElement.next);
        actualElement.next = listNode;
        numberOfElements++;
    }

    public boolean deleteFirst() {
        if (isEmpty())
            return false;
        if (index > 0)
            index--;
        head = head.next;
        numberOfElements--;
        return true;
    }

    public boolean deleteActualElement() {
        if (index > 0) {
            numberOfElements--;
            index--;
            ListNode listNode = head;
            while (listNode.next.equals(actualElement) == false)
                listNode = listNode.next;
            listNode.next = actualElement.next;
            actualElement = listNode;
            return true;
        }
        else {
            actualElement = head.next;
            index = 0;
            return deleteFirst();
        }
    }

    public boolean goToNextElement() {
        if (isEmpty())
            return false;
        index = (index + 1) % numberOfElements;
        if (index == 0)
            actualElement = head;
        else
            actualElement = actualElement.next;
        return true;
    }

    public Object getActualElementData() {
        return actualElement.data;
    }

    public void setActualElementData(Object data) {
        actualElement.data = data;
    }
}

Answer 2

Для практического применения (например, не только для игры или обучения), я бы лично предпочел метод Iterables.cycle от Guava - см. http://guava -libraries.googlecode.com / svn / trunk / javadoc / com / google / common/collect/Iterables.html#cycle%28java.lang.Iterable%29.

Answer 3

java.util.LinkedList является одним из типов данных Collections.Целью коллекций является предоставление служебных структур, не мешающих программисту беспокоиться об их внутренней реализации.Если вы должны иметь внутренние устройства, которые работают определенным образом, а java.util не гарантирует, что именно так они работают, то они не для вас.

Для реализации циркулярногосвязанный список, сначала создайте класс ListNode:

class ListNode {
    ListNode next;
    ListNode prev;
    Object data;
}

Затем сохраните ListNode head и убедитесь, что prev из head указывает на «конец» списка, а next из«конец» указывает на head.Честно говоря, есть небольшая разница между двунаправленным связанным списком, в котором хранится хвостовой указатель, и круглым связанным списком.

Answer 4

См. здесь для всесторонней реализации Singlely Linked List в Java.Сделать его круглым - это всего лишь настройка в этом коде.