- Array Based Linked List - An array based linked list implements the basic functions of a normal single linked list.
There are the conceptual equivalents to nodes, next pointers and head pointers. The functions of a single linked list are
implemented in an almost identical fashion. The benefit of using the array based linked list is the fact that the list will
only take up to a specific amount of memory that is initially defined. The down side to this is that the list can only
contain a specific predefined amount of items. Below is the general concept of the array based linked list.
The array based linked list is generally defined in a 2-dimentional array. Below is the basic concept of what is being
This list will allow 5 items to be inserted into it before it will no longer have any room to add new items. This is the
basic idea behind the use of the structure of the 2-dimentional array. The indices on the left provide the locations of
each 'node'. A node is defined by a single row (as shown below). Each node has a row index. The indices on the top
provide the data and next properties of the 'node'.
The area highlighted is the same concept as a node from a single linked list. The top index at 0 is the location of the
data of the node. The top index at 1 is the pointer to the index of the next node. The array above has 5 nodes at
indices 0 - 4. As a single linked list the data structure has to hold a head pointer. This data structure holds a head
pointer however in this specific implementation it is a int. The head of the list is the pointer that holds the index to
the first node. The first node holds the index to the next node and so on. The last node in the list will hold a next
value of -1. This will indicate the end of the list. The fact that indices are taken as elements are added into the
structure makes a requirement for a free list head. This free list is incorporated into the same 2-dementional array.
Just as the head is an int the free list pointer is an int. The picture below describes how both pointers point to different
indices at the same time. ( H represents Head and F represents Free head )
Now the data structure is composted of 3 major elements. The head pointer, the free head pointer and the
2-dimentional array. The list has to be initialized correctly to allow the list to be used. The list should be initialized as
The head pointer is initialized to -1. This is because there are no elements in the list to begin with. As seen above
the free head is initialized to 0. This is because this is the first free index in the list. As in the single linked list the
free head points to a node that has a next. The next of the free head is initialized to 1. This is because 1 is the next
available index after 0. This continues throughout the free list until at index 4 the next value is -1. This means that 4 is
the last available index in the free list.
Adding to the list is a little more complex than in a single linked list. The example below is adding 18 to the list. The
head pointer and free head pointers need to be updated. The head is changed from -1 to the first available index from
the free head list ( the free head value ). The heads next value is then set to -1 this declares that the list only has 1
node and it has no next node. The free head is then updated to equal its next node removing the first node from the
free list. Thus the size of the list is increased by 1 and the size of the free list is decreased by 1.
Add First: Below is a sequence of the add First algorithm. As each item is inserted into the front of the list the head
and free head are updated accordingly. The sequence from left to right is the addition of 18, 19, 20, and 21. The new
items are inserted wherever the free head was pointed last. (Note that inserting first does not shift elements).
The string representation of the final step above is "18 : 19 : 20 : 21 : 22" The list now contains 5 elements. Note that
in the last step the free head is now gone. This is because the free head is now set to -1. There are no available
indices to insert new elements at. This means that the list is full and cannot hold any more elements.
Add Last: To add last to a single linked list, a pointer must be created to travel down the list to find the next available
location to add the new data. When you reach the last value you want to set its next to the newly inserted data. This
is fairly straight forward and the only special cases are if the list is empty (H = -1) and there is no free space to add
the new data (F = -1 ).
Remove First: To remove first from a linked list the head is set to its next node. If the next node is null then the
new list is now empty.
Remove Last: The remove last algorithm is similar to the add last algorithm, however instead of adding to the last
last index the remove last algorithm requires remembering the index prior to the last index. This is because to delete
the last value, the prior index must set its next to null. This will remove the last value, the data of the last index does
not need to be modified in any way. The free head should now point to the index of the value that was removed.
Remove Value: Removing every instance of a value is one of the most complex algorithms because it has more
special cases than other simpler algorithms. Below illustrates the a break down of each case removing the value (7).
The first case on the left is an example of a list containing the remove value (7) at each position in the list. This
is a special case that can be managed by using a last saved valid index algorithm. This is based off of the idea
that each index is either valid or invalid. Valid indices do not contain the remove value (7). Invalid indices do contain
the remove value (7). If the last saved value remains -1 throughout the entire iteration of the list, the list is now empty.
The second case is the case where the first X elements are the remove value (7). This case can easily be taken care
of. While the first value is the remove value remove it, update pointers and continue. This will remove every value at the
the beginning of the list that is the remove value (7). This is only a section of the entire algorithm but is best to be
taken care of first.
The third case is an example of when the first and last indices contain the remove value (7). The first remove value can
be taken care of using the second case, however the fact that the last index of the list contains the remove value
means that the last saved valid must point to a -1.
The forth case is an example of connecting last saved valid indices. The remove value (7) must be removed from
index 4, 2, and 0. This creates a gap between the 2 valid indices. The pointer of the first valid index must point to the
next valid index before continuing.
Any other algorithms for this data structure mimic the actions of the pointer single linked list. The only other actions to
take are: updating the free head list, insuring the list is not full before trying to insert and ignoring the data values of
- Current Projects -