我正在循环DoublyLinkedList类以及Node内部类中实现add（E）方法。
节点应该实现为私有内部类。
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;
}
}
}
修改了最小变化的代码（只是添加的其他情况）：
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;
}
}
}
编辑：
这里有一个错误：而不是这一行this.next = prev;它应该有this.prev = 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 + ", "));
}
}
我做了什么：为了创建一个循环的双链表，我保留了对尾部的引用。
以下是您案例的示例实现 -
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 && 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));
}
}
}