Better Array

Please use comments so I can understand the code better, thank you

Problem Description:

This lab will use the concept of a doubly-linked list to provide the capability for a more flexible array structure. The traditional array while being very efficient as regards execution time is relatively inflexible. It is a modern programming language implementation of a block of memory, accessed as a fixed number of data elements.

Good points:

No meta-data in memory (no wasted memory)

Random access with a simple calculation

Access to known index in constant time

Bad points:

Number of elements is fixed (cannot be expanded dynamically)

Each elements location in the array is fixed (no insertions)

In order to make a better array we will add meta-data in memory (bad) and give up the ability to access a known index in constant time (bad). However, we will gain the ability to extend the array indefinitely (good) and to insert or delete an element anywhere in the array (good).

The key is to replace a block of memory and data elements adjacent to each other (an array) with a doubly-linked list, each node containing a data element (better array). The linked list gives us the ability to (a) add new elements indefinitely and (b) insert or delete an element anywhere in the list. The use of double linking gives us the ability to access an arbitrary sequence of elements more efficiently than repeated sequential access from the head-node. It also gives us the ability to sort the nodes in-place rather than duplicating the array size as workspace.

The exercise will involve three classes, the node class, the linked list class and the main program that instantiates, uses, sorts and tests an array.

The node class will be used to create each individual node as it is added to the list. It should contain no more than attributes for the data and the fore- and back-links and necessary methods for setting and retrieving the data value.

public node(int v) class constructor, v = data value

public node( ) class constructor

public int get( ) returns the data value from the node

public void set(int v) saves the data value v in the node

The linked list class will define the array-like interface between the main program and the linked list array implementation. It will provide for creation of the head and tail nodes and initialization of them. It will also maintain an integer value containing the current number of nodes in the array. A second integer value will contain the index of the most-recently addressed node and a node reference value will refer to the most-recently addressed node itself.

public BetterArray(int n) class constructor, n is the initial allocation (the starting array size).

public BetterArray( ) class constructor, use default initial allocation

public int get(int index) uses the index to access a specific array element (node) and returns the value to the caller.

public void put(int value, int index) uses the index to find the specific array element (node) and saves the data value in the node. If the requested node is outside the current size of the array (linked-list), expand the list to accommodate the new element.

public void insert(int value, int index) uses the index to find the specific array element (node) and saves the data value in the preceding node. If the requested node is outside the current size of the array (linked-list), expand the list to accommodate the new element.

public void delete(int index) uses the index to find the specific array element (node) and deletes it from the list.

Testing:

The main class will create an object of the BetterArray class and run it through some tests.

Create the object and make its size 10 elements.

Store a random sequence of 10 numbers in the array.

Read back the elements 0 thru 19 and display the values.

Store a random sequence of 20 numbers into the array.

Read back the elements 0 thru 19 and display the values.

Insert the number 999 immediately before element 14.

Read back the elements 0 thru 20 and display the values.

Delete element 15

Read back the elements 0 thru 19 and display the values.

Create another object and make its size 1000 elements.

Fill it with randomly-generated integers

Sort the array in either increasing or decreasing order

Your program will test the result by comparing each element of the sorted array to the one adjacent to it and reporting any out-of-order results.