Java中的双链表

Question

我必须实现类"DoubleChainedList"one_answers";Elem"。DoubleChainedList管理一个双链表，而Elem是关联的节点类，具有指向后继节点和前导节点的指针。

我必须实现以下方法:

public void removeAtIndex(int i)//移除位置i的元素。If i>length-1 or i<0抛出IndexOutOfBoundsException

• public int[] toArray()//返回列表作为数组

DoubleChainedList

import java.util.Collections;
import java.util.LinkedList;
public class DoubleChainedList {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(4);
list.add(1);
list.add(7);
list.add(2);
list.add(9);
Integer[] arr = list.toArray(new Integer[0]);
Collections.sort(list);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
public int[] toArray() {
Integer[] arr = list.toArray(new Integer[0]);
return null;
}
public int smallest() {
int min = Integer.MAX_VALUE;
// Check loop while head not equal to NULL
while (head != null) {
if (min > head.data)
min = head.data;
head = head.next;
}
return min;
}

Elem:

public class Elem {
public static void main(String[] args) {
// TODO Auto-generated method stub
}
private Node head = null;
private Node tail = null;
public class Node {
public int data;
public Node next;
public Node prev;
}
}

我的问题:它显示我以下错误:头部无法解决到一个变量，我的问题是如何修复它?

Answer 1

您的DoubleChainedList应该有head和tail。它们分别是列表的开头和结尾。列表中的每个节点(您已被指示将其命名为Elem)应该具有类型为Elem的prev和next。您的Elem类包含另一个名为Node的类—这似乎是多余的，并且可能会使您感到困惑—将其扁平化到Elem类中。

你的smallest()方法包含一个错误，因为它正在改变列表。创建一个单独的Elem变量来导航列表的内容——不要在这里更改head或tail。

返回Integer会引起误解。MIN_VALUE，当列表为空时。如果列表为空，则考虑抛出异常。您将发现，您必须在列表实现的几乎每个方法中为is-empty情况定义特殊处理。

public class DoubleChainedList {
private Elem head;
private Elem tail;
// using protected here because you aren't exposing this to consumers
// but its available for extension
protected class Elem {
private int data;
private Elem prev;
private Elem next;
}
public int smallest() {
if (head == null) {
throw new Exception("list is empty - no smallest value");
}
int min = Integer.MAX_VALUE;
Elem cursor = head;
while (cursor != null) {
min = Math.min(min, cursor.data);
cursor = cursor.next;
}
return min;
}
}