- Home

   - Forums

   - Programming

   - Development

   - Projects

   - Articles

   - Tutorials

   - Snippets

   - Synapse Engine

 

  - 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

PE