#java #data-structures #linked-list #iterator #doubly-linked-list
#java #структуры данных #связанный список #итератор #двусвязный список
Вопрос:
Я пытаюсь реализовать двусвязный список и тестирую его с помощью итератора. По какой-то причине dll возвращает null в конце списка, и я не могу понять, почему. Я был бы очень признателен эксперту, чтобы определить, чего мне не хватает. Заранее спасибо
тест:
void testIterator() {
DoublyLinkedList<Integer> ll = new DoublyLinkedList<>();
for(int i = 0; i < 5; i) ll.addLast(i);
ArrayList<Integer> buf = new ArrayList<>();
for(Integer i : ll) {
buf.add(i);
}
assertEquals("[0, 1, 2, 3, 4]", buf.toString());
}
Тест возвращает:
ожидание [0, 1, 2, 3, 4] но был [0, 1, 2, 3, 4, нулевой]
Двусвязный список
import java.util.Iterator;
public class DoublyLinkedList<E> implements List<E> {
/** Sentinel node at the beginning of the list */
private Node<E> header; // header sentinel
/** Sentinel node at the end of the list */
private Node<E> trailer; // trailer sentinel
/** Number of elements in the list (not including sentinels) */
private int size = 0;
//---------------- nested Node class ----------------
/**
* Node of a doubly linked list, which stores a reference to its
* element and to both the previous and next node in the list.
*/
private static class Node<E> {
private E data;
private Node<E> next;
private Node<E> previous;
public Node(E data, Node<E> previous,Node<E> next)
{
this.data = data;
this.next = next;
this.previous = previous;
}
public E getData()
{
return data;
}
public Node<E> getNext()
{
return next;
}
public Node<E> getPrevious()
{
return previous;
}
public void setNext(Node<E> n)
{
next = n;
}
public void setPrevious(Node<E> p)
{
previous = p;
}
public void setData(E d)
{
data = d;
}
} //----------- end of nested Node class -----------
// instance variables of the DoublyLinkedList
// number of elements in the list
/** Constructs a new empty list. */
public DoublyLinkedList() {
header = new Node<>(null, null, null);
trailer = new Node<>(null, header, null);
header.setNext(trailer);
}
// public accessor methods
/**
* Returns the number of elements in the linked list.
* @return number of elements in the linked list
*/
public int size() { return size; }
/**
* Tests whether the linked list is empty.
* @return true if the linked list is empty, false otherwise
*/
public boolean isEmpty() { return size == 0; }
@Override
public E get(int i) throws IndexOutOfBoundsException {
if((i>size()-1) || isEmpty()) {
throw new IndexOutOfBoundsException("It is not possible to get this indexed value");
}
Node<E> current = header.getNext();
for(int j=0;j<i amp;amp; current != trailer;j ) {
current = current.getNext();
}
return current.getData();
}
@Override
public E set(int i, E e) throws IndexOutOfBoundsException {
Node<E> current = header.getNext();
if (isEmpty() || i > size()-1)
{
throw new RuntimeException("cannot delete either index too big or list is empty");
}
for(int j =0; j<i;j ) {
current = current.getNext();
}
current.setData(e);
return current.getData();
}
@Override
public void add(int i, E e) throws IndexOutOfBoundsException {
if (i < 0|| i > size()-1)
{
throw new RuntimeException("cannot delete either index too big or list is empty");
}
else {
Node<E> current = header.getNext();
for(int j = 0; j< i;j ) {
current = current.getNext();
}
addBetween(e,current.getPrevious(),current);
}
}
@Override
public E remove(int i) throws IndexOutOfBoundsException {
if (isEmpty() || i > size()-1)
{
throw new RuntimeException("cannot delete either index too big or list is empty");
}
Node<E> current = header.getNext();
Node<E> previous = header;
//find the correct node to remove
for (int k = 0; k < i; k )
{
previous = current;
current = current.getNext();
}
Node<E> next =current.getNext();
previous.setNext(next);
next.setPrevious(previous);
size--;
return current.getData();
}
@Override
public Iterator<E> iterator() {
return new DoublyLinkedListIterator();
}
private class DoublyLinkedListIterator implements Iterator<E> {
private Node<E> current;
public DoublyLinkedListIterator() {
current = header.getNext();
}
@Override
public boolean hasNext() {
return current != null;
}
@Override
public E next() {
if(!hasNext()) throw new RuntimeException("No such element");
E res = current.getData();
current = current.getNext();
return res;
}
}
/**
* Returns (but does not remove) the first element of the list.
* @return element at the front of the list (or null if empty)
*/
public E first() {
// TODO
return header.getNext().getData();
}
/**
* Returns (but does not remove) the last element of the list.
* @return element at the end of the list (or null if empty)
*/
public E last() {
// TODO
return trailer.getPrevious().getData();
}
// public update methods
/**
* Adds an element to the front of the list.
* @param e the new element to add
*/
public void addFirst(E e) {
addBetween(e,header,header.getNext());
}
/**
* Adds an element to the end of the list.
* @param e the new element to add
*/
public void addLast(E e) {
addBetween(e,trailer.getPrevious(),trailer);
}
/**
* Removes and returns the first element of the list.
* @return the removed element (or null if empty)
*/
public E removeFirst() {
Node<E> current = header.getNext();
remove(0);
return current.getData();
}
/**
* Removes and returns the last element of the list.
* @return the removed element (or null if empty)
*/
public E removeLast() {
return remove((this.size()-1));
}
// private update methods
/**
* Adds an element to the linked list in between the given nodes.
* The given predecessor and successor should be neighboring each
* other prior to the call.
*
* @param predecessor node just before the location where the new element is inserted
* @param successor node just after the location where the new element is inserted
*/
private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
Node<E> newNode = new Node(e,predecessor,successor);
predecessor.setNext(newNode);
successor.setPrevious(newNode);
this.size ;
}
/**
* Removes the given node from the list and returns its element.
* @param node the node to be removed (must not be a sentinel)
*/
/**
* Produces a string representation of the contents of the list.
* This exists for debugging purposes only.
*/
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
Node<E> current = header.getNext();
while (current.getNext() != null amp;amp; current != null)
{
stringBuilder.append(current.getData());
stringBuilder.append(", ");
current = current.getNext();
}
stringBuilder.replace(stringBuilder.length()-2, stringBuilder.length(), "");
stringBuilder.append("]");
return stringBuilder.toString();
}
public static void main(String [] args) {
//ArrayList<String> all;
//LinkedList<String> ll;
DoublyLinkedList<String> ll = new DoublyLinkedList<String>();
String[] alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
for (String s : alphabet) {
ll.addFirst(s);
ll.addLast(s);
}
System.out.println(ll.toString());
for (String s : ll) {
System.out.print(s ", ");
}
}
} //----------- end of DoublyLinkedList class -----------```
Комментарии:
1. У вас
trailer
в списке есть a со значениемnull
, почему? И если вы пойдете этим путем, убедитесь, что вашiterator
запоминает это в своемhasNext
методе2.
while (current.getNext() != null amp;amp; current != null)
эта строка должна выдавать исключение, если значение null должно было бытьcurrent