codemorphis.com Forum Index codemorphis.com
Software development: pure and simple.
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Programming Tip #13: The Linked List Component

 
This forum is locked: you cannot post, reply to, or edit topics.   This topic is locked: you cannot edit posts or make replies.    codemorphis.com Forum Index -> Visual Programming Forum
View previous topic :: View next topic  

Please rate on a scale of 1-5 (5 being max)
how helpful (clarity, ease of understanding, relevance) this article was for you.
You must be logged in to vote.
1
0%
 0%  [ 0 ]
2
0%
 0%  [ 0 ]
3
0%
 0%  [ 0 ]
4
0%
 0%  [ 0 ]
5
100%
 100%  [ 1 ]
Total Votes : 1

Author Message
CodeMorphis



Joined: 02 Dec 2003
Posts: 252

PostPosted: Fri Nov 19, 2004 3:16 am    Post subject: Programming Tip #13: The Linked List Component Reply with quote

Programming Tip #13: The Linked List Component

The Linked List component represents a common structure in computing used to store a list of data. You can use a Linked List component to maintain data lists throughout the lifetime of your program for quick access and updating.

The purpose of a linked list is similar to that of an array (see http://www.codemorphis.com/forums/viewtopic.php?t=34 for a treatment on the array component) but the two data structures have differences in the way that they are stored in memory which give them different properties. This makes each structure more suitable for certain applications and programming situations.

There are several services that are identical in usage in and in purpose for both the Linked List and Array components. See http://www.codemorphis.com/forums/viewtopic.php?t=34 for explanations of how to use the “Add item(s) ”, “Get item”, “Delete”, “Insert”, “Num items”, “Find item”, and “Print”.

The Linked List component has several services not available to the Array component that are related to the way the linked list data structure is stored in RAM memory. In order to understand the differences, let’s first take a look at the physical difference between an array and a linked list.



In memory, an array occupies a contiguous block. This makes an array an ideal data structure for random access, where we want to quickly access a given element. Since the elements of the array are physically stored one after another, it is a simple matter of computing element offsets from the start of the array in order to gain access to an element for reading or writing. The Synopsis Array component contains such a data structure, however, you are not required to understand or perform these array-offset computations – they are done for you so as to simplify the interface. But understanding the basic physical properties of the array data structure can be helpful when designing your program. If you need to have fast access to data elements then the array component might be ideal for your program. While quick access is an advantage for using an array, a disadvantage is that if the array gets very large it can be computationally expensive to add and delete elements. An analogy of an array could be a set of books in a bookshelf. If you need to add a new book but the shelf is now too small to accommodate the larger set of books then you have to move all of the books to a larger shelf that has more space.



A linked list differs from an array in that the elements of a linked list are not necessarily stored contiguously in memory, one after another. You can think of a linked list as a set of beads strung together with string. To add a new bead at the front of end of the chain you simply tie the bead with a piece of string. To insert a new bead in the middle of the chain you simply untie two connected beads and introduce the new bead. So we can see that insertion and deletion operations can be much faster for linked lists than for arrays, particularly if we have many elements stored in memory. The disadvantage of using a linked list, however, is that to find an element we have to start at the beginning or end of the chain and traverse the elements one at a time. Thus, a linked list does not offer random element access as does an array and therefore has slower access times.

The choice between an array and a linked list for storing/accessing data is therefore one of speed versus memory management efficiency.

The main services of the Array component such as “Add item(s) ”, “Get item”, “Delete”, “Insert”, “Num items”, “Find item” are available to the Linked List component. This gives a common interface for the two components to make it easier to manipulate the components – you don’t have to understand the physical properties of the two data structures in order to user them.

The additional services offered by the Linked List component have to do with the efficient access of the elements. You can use the “Get item” service to retrieve an element with a given index but the retrieval will sequentially move from element to element starting at the beginning of the linked list. If you are repeatedly accessing elements such as the fourth, then the fifth then the sixth, etc. for example then this will result in wastage, since the retrieval for each element will always start from the beginning.

To facilitate the efficient access of elements, the linked list has a current element pointer, which marks a current element in the list that we are examining. With the current element defined, we can move forwards or backwards through the list and quickly access elements. If we wanted to access the fourth, fifth and then sixth elements for example, we would move to the fourth element then advance twice to access the fifth and then the sixth elements. This results in much faster data access then the sequential “random” access offered by the “Get item” service.

Let’s take a look at how to use the current element of the linked list. In the program below, we have added five string elements to the linked list using the “Add item(s)” service. The “Print” service is used to output the linked list to the console output area.



Here’s our program with two new components added. We call the “Set cur ind” service to set the index of the current element to 2, as indicated in the input argument editor. Since indices are always 0 (zero) offsets in Synopsis, an index of 2 corresponds to the third element in the linked list (0 offsets are used to respect traditional computing conventions). We use the “Get cur” service to retrieve the element stored at the current element, i.e. the third element since we set 2 as the current element index. We can see the result in the console output area as written by the Console Print component.



In the program snapshot below, we have introduced a call to the “Move next” service (in the component named “Serv Call 3”). This causes the current element pointer to move forward in the list, thereby referencing the fourth element. The result is seen in the console output area.



If we connect the component “Serv Call 3” to the “Move prev” instead of the “Move next” service of the connected Linked List component, then the current element is moved back instead of forward. This results in the second element being defined as the current element, as we can see in the output result.



In the snapshot below, we have changed component “Serv Call 1” to use the “Set cur” service instead of the “Get cur” service. This allows us to the change the value of the current element in the list. Since this component follows the “Move prev” call, we wind up changing the value of the second element. Recall that the “Set cur ind” service set the third element as current (index of 2). We set the value of input data port 0 of “Serv Call 1” to “New element”.



If we set the service of “Serv Call 1” to the “Del at cur” service then we can delete one or more elements starting at the current element. In the example, below, we set input data port 0 of “Serv Call 1” to 1, to indicate that one element should be deleted. We can see the result of the output in the program snapshot below.



“Move prev” and “Move next” services return a TRUE or FALSE result in output data port 0 to indicate whether or not the current element is defined after the operation is executed. Thus, if we get a value of TRUE then we know that there is an element before or after the current element, depending on the choice of the “Move prev” or “Move next” service. This value allows us to know if we can continue moving backwards or forwards through the elements of the list.

Here is an example of when we would need to use this information. In the program below we first add the five elements to the list as before. Then with component “Serv Call 2” we set the current element index to 4 with the “Set cur ind” service call. Since we have 5 elements in the list, an index of 4 means the last element in the list. We then test the output value of the component to see if the current element is set. This boolean value is passed to the component “Comp 2”. If the current element is defined then we get the value of the current element, print it to the console output area and then move to the previous element. The output value of “Serv Call 3” is also fed into “Comp 2” so as to test if the current element is still defined, i.e. there is another element to be traversed in reverse order. Process control moves from “Serv Call 3” back to “Comp 2” so that we loop until no more elements occur before the last element printed. The result is that we traverse the entire linked list in reverse order and on each iteration, print out the current element’s value.



You can download this program here:
http://www.codemorphis.com/articles/tip13/reverse_list.vpd

We could have implemented this program using the “Get item” service which uses an index as argument. But the “Get item” service will start from the beginning of the list and “count through” the elements to get to the required element. You can see that in our program, using the “Get item” service this way will result in a slower program if we have many elements in the list, since we would have to traverse the elements in the list many times for nothing.

Again, the choice between the Linked List component and the Array component depends on how much data you are storing and how you need to access the data. If the amount of data is small, it will not make much of a difference which data structure you use. But if you have a huge amount of data and you need to make many insertions and deletions then using the Linked List component may make sense. If you need fast random access to the data then the Array component may be a better choice.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
This forum is locked: you cannot post, reply to, or edit topics.   This topic is locked: you cannot edit posts or make replies.    codemorphis.com Forum Index -> Visual Programming Forum All times are GMT - 5 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group