#java #nodes #doubly-linked-list
#java #узлы #дважды связанный список
Вопрос:
Я реализую метод add (E) в циклическом классе DoublyLinkedList, а также во внутреннем классе Node.
Узел должен быть реализован как частный внутренний класс.
Атрибут DoublyLinkedList «first» должен указывать на первый узел в списке. Его атрибут «size» должен хранить количество элементов в списке.
Я испытываю трудности с моим методом добавления, потому что кажется, что все в порядке, и я не знаю, что еще я могу добавить в этот этот код, который может это исправить.
Поэтому краткое введение в то, что должен делать метод add.
Метод add (E) должен добавить параметр value в конец списка. Обязательно рассмотрите случай, когда список пуст и / или добавленный элемент является первым в списке.
Вот мой код:
public class DoublyLinkedList<E>
{
private Node first;
private int size;
@SuppressWarnings("unchecked")
public void add(E value)
{
if(first == null)
{
first = new Node(value, null, null);
first.next = first;
first.prev = first;
}
else
{
first = new Node(value, first.next, first.prev);
first.next = first.prev;
first = first.next;
first.prev = first;
}
size ;
}
private class Node<E>
{
private E data;
private Node next;
private Node prev;
public Node(E data, Node next, Node prev)
{
this.data = data;
this.next = next;
this.prev = prev;
}
}
}
Комментарии:
1. Чтобы прояснить для других, читающих это, я предполагаю, что циклический означает, что это круговой связанный список. Вот почему, если size == 1, то first-> next = first=> prev = first.
2. @rcgldr Извините, это сбивает с толку. так что, у меня неправильный способ?
3. Это было просто разъяснение. Я предполагаю, что ваш класс назвал его циклическим вместо circular. Некоторые, читающие это, могут не понимать, что это означает одно и то же.
4. @AdanVivero — Хотя, похоже, вы получили свой ответ здесь; все же подумал, что, возможно, я захочу поделиться чем-то еще для будущих читателей этой темы. После долгих размышлений в этой области на выходных я почувствовал, что циклическая структура данных может быть не очень хорошей идеей. То, что вы намереваетесь здесь сделать, это получить циклический доступ к структуре данных, а доступ к данным — это нечто иное, чем то, как данные фактически хранятся. Подумайте о «разделении обязанностей» здесь. В идеале в вашем случае вам может потребоваться вернуть итератор из вашего класса и реализовать концепцию циклических чтений
5. @RahulR. Это именно то, над чем я работаю. Циклический, но многие, похоже, об этом не знают. Вы знаете, как это исправить? Кроме того, если вы не возражаете, мне вроде как нужна помощь по методу get, у меня есть его по другому вопросу, он привязан к этому же коду.
Ответ №1:
Исправлен код с минимальными изменениями (только случай else в add):
class DoublyLinkedList<E>
{
private Node first;
private int size;
public void add(E value)
{
if(first == null)
{
first = new Node(value, null, null);
first.next = first;
first.prev = first;
}
else
{
first.prev.next = new Node(value, first, first.prev);
first.prev = first.prev.next;
}
size ;
}
private class Node<E>
{
private E data;
private Node next;
private Node prev;
public Node(E data, Node next, Node prev)
{
this.data = data;
this.next = next;
this.prev = prev;
}
}
}
Комментарии:
1. Объяснение else { … } в add(): новый узел (…) устанавливает данные, new.next = первый, new.prev = последний. first.prev.next = новый узел (…) устанавливает last.next = новый узел. first.prev = first.prev.next устанавливает first.prev в новый узел, который является новым последним узлом.
2. вы оказали потрясающую помощь в этом, как вы думаете, вы могли бы помочь мне с моим методом get, я опубликовал еще один вопрос..
Ответ №2:
Редактировать:
Здесь одна ошибка: вместо этой строки this.next = prev; в ней должно быть this .prev = предыдущий;
Однако, если вы исправите эту строку, код все равно не будет работать. Это упрощенная версия вашего кода, которая работает.
public class DoublyLinkedList<E> {
private static class Node<E> {
private final E data;
private Node<E> next;
private Node<E> prev;
Node(E data) {
this.data = data;
this.next = this;
this.prev = this;
}
Node(E data, Node<E> next) {
this.data = data;
this.next = next;
next.prev = this;
}
}
private Node<E> head;
private Node<E> tail;
private int size;
public void add(E value) {
if (this.head == null) {
this.head = new Node<>(value);
this.tail = head;
} else {
this.head = new Node<>(value, head);
this.head.prev = this.tail;
this.tail.next = head;
}
size ;
}
public void forEach(Consumer<E> consumer) {
Node<E> node = this.head;
if (node != null) {
do {
consumer.accept(node.data);
node = node.next;
} while (node != this.head);
}
}
public static void main(String[] args) {
DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.forEach(e -> System.out.print(e ", "));
}
}
Что я сделал: чтобы создать циклический список с двойной связью, я сохраняю ссылку на хвост.
Комментарии:
1. Цель состоит в том, чтобы создать циклический связанный список. first.prev == последний, first.next = второй, last.prev = предпоследний, last.next = первый.
2. будет ли last первым.next?
3. @AdanVivero Да. Реализация представляет собой циклический список
Ответ №3:
Вот пример реализации для вашего случая —
import java.util.Iterator;
public class DoublyLinkedList<E> {
// A reference to the root node
private Node<E> root = null;
// attribute for storing the size of the linked list
private int countOfNodes = 0;
// attribute that indicates if the linked list would be iterated in a cycle
private boolean isCircular = false;
/**
* The linked list Node class
*
* @param <E>
*/
@SuppressWarnings("hiding")
class Node<E> {
// attribute for storing the value
private E data;
// attributes for storing the linked list references
private Node<E> previousNode = null;
private Node<E> nextNode = null;
public Node() {
super();
}
public Node(E data) {
super();
this.data = data;
}
public Node<E> getPreviousNode() {
return previousNode;
}
public void setPreviousNode(Node<E> previousNode) {
this.previousNode = previousNode;
}
public Node<E> getNextNode() {
return nextNode;
}
public void setNextNode(Node<E> nextNode) {
this.nextNode = nextNode;
}
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
}
/**
* The iterator implementation
*/
@SuppressWarnings("hiding")
class DoublyLinkedListIterator<E> implements Iterator<E> {
private Node<E> currentNode = null;
public DoublyLinkedListIterator(Node<E> startNode) {
super();
this.currentNode = startNode;
}
@Override
public boolean hasNext() {
return (this.currentNode != null);
}
@SuppressWarnings("unchecked")
@Override
public E next() {
E data = currentNode.getData();
currentNode = currentNode.getNextNode();
if (currentNode == null amp;amp; DoublyLinkedList.this.isCircular()) {
this.currentNode = (Node<E>) DoublyLinkedList.this.getRoot();
}
return data;
}
}
public DoublyLinkedList() {
super();
}
public boolean isCircular() {
return this.isCircular;
}
public void setCircular(boolean isCircular) {
this.isCircular = isCircular;
}
public Node<E> getRoot() {
return root;
}
public void setRoot(Node<E> root) {
this.root = root;
}
public int size() {
return this.countOfNodes;
}
public Iterator<E> iterator() {
return new DoublyLinkedListIterator<>(this.getRoot());
}
public void add(E value) {
Node<E> node = new Node<E>(value);
addAfter(getLastNode(), node);
this.countOfNodes ;
}
public Node<E> getLastNode() {
Node<E> lastNode = null;
Node<E> node = getRoot();
while (node != null) {
lastNode = node;
node = node.getNextNode();
}
return lastNode;
}
public void addAfter(Node<E> parentNode, E value) {
Node<E> newNode = new Node<E>(value);
addAfter(parentNode, newNode);
}
public void addAfter(Node<E> parentNode, Node<E> newNode) {
if (parentNode == null) {
this.setRoot(newNode);
} else {
parentNode.setNextNode(newNode);
}
}
public void addBefore(Node<E> parentNode, E value) {
Node<E> newNode = new Node<E>(value);
addBefore(parentNode, newNode);
}
public void addBefore(Node<E> parentNode, Node<E> newNode) {
if (parentNode == null) {
this.setRoot(newNode);
} else {
Node<E> prevNode = parentNode.getPreviousNode();
parentNode.setPreviousNode(newNode);
newNode.setNextNode(parentNode);
newNode.setPreviousNode(prevNode);
if (newNode.getPreviousNode() == null) {
this.setRoot(newNode);
}
}
}
}
И ниже приведен тест —
import static org.junit.jupiter.api.Assertions.fail;
import java.util.Iterator;
import org.junit.jupiter.api.Test;
class DoublyLinkedListTest {
private final int initialSize = 4;
private DoublyLinkedList<String> list = new DoublyLinkedList<String>() {{
setCircular(true);
for(int i = 0; i < initialSize; i ) {
add("Data " (i 1));
}
}};
public DoublyLinkedListTest() {
super();
}
@Test
void testListSize() {
if (list.size() != initialSize) {
fail(String.format("Expected value for the list's size is %d, whereas obtained value is %d", 4, list.size()));
}
}
@Test
void testLastElement() {
String lastAddedValue = list.getLastNode().getData();
String expectedValue = "Data 4";
if (!expectedValue.equals(lastAddedValue)) {
fail(String.format("Expected value for the last node is %s, whereas obtained value is %s", expectedValue, lastAddedValue));
}
}
@Test
void testAddElementOnTop() {
list.addBefore(list.getRoot(), "Data 5");
String lastAddedValue = list.getRoot().getData();
String expectedValue = "Data 5";
if (!expectedValue.equals(lastAddedValue)) {
fail(String.format("Expected value for the last node is %s, whereas obtained value is %s", expectedValue, lastAddedValue));
}
}
@Test
void testCircularIteration() {
Iterator<String> iterator = list.iterator();
int counter = 0;
final int expectedValue = (initialSize 1) * 2;
while(iterator.hasNext()) {
counter ;
if (counter == expectedValue) {
break;
}
}
if (counter != expectedValue) {
fail(String.format("Expected value for the iteration count is %d, whereas obtained value is %d", expectedValue, counter));
}
}
}
Комментарии:
1. Извините, это не помогает с тем, что я ищу.
2. @AdanVivero — Отредактировал код, чтобы добавить элементы в начало.
3. Изменен код для реализации разделения обязанностей, т. Е. способ фактического хранения данных отделен от способа, которым данные предназначены для чтения, который в этом контексте необязательно может быть «циклическим».
4. Спасибо, но у меня есть конкретные рекомендации о том, как они хотят, чтобы мой код был настроен с использованием определенных методов, частного класса и т.д. Следовательно, работа должна выполняться в рамках моего метода добавления.