什么是数组链接结构或节点数组? [英] What is an array linked structure or node array?

问题描述

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

I am a couple of java data data structure exercises.

这是我目前正在做的练习

Here is the exercise I am currently doing

在整体结构中添加一个数组链接的层次结构.使用以下名称:AbstractNodeArrayMyList、NodeArraySorted 和 NodeArrayUnsorted

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

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

I've already implemented abstract array list, sorted array list, unsorted array list, abstract linked list, sorted linked list, and unsorted linked list.

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

However I am confused about what this array linked structure or node array is.

我尝试对数组链表或结构进行谷歌搜索但我得到的只是导致数组和链表之间存在差异的搜索.谁能澄清或确认我对这个节点数组或数组链接结构实际上是什么的初步意见?

I tried doing a google search for an array linked list or structure but all I got was searches that resulted in difference between array and linked list. Can anyone clarify or confirm my initial opinions of what this node array or array linked structure actually is?

当我想到一个节点时，我会想到一个链表中的一个节点，一个包含数据的东西，以及对它所连接的节点的引用，比如来自 ListNode.java 的这些讲义

When I think of a node, I think of a node in a linked list, something that contains data, and the reference to the node it is connected to, something like from 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 定义为私有内部类)并且外部类看起来像

And when I think about array. I think about something that supports random access, like you can access any element in the array and it would take constant time. So would a node array look something like this? (you define the ListNode as a private inner class) and the outside class would look like

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

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

I didn't think my initial idea was right because the whole idea of the generic array list is that it would work with any type of data. Why have a special class for ArrayNode then?

推荐答案

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

Linked lists can either be array-based or pointer-based. If you've studied C++, you're probably familiar with pointers. They also exist in Java, but they're controlled by the java compiler behind the scenes, so you don't explicitly reference them. If you think of these structures as arrays vs linked lists, you'll probably confuse yourself. You really should be thinking arrays vs pointers. I know you asked this question in java, but since you don't explicitly use pointers in java, it might make more sense to see an example in C++.

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

Let's say you have a list classes, ArrayList and PointerList. ArrayList might be set up like the following:

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() 实现如下所示:

The implementation of getNextItem() using an array-based linked list would look something like this:

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

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

With this implementation, the method returns a copy of the object stored at the index currentPos points to. The index number itself (currentPos) is never revealed to the code that called it, and since the returned object is a copy of the stored object, any changes made to the copy won't automatically be made to the stored version. To store the updated version of the object, the user would have to delete the stored object at info[currentPos], then add the new version in its place. Hopefully this makes sense.

现在让我们看看PointerList.它可能是这样定义的:

Now let's look at PointerList. It might be defined like so:

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() 的实现可能如下所示:

The implementation of the pointer-based getNextItem() could look like this:

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

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

This implementation will return the address of the item in the linked list. Using pointers will return an object by reference, whereas using an array will return an object by value. Any changes made to the object in this implementation will immediately be made to the stored object since the code that called this method has direct access to the stored object.

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

In both of the above examples, don't worry about ItemType and NodeType. These aren't special data types in C++. They could just as easily be Foo or Car, etc. Also, they can both refer to the same data type.

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

I hope this makes sense. Let me know if you have further questions.

这篇关于什么是数组链接结构或节点数组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！