-{ Brokendust }-

- 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

created.

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

below.

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

deleted indices.

- About Brokendust - I am a computer science major with a minor in mathematics. My interests include programming, 3d Design and application development. I document everything I do and write articles explaining things both as a way to remember what I have learned before and as way to show others how to accomplish things. I do not post tutorials that do not live up to my expectations. Each article is toughly revised to be quality work. I document advanced computer science topics that are not explained clearly with clear illustrations and step by step algorithm design.

- Current Projects -

3D MGR

ABLL