![]() ![]() Main Guide What's new Products Downloads FAQ Mailing List Links |
| |||||||||||||||||||||||
How to Implement Linked Lists in WimpWorks 2Written by Charles Talibard <charles@jaffasoft.co.uk> IntroductionA linked list is a structure similar to an array but with many more desirable properties. An array can be considered as one object with a fixed number of sections - once declared, the only way of changing its size is to create a new array and copy the data in (which is wasteful and not possible in some languages). One elegant solution to this problem is to treat each element of an array as a separate object. By creating each element only as required, and linking elements together using pointers, you can have a structure similar to an array that can grow and shrink dynamically at run-time. Data structures like this are called linked lists.
Linked lists come in two main varieties - Single and Double. Both can be be tricky to implement as they involve manipulating pointers. Basically, for each element you allocate enough memory to store the data plus additional memory to store either one or two pointers (depending on whether you are linking singly or doubly). Each item in the list contains a pointer to the next item (and, if linking doubly, a pointer to the previous item). Access to the list is facilitated by keeping a pointer to the first item in the list or 'head item'. Because the items are linked by pointers, they do not have to be adjacent in memory and can be created whenever required. Because of the properties described above, linked lists lend themselves very well to a number of computing problems. Any application which has to keep details on an unknown number of objects will need to use a linked list. However, even if the number of objects is set at a maximum value, linked lists still offer other good advantages. If objects are created by the user of an application in a random order, but need to be presented in a fixed order (an address book for example), linked lists are ideal, as an object can be inserted in the list between any other two objects. This means that (using the address book example) 'people' objects could be inserted into the address book list in any order, but stored and displayed alphabetically by surname. If you are storing complex data structures (comprising of many variables) in a list, then swapping two items is only a case of changing a few pointers. In an array, you would have to copy whole blocks of memory to achieve this. As most sorting algorithms require swapping of objects this means sorting a linked list can be a lot simpler than sorting an array. Singly Linked Lists vs Doubly Linked ListsOne disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If you want to read/write a particular item then you have to start at one end of the list and follow the pointers until you get to that item. Although singly linked lists have a lower memory requirement, because each item only contains a pointer to the next item you cannot traverse singly linked lists from the tail towards the head. If you will need to move in both directions along the list then double is the only option. However, as can be seen from the examples below, adding an item to a doubly linked list is more complex (as it involves more pointer manipulation) while removing an item from a singly linked list is more complicated (because of the lack of pointers in each item). Pointers and Data Types in BASIC
As BBC BASIC is by nature basic, very little support for composite data types
is present. In C we have, (the
Having defined this, we can create new objects of this type, just as we could create a new integer or string, and access the individual members of the structure.
But in BBC BASIC, as no support for data structures is provided, we have to
use pointers to a block of memory to access the different members in our
structure. In the above example we need to calculate the exact size of an
Now that we have enough memory, we can start using
These would probably exists in a procedure that responded to 'Starting Up'
so that they would be defined from the start of the program. In order to
access the data using a pointer (
By defining variables to hold all the offsets you instantly make your code
more robust and more readable. If you have to change the format of your
structure then all you have to do is alter the value of the variables and all
the code that accesses that part of the structure will use the new offset.
Imagine if you decided that the pointer to the previous item should come
first. You would have to change every instance of For a more detailed explanation of how to design and implement advanced data structures see the Application Note "Designing and Implementing Data Structures using WimpWorks 2" (Not yet available) Linked List Operations
Throughout all the examples given in the following sections
As recommended above we will define the following offsets for singly linked lists and the constant NULL:
While for examples that use doubly linked lists we will define :
In this article I will discuss, in detail, the operations:
Though many more are possible, due to space constraints we cannot include them here. Searching a Linked List for the desired ItemAs mentioned earlier, because a linked list doesn't reside in one contiguous block of memory, we have to locate the desired element each time we want to read or alter its contents. We could just store pointers to all the objects we create but we don't know how many objects will be created. To store all the pointers would require a further linked list! So we can't get away from the fact that linked lists will never permit direct access to the objects they contain. In order to identify which node or element of the list we want, we require some way of uniquely identifying each node. Two methods for this are outlined below :
Example 1 : Locating an element based on its position
Example 2 : Locating an element based on its contents The two examples above traverse the linked list to locate a given element. The first will locate the nth element in a list. The second will return the pointer to the element containing a given string. Adding Items to a ListBecause of the nature of a linked list items can be added at any point in the chain without overwriting any existing items. The easiest place to add a new item is at the head or tail of a list. This is because we can keep a pointer to the head/tail element. To add an item to a linked list you must first claim a block of memory to store the item in. After the memory is claimed you can treat it like a data structure and start filling in the data that the structure stores. This will include any pointers to other objects in the list. These pointers, along with the equivalent pointers for other objects in the list, should be used to link the object in to the list. Once this is done the actual data to be stored at that position can be inserted.
Allocation of memory should be done using the WimpWorks 2 command
Adding an item to the head of a list
Since this item is going to be the head of the list, its 'next item'
pointer should point to the current head of the list, and only when that is
the case can the
The following examples show how to add a node to the head of a list.
Example 3 : Adding a node to the head of a singly linked list
Example 4 : Adding a node to the head of a doubly linked list Adding an item to the tail of a listAs this item is going to be the tail of the list, its 'next item' pointer should be NULL as there is no next item. However, the current tail will no longer be tail once we have finished, so its 'next item' pointer should point to the new item we have created. Examples:
Example 5 : Adding a node to the tail of a singly linked list
Example 6 : Adding a node to the tail of a doubly linked list Adding an item in the middle of the listTo add an item in the middle of the list we need a pointer to the item after which we want to insert the new item. If the item after which we wish to insert is not the tail, or NULL, then we must devise a method to insert in the middle of the list. For the purposes of the steps outlined below let us assume 'before ' is a
pointer to the element that will be before the new one in the list and
that 'new ' will be a pointer to the new item (after we
allocate the memory). One possible method, for a singly linked list, is
detailed below (it might be useful to sketch the pointer alterations on a
bit of scrap paper using a style similar to figures 2 and 3) :
Example 7 : Adding a node in the middle of a singly linked list. For a doubly linked list this method will have the same effect:
Example 8 : Adding a node in the middle of a doubly linked list. Removing an item from a linked list
When removing a node from a linked list you need first to un-link it from
the list so that all the pointers that keep in place it in the list skip
over it. Secondly you must free up all the memory for that node using
Removing the head node of a linked listSingly linked lists
In a singly linked list removing the head item is extremely simple. You
must ensure that the pointer you have to the head of the list is altered to
point at the item after the head. But if you move the pointer straight away
you won't be able to call
Example 9 : Removing a node from the head of a singly linked list Doubly Linked ListsTo remove the head element from a doubly linked list is only slightly more complex than for singly linked lists. The method is exactly the same, but with the added step of ensuring the the new head of the list doesn't point back to the now non-existent previous head :
Example 10 : Removing a node from the head of a doubly linked list Removing the tail element from a linked listDoubly linked listsThis is the simplest style of list to remove the tail element from. The 'previous element' pointer of the tail element gives us the new tail element. All we have to do is set its 'next element' pointer to NULL (reflecting the fact that nothing is after it).
Example 11 : Removing a node from the tail of a doubly linked list Singly linked listsBecause it is not possible to traverse a singly linked list backwards, we must locate the new tail element by traversing it from the front until we find a node which points to the current tail element. After this is done we proceed in a similar manner as for a doubly linked list.
Example 12 : Removing a node from the tail of a singly linked list Removing an element from the middle of a listDoubly linked listsWhen there are elements on either side of the one you want to delete you need a pointer to the element before the one being deleted and for a doubly linked list you also need a pointer to the element after. With a doubly linked list this is simple as the node you want to delete will have both these pointers stored in it. All we have to do is ensure that the items on either side have their pointers altered so that the item to be deleted is excluded from the list:
Example 13 : Removing an element from the middle of a doubly linked list Singly linked listsWith the singly linked list we have the same complications we did previously for deleting the tail. Without searching through the list, we have no way of getting the item before the one we are deleting. We will have to search for it. Once it is found we can perform similar operations to those required for a doubly linked list.
Example 14 : Removing an element from the middle of a singly linked list Beware of NULL pointersIf a pointer is passed to a program in a language, it must assume that the pointer is valid as there is no real method of checking. Even advanced, modern languages like Java will throw exceptions when a bad pointer (Java calls them references) is used. A classic example of an invalid pointer is NULL. NULL evaluates to either -1 or 0 in most languages. The memory location 0 or -1 is either at the very start of the address space (usually populated by the program itself) or at the very end which is usually never used as it corresponds to +16Mb from the start of the program. If you try to access these points in memory you will cause your program to crash.
When writing software that uses lots of pointers, it is essential to
consider all the possible states that the system will be in when your
operations are called. If you are changing the value of a pointer you must
make sure that you have another copy of that pointer or that the memory it
points to has been released. Once the last pointer to a block of memory is lost the memory itself is void as we now have no way of knowing where it
is. In the examples above it is assumed that a list already exists (this
is to simplify matters). What would happen if the user tried to add a node
to a non-existent list? One can assume that the values of
Another point worth mentioning is that if we try to delete the last node in the list we will also encounter problems. At this point it will be both the head and the tail of list. Which method do we use? Well, we cannot use either. This is because we won't have another element in the list to make the new tail or head item. Generic add and delete operationsBecause of the problems outlined above I have defined generic operations that catch the problem cases and deal with them. I have assumed that, as well as defining variables for the offsets of the members in the structures, the pointershead_item% and tail_item% have been
initialised to NULL at start-up.
AddWe need to catch the case when there is no list yet and initialise it. This involves creating the first node and making the head_item% and tail_item% pointer point to it. As this node doesn't point to anything else yet the 'nest item' and 'previous item' pointer are NULL.
Delete
ConclusionI hope that I have given an insight into how useful the linked list can be. With a pen and paper and a little thought, linked lists are not at all difficult to program. Many algorithms require the swapping of items and the re-ordering of data. With a linked list this can be done simply by changing a few pointers. One of the very interesting points only briefly discussed here is concept of the compound (or composite) data type. These are detailed in another application note called "Designing and Implementing Data Structures using WimpWorks 2" (Not yet available) , which links in with this one very well. Anybody considering implementing a linked list should read it. © Jaffa Software 1998. |