DEVTOME.COM HOSTING COSTS HAVE BEGUN TO EXCEED 115$ MONTHLY. THE ADMINISTRATION IS NO LONGER ABLE TO HANDLE THE COST WITHOUT ASSISTANCE DUE TO THE RISING COST. THIS HAS BEEN OCCURRING FOR ALMOST A YEAR, BUT WE HAVE BEEN HANDLING IT FROM OUR OWN POCKETS. HOWEVER, WITH LITERALLY NO DONATIONS FOR THE PAST 2+ YEARS IT HAS DEPLETED THE BUDGET IN SHORT ORDER WITH THE INCREASE IN ACTIVITY ON THE SITE IN THE PAST 6 MONTHS. OUR CPU USAGE HAS BECOME TOO HIGH TO REMAIN ON A REASONABLE COSTING PLAN THAT WE COULD MAINTAIN. IF YOU WOULD LIKE TO SUPPORT THE DEVTOME PROJECT AND KEEP THE SITE UP/ALIVE PLEASE DONATE (EVEN IF ITS A SATOSHI) TO OUR DEVCOIN 1M4PCuMXvpWX6LHPkBEf3LJ2z1boZv4EQa OR OUR BTC WALLET 16eqEcqfw4zHUh2znvMcmRzGVwCn7CJLxR TO ALLOW US TO AFFORD THE HOSTING.

THE DEVCOIN AND DEVTOME PROJECTS ARE BOTH VERY IMPORTANT TO THE COMMUNITY. PLEASE CONTRIBUTE TO ITS FURTHER SUCCESS FOR ANOTHER 5 OR MORE YEARS!

Linked Lists

Linked lists are a commonly employed data storage mechanism in computing. They are a useful tool if you have a number of data items to store, but the number of such items is variable and is not known in advance.

In these circumstances, unless you are happy with a very wasteful program that allocates an array way in excess of anything that will ever be needed, it is best to allocate the memory in chunks as and when you need it, and store each record in a linked list. If you do allocate a large array then there is every likelihood that one day, possibly many years in the future, you will exceed the data size you originally thought was more than you would ever need. When this happens you will at best get an error and the program will not operate, or at worst you will write beyond your allocated memory space and the program will fall over with a segmentation violation (it will depend on your diligence on checking your array index is within bounds as to which of these happens).

In a linked list you have individual blocks of memory which are separately allocated. You will have a pointer to the start of the data, and each record will have a pointer to the next block of memory. In this way an arbitrary number of records can be created.

list1.jpg

Sometimes people create lists in which a pointer to both the next, and the previous record is maintained. Usually lists are setup in this way to assist with some specific requirement in the way that the data needs to be referenced (e,g, suppose the records in your list are in time order, and you need to look at a record 10 previous to the one you are currently looking at. To do this you will need to follow the reverse pointers back 10 records.

list2.jpg

Adding a new record to the list

Unless you have a specific requirement for the data items to be sorted into a particular order, the easiest way to build up a linked list is by inserting each new item onto the start of the list. Initially your List pointer will be a NULL pointer, and as you add items your list will build up as follows.

List -> null
List -> data 1 -> null
List -> data 2 -> data 1 -> null
List -> data 3 -> data 2 -> data 1 -> null

Here is some sample code showing how to create and add entries to a linked list. In this example each record contains a name and a phone number.

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <string.h>

typedef struct nameNumber
{
    char *name ;
    char *number ;
    struct nameNumber *next ;
} NameNumber ;

static NameNumber *list = NULL ;

void addEntryToList(char *name, char *number)
{
    NameNumber *new = (NameNumber *) calloc (1, sizeof (NameNumber)) ;

    new->name = strdup (name) ;
    new->number = strdup (number) ;

    // slot into beginning of list
    new->next = list ;
    list = new ;
}

main (int argc, char **argv)
{
    addEntryToList ("Joe Bloggs", "+44123456789") ;
    addEntryToList ("John Doe", "+1123456789") ;
}

How to find a record in a linked list

Here is some sample code for traversing a linked list to find a particular record. In this example we are looking for a record where we are searching by the name field.

NameNumber *findByName (char *name)
{
    NameNumber *ptr = NULL ;

    for (ptr = list; ptr; ptr = ptr->next)
    {
        if (!strcmp (ptr->name, name))
            return (ptr) ;
    }
    return (NULL) ;
}

If we were searching by phone number the code would be quite similar, as follows

NameNumber *findByNumber (char *number)
{
    NameNumber *ptr = NULL ;

    for (ptr = list; ptr; ptr = ptr->next)
    {
        if (!strcmp (ptr->number, number))
            return (ptr) ;
    }
    return (NULL) ;
}

Deleting Records from a list

Suppose we want to remove a record from the list. The mechanism for doing this is quite simple. You need to traverse the list until you find the record that points to the record you want to delete. You then change the pointer so that it points at the record that is currently pointed at by the record you are going to delete. Then you may remove the item you no longer require.

The following code snippet shows how it is done.

void deleteVictim (NameNumber *victim)
{
    if (victim)
    {
        free (victim->name) ;
        free (victim->number) ;
        free (victim) ;
    }
}

int deleteFromList (NameNumber *victim)
{
    NameNumber *ptr = NULL ;

    if (!victim)
        return -1;

    // victim may be the first entry in the list
    if (list == victim)
    {
        list = victim->next ;
        deleteVictim (victim) ;

        // success return
        return 0 ;
    }

    for (ptr = list; ptr; ptr = ptr->next)
    {
        if (ptr->next == victim)
        {
            ptr->next = victim->next ;
            deleteVictim (victim) ;

            // success return
            return 0 ;
        }
    }
    return -1 ;
}

Hashed linked lists

What happens if the number of data items in your linked list gets very large? The main impact is that it becomes progressively slower to find any particular record. Depending on the number of searches you need to do, this can have negative impacts on the performance of your program.

In this scenario I would recommend “hashing” your linked list. This is just a fancy term for splitting it into a number of smaller lists which will be quicker to search. Instead of having a single pointer to the start of the list, we could have an array of pointer, each of which points to the start of a much smaller linked list.

listhash.jpg

Continuing with our example of a linked list of records containing name and phone number, let’s imagine that we setup an array of 100 pointers as the start of the linked list. The question then arises how we allocate individual data items to a particular list. It has to be done in a predictable way so that we know where to look when we are searching for the data.

This is where the “hashing” comes in. Hashing is just the application of some function on your data to arrive at a numeric value in a known range. So what does that mean in practice? Well, for example if we are hashing according to the name field of our data items, one approach we could take is to add together the ASCII 1) values of each letter in the name.

