java - 什么是数组链接结构或节点数组？

Question

我是几个java数据数据结构练习。

这是我目前正在做的练习

Add an array-linked hierarchy to the overall structure. Use the following names: AbstractNodeArrayMyList, NodeArraySorted, and NodeArrayUnsorted

我已经实现了抽象数组列表、排序数组列表、未排序数组列表、抽象链表、排序链表和未排序链表。

但是我对这个数组链接结构或节点数组是什么感到困惑。

我尝试做 google search对于数组链表或结构，但我得到的只是导致数组和链表之间存在差异的搜索。谁能澄清或确认我对这个节点数组或数组链接结构实际上是什么的初步看法？

当我想到节点时，我会想到链表中的节点，包含数据的东西，以及对其所连接的节点的引用，例如 来自these lecture notes for ListNode.java

 public class ListNode {
         int data;
         ListNode next;
         public ListNode() {
               this(0, null);
         }
        public ListNode(int data) {
                this(data, null);
        }
        public ListNode(int data, ListNode next) {
               this.data = data;
              this.next = next;
        }
    }

当我想到数组时。我想到了支持随机访问的东西，就像你可以访问数组中的任何元素，并且需要恒定的时间。那么节点数组看起来像这样吗？ (您将 ListNode 定义为私有(private)内部类)并且外部类看起来像

public class NodeArray {
       private ListNode[] elementData;
        ...
       private class ListNode {
           ....
       }
 }

我不认为我最初的想法是正确的，因为通用数组列表的整个想法是它可以处理任何类型的数据。那么为什么要为 ArrayNode 提供一个特殊的类呢？

Answer 1

链接列表可以是基于数组的，也可以是基于指针的。如果您学过 C++，您可能熟悉指针。它们也存在于 Java 中，但它们是由 java 编译器在幕后控制的，因此您不必显式引用它们。如果您将这些结构视为数组与链表，您可能会感到困惑。您确实应该考虑数组与指针。我知道您在 java 中问过这个问题，但由于您没有在 java 中显式使用指针，因此查看 C++ 中的示例可能更有意义。

假设您有一个列表类，ArrayList 和 PointerList。 ArrayList 可能设置如下:

class ArrayClass
{
public:
// Default constructor 
ArrayClass();

// Returns the next item in the list using currentPos
// If the end of the list is reached, 
// currentPos is reset to begin again.
ItemType getNextItem();

//other methods

private:
    int length;                // Number of items
    ItemType info[MAX_ITEMS];  // Array of items
    int currentPos;            // List iterator
};

使用基于数组的链表实现 getNextItem() 看起来像这样:

ItemType ArrayList::getNextItem()
{
    currentPos++;
    return info[currentPos];
}

通过此实现，该方法返回存储在 currentPos 指向的索引处的对象的副本。索引号本身 (currentPos) 永远不会向调用它的代码透露，并且由于返回的对象是存储对象的副本，因此对副本所做的任何更改都不会自动对存储版本进行。要存储对象的更新版本，用户必须删除 info[currentPos] 处存储的对象，然后在其位置添加新版本。希望这是有道理的。

现在让我们看看PointerList。它可以这样定义:

class PointerList
{
public:
// Default constructor : 
PointerList();

// Returns the next item in the list using currentPos
// If the end of the list is reached, 
// currentPos is reset to begin again.
ItemType getNextItem();

//other methods

private:
    int length;             // Number of nodes on list
    NodeType* listData;     // List head ptr
    NodeType* currentPos;   // List iterator
};

基于指针的 getNextItem() 的实现可能如下所示:

ItemType PointerArray::getNextItem()
{
    ItemType item;
    if (currentPos == NULL)
    {
        currentPos = listData;
    }
    else
    {
        currentPos = currentPos->next;
    }
    item = currentPos->info;
    return item;
}

此实现将返回链表中项目的地址。使用指针将通过引用返回对象，而使用数组将通过值返回对象。在此实现中对对象所做的任何更改都将立即对存储的对象进行，因为调用此方法的代码可以直接访问存储的对象。

在上面的两个示例中，不必担心 ItemType 和 NodeType。这些不是 C++ 中的特殊数据类型。它们可以很容易地是 Foo 或 Car 等。此外，它们都可以引用相同的数据类型。

我希望这是有道理的。如果您还有其他问题，请告诉我。