Linked Lists - Advanced Topics in Java: Core Concepts in Data Structures - page 100

3.14 Storing a Linked List Using Arrays
We have seen how to create a linked list using dynamic storage allocation. When we need to add another node to a
linked list, we request the storage for that node. If we need to delete a node from a linked list, we first delete it logically
by changing pointers and then physically by freeing the storage occupied by the node.
It is also possible to represent a linked list using arrays. Consider, once again, the following linked list:

top

36 15 52 23

We can store this as follows:

data next

0
1
2
3
4
5
6
7
8
9

top

5

15 7

23 -1

36 1

52 3

Here, the links (pointers) are merely array subscripts. Since an array subscript is just an integer, top is an int
variable, and next is an int array. In this example, the data happens to be integers (so data is an int array), but it
could be of any other type, even an object.
The value of top is 5, so this says that the first item in the list is found at array index 5; data[5] holds the data
(36, in this case), and next[5] (1, in this case) tells us where to find the next (second) item in the list.
So, the second item is found at array index 1; data[1] holds the data (15), and next[1] (7) tells us where to find
the next (third) item in the list.
The third item is found at array index 7; data[7] holds the data (52), and next[7] (3) tells us where to find the
next (fourth) item in the list.
The fourth item is found at array index 3; data[3] holds the data (23), and next[3] (-1) tells us where to find the
next item in the list. Here, we use -1 as the null pointer, so we've come to the end of the list. Any value that cannot be
confused with a valid array subscript can be used to denote the null pointer, but -1 is commonly used.
All the operations described in this chapter for working with linked lists (for example, adding, deleting, and
traversing) can be performed in a similar manner on linked lists stored using arrays. The main difference is that,
previously, if curr points to the current node, curr.next points to the next node. Now, if curr points to the current
node, next[curr] points to the next node.
One disadvantage of using arrays to store a linked list is that you must have some idea of how big the list is
expected to be in order to declare the arrays. Another is that storage for deleted items cannot be freed or garbage-
collected. However, the storage can be reused to store new items.