Java中的双链列表

Question

我必须实现类"DoubleChainedList"和"Elem"。DoubleChainedList管理一个双链列表，Elem是关联的节点类，指针指向后继节点和前驱节点。

我必须实施以下方法：

public void removeAtIndex（int i）//删除位置i处的元素

• public int[]toArray（）//将列表作为数组返回

双链列表

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;
    }

要素：

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;

    }

}

我的问题：它显示了以下错误：head无法解析为变量，我的问题是如何修复它？

Answer 1

您的双链列表应该有头部和尾部。这些分别是列表的开头和结尾。已指示您命名Elem的列表中的每个节点应具有prev和next类型的Elem。您的Elem类包含另一个名为Node的类-这似乎是多余的，可能会让您感到困惑-将其展平到Elem类中。

您的最小（）方法包含一个错误，因为它正在更改列表。创建一个单独的Elem变量来导航列表的内容-不要在这里更改head或ail。

返回整数有误导性。列表为空时的最小值。如果列表为空，则考虑抛出异常。您将发现，在列表实现的几乎每个方法中，都必须为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;
  }
}