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

For example, suppose we have a linked list of at most 50 integers pointed to by top . If num and next are the fields
of a node, we can store the integers in an array saveLL with the following code:

int saveLL[50], n = 0;
while (top != null & n < 50) {
saveLL[n++] = top.num;
top = top.next;
}

On completion, the value of n will indicate how many numbers were saved. They will be stored in
saveLL[0..n-1] .

3.13 Arrays vs. Linked Lists
Arrays and linked lists are the two common ways to store a linear list, and each has its advantages and disadvantages.
The big difference between the two is that we have direct access to any element of an array by using a subscript,
whereas to get to any element of a linked list, we have to traverse the list starting from the top.
If the list of items is unsorted, we must search the list using a sequential search whether the items are stored in an array
or a linked list. If the list is sorted, it is possible to search the array using a binary search. Since binary search requires direct
access to an element, we cannot perform a binary search on a linked list. The only way to search a linked list is sequential.
Inserting an item at the tail of a list stored in an array is easy (assuming there is room), but inserting an item at the
head requires that all the other items be moved to make room for the new one. Inserting an item in the middle would
require about half of the items to be moved to make room for the new one. Inserting an item anywhere in a linked list
is easy since it requires setting/changing just a couple links.
Similarly, deleting an item from a linked list is easy regardless of where the item is located (head, tail, middle).
Deleting an item from an array is easy only if it is the last one; deleting any other item would require other items to be
moved to “close the space” previously occupied by the deleted item.
Maintaining an array in sorted order (when new items are added) is cumbersome since each new item has to be
inserted “in place,” and, as we've seen, this would normally require that other items be moved. However, finding the
location in which to insert the item can be done quickly using a binary search.
Finding the position at which to insert a new item in a sorted linked list must be done using a sequential search.
However, once the position is found, the item can be quickly inserted by setting/changing a couple links.
Table 3-1 summarizes the strengths and weaknesses of storing a list of items in an array versus storing the items
in a linked list.

Table 3-1. Storing List of Items in an Array vs. in Linked List

Array Linked List

Direct access to any element Must traverse list to get to element

If unsorted, sequential search If unsorted, sequential search

If sorted, binary search If sorted, sequential search

Easy to insert item at the tail of the list Easy to insert item anywhere in the list

Must move items to insert anywhere but the tail Easy to insert item anywhere in the list

Deletion (except the last one) requires items to be moved Deleting any item is easy

Need to move items when adding a new item to a sorted list Adding a new item to a sorted linked list is easy

Can use binary search on a sorted list to find the position at
which to insert new item

Must use sequential search to find the position at
which to insert a new item in a sorted linked list