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

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 定义为私有内部 class），外部 class 看起来像

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

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

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

通过此实现，方法 returns 存储在索引 currentPos 指向的对象的副本。索引号本身 (currentPos) 永远不会透露给调用它的代码，并且由于 returned 对象是存储对象的副本，因此对副本所做的任何更改都不会自动对存储的对象进行更改版本。要存储对象的更新版本，用户必须删除 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;
}

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

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

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

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

What is an array linked structure or node array?

java

arrays

linked-list

arraylist

data-structures