什么是数组联结构或节点阵列？ [英] What is an array linked structure or node array?

问题描述

我是一对夫妇的Java数据数据结构练习。

I am a couple of java data data structure exercises.

下面是我目前做运动

...添加阵列联层次结构的整体结构。请使用以下的名称： 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编译器控制，所以你没有明确引用它们。如果你觉得这些结构为数组VS链表的，你可能会迷惑自己。你真的应该考虑阵列VS指针。我知道你问在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）从未显露到code调用它，而且由于返回的对象是存储对象的副本，该副本所做的任何更改将不会自动为存储的版本进行。存储对象的更新版本，用户必须删除存储在对象信息[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;
}

这将实现在链表返回该项目的地址。使用指针将参照返回一个对象，而使用数组将返回值的对象。在此实现对对象所做的任何更改将立即对存储的对象，因为code调用此方法具有对存储的对象直接访问进行。

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和节点类型。这些都不是在C ++中的特殊数据类型。他们可以很容易被富或汽车等，此外，他们既可以指的是相同的数据类型。

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屋！