What is an array linked structure or node array?

Question

I am a couple of java data data structure exercises.

Here is the exercise I am currently doing

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?

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

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 {
           ....
       }
 }

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?

Ask your teacher what he meant. The terms "array-linked list" and "array-linked hierarchy" seem ambiguous to me. — Robert Harvey, Jan 19 '15 at 19:17
No it doesn't make sense when you've already implemented linked lists. — gknicker, Jan 19 '15 at 19:28
It *may* be that array-linked means that links should be implemented by indices of an array. — laune, Jan 19 '15 at 19:28
This is a technique that is used if you have a limited set of nodes of a fixed type, held in an array Node[] = new Node[CAPACITY], one field of Node being an int - the index. The payload is anything, as usual. You have, initially, all nodes in an avail list, linked 0->1->2->... — laune, Jan 19 '15 at 19:30
Allocation takes from, deallocation returns to avail. Everything else proceeds as usual. --- But I may be terribly wrong. — laune, Jan 19 '15 at 19:31
The data that should be stored in a node (or message). Node = link(s) + "payload". — laune, Jan 19 '15 at 20:09
so how does this structure work better for limited set of nodes of fixed type? i don't see the difference between this and a regular linked list. — committedandroider, Jan 19 '15 at 20:25
@laune I think you're right. Is what I said of an example what to implement correct ? — committedandroider, Jan 19 '15 at 20:58

score 1 · Accepted Answer · answered Mar 25 '15 at 02:56

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++.

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

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

ItemType ArrayList::getNextItem()
{
    currentPos++;
    return 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.

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

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.

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.

What is an array linked structure or node array?

1 Answers1

Linked