How does an array of nodes work?

Question

This is based off my other question. What is an array linked structure or node array?

I was trying to do this exercise

One of the responses to my other question asked me to ask my teacher to clarify what an array-linked hierarchy is. After I asked her, she said that it's just an array of nodes.

I think the array of nodes goes with what laune said, in that " 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->", with payload being the data that the node holds, which includes, the data and its links its holding .

So from all of that, this is what the data structure looks like in my head

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

What advantages dos this array of nodes data structure have to just regular linked list and array lists? I can't see a situation of why you would want a data structure like this. To me, its just another from of ArrayList because array lists are generic, their arrays could work with any type, including a list node.

Answer 1

I tend to think of linked lists as being better for insertions and deletions while array lists are more suited for searching.

Some advantages to array list:

-An array list's memory is consolidated opposed to a linked list's whose disjointed node objects will be located at sparse addresses. Having all your objects located close to each other can improve caching and memory look ups.

-Searching for an nth element using an array list is an array index which is an O(1) operation; while searching for an nth element in a linked list is an O(N) operation.

Some advantages to linked lists:

-Array lists typically allocate more memory than is necessary since every time capacity is reached an entirely new block of memory needs to be allocated and the data from the original array has to be copied over.

-Remove operations can be less expensive since memory above the address removed doesn't need to be shifted down.

Edit: Here's is a great answer to your question When to use LinkedList over ArrayList?