Embedded Files
If a list is static and small then an array could be used for a list.
This will pose a problem. We will need to know the maximum number of items to be held in the list before we declare the array.
Adding items to a list
Adding items to a list
Adding items to the end of an array list is easy, we just need to keep track of the index of the end of the list. If the list is empty the index is -1. As we add items, we need to increment the index.
We do need to check however that there is space to add an item, if not the list should throw an exception.
Removing Items from a list
Removing Items from a list
Removing an item from the end of a list is also straight forward, we follow the pointer to the end of the list and remove the data held in that element. The end of list pointer is then pointed at the the index -1.
A problem posed by using an array is how do we deal with removing and adding items if they are not at the end of the list?
Inserting Items into a list
Inserting Items into a list
To insert an item into a list, we must first make space for the item by copying all the items from the location we want to insert the item onwards to the next location.
We then can add the item in the space we have created and we also need to increment the End of List pointer.
The additional problem this may cause is that by moving a all the items along to make space, is that if the list is full, the last item on the list may be removed...
Advantages and Disadvantages of using an Array as a List
Advantages and Disadvantages of using an Array as a List
Advantages
Advantages
Once the array has been declared there is not time spent creating the space for an item if it is added to the end of a list.
If the index of the item is know, then there is direct random access to that item making it quick to retrieve the data held at that index.
Adding or removing items at the end of the list is quick because you have direct access to that item via the pointer.
Disadvantages
Disadvantages
An array is static, so can't hold more than the number of items specified when the array is declared.
The empty elements in the list take up space in the computer's memory.
Inserting an item is slow because all items after the insertion point need to be copied to the next element. There is a risk that if the list is full the last item may be removed.
Removing an item that is not at the end of the list is slow because all the items after the item deleted need to be copied to the previous element
Can an Array List be Dynamic?
Can an Array List be Dynamic?
Sort of...
We can turn our static array list into a dynamic list by testing to see if there is enough space to add a new item to the list. If not a new array could be created that is double the length of the original. All the items in the original array should be copied into it. Then this array should replace the first.
This is of course expensive in terms of the time needed to do this (On).
We still have the problem that we create a lot of new empty elements in the larger array that may never be used.
Report abuse