Suppose we are hashing the name “Joe Bloggs”. Joe Bloggs is the English equivalent of the name “John Doe” in America. Let’s apply this hashing algorithm.

The ASCII values for Joe Bloggs are

74,111,101 66,108,111,111,155 = Total 837

I have ignored the space, but you could equally well include the ascii value for space (32) in the hash.

So we have the value 837 but we have already decided that we are going to have only 100 starting points in our array, so we need to reduce the hash value into that range. We do this by simply dividing by size of the hash (100) and taking the remainder. So in this case our hash value is 37 and we will be adding (and searching) for this data item starting at the list[37] starting point.

If we apply the same technique to the name John Doe we get

74,111,104,110 68,111,101 = Total 679 so Hash value 79.

Obviously the Hash value is not unique for each record, but it is predictable and so provides this way of quickly narrowing your search.

Now if you are thinking that this process of adding up the ascii values of all the characters in the name is a bit of a faff, well luckily there is a built in function strcmp 2) which does most of what you need. Using strcmp your hashing algorithm can be as follows

#define HASH_SIZE 100

int getHashValue (char *name)
{
    // avoid core dumps
    if (!name)
        return (0) ;

    int Hash = strcmp (name, "My Hashing String") ;
    if (Hash < 0)
        Hash *= -1 ;

    Hash = Hash % HASH_SIZE ;
    return (Hash) ;
}

Then, we adapt our add and find functions as follows

static NameNumber *list[HASH_SIZE] ;

void addEntryToList(char *name, char *number)
{
    NameNumber *new = (NameNumber *) calloc (1, sizeof (NameNumber)) ;

    new->name = strdup (name) ;
    new->number = strdup (number) ;

    int hash = getHashValue (new->name) ;

    // slot into beginning of list
    new->next = list[hash] ;
    list[hash] = new ;
}

NameNumber *findByName (char *name)
{
    NameNumber *ptr = NULL ;

    int hash = getHashValue (name) ;

    for (ptr = list[hash]; ptr; ptr = ptr->next)
    {
        if (!strcmp (ptr->name, name))
            return (ptr) ;
    }
    return (NULL) ;
}

Nothing at all complicated about this. However, if you are wanting to search your linked list by more than 1 feature (in this case if you need to search by either name or number) then things could start getting complicated. If you want to keep a single data block for each record you will need 2 Hash arrays for starting points and you will need 2 pointers in the structure to give the next item depending on whether you are traversing the name list or the number list. You will also need to pay attention to the functions that add and remove entries from the list.

For simplicity and clarity I would recommend maintaining 2 entirely separate (hashed) link lists, each setup as described above. So for each piece of data (name and number) you would allocate 2 blocks of memory, filled in with the same data, and place one in your numberHash list and one in your nameHash list. If there is some common data which needs to be manipulated irrespective of the search method that has been used to find the data, then this can be allocated (once) and the pointer to this data area placed in both data blocks (one in each list).


Computing | Programming


QR Code
QR Code linked_lists (generated for current page)
 

Advertise with Anonymous Ads