From the wikipedia:

“A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including stacks, queues, associative arrays, and symbolic expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation.”


For beginners, linked lists are often a very high wall to climb, In this article I’m going to code the most important functions to handle linked lists and then I’ll write a simple program which uses these functions.

Essentially to handle a linked list we have to write at least 3 functions:

  • A function which adds an item to the list
  • A function which removes an item from the list.
  • A function which scans the list.

First of all we must define the structure

typedef struct linked_list_s
{
    int                  data;
    struct linked_list_s *link;
}linked_list_t;

Then we have to insert our functions, let’s start with the addItem function, this function will add an item after the last item of the linked list.

void addItem(linked_list_t **aLinkedList, int aData);


void addItem(linked_list_t **aLinkedList, int aData)
{
    linked_list_t *temp;
    temp = *aLinkedList;
    if(*aLinkedList==NULL)
    {
        *aLinkedList=malloc(sizeof(linked_list_t));
        temp = *aLinkedList;
    }
    else
    {
        while((temp->link)!=NULL)
        {
            temp=temp->link;
        }
        temp->link = malloc(sizeof(linked_list_t));
        temp=temp->link;
    }
    temp->data = aData;
    temp->link  = NULL;
}


the removeItem function will check for an item into the list, if the item is present the function will remove it from the linked list

void removeItem(linked_list_t *aList, int aData);
void removeItem(linked_list_t *aList, int aData);
{
  linked_list_t *currentPointer, *previousPointer;

  previousPointer = NULL;

  /*
   * Visit all nodes, maintaining a pointer to previous visited node .
   */
  for (currentPointer = *aList;	currentPointer != NULL;	
       previousPointer = currentPointer, currentPointer = currentPointer->link) {

    if (currentPointer->element == aData) {  // Found it.
      if (previousPointer == NULL) {
        /* Fix beginning pointer. */
        *aList = currentPointer->link;
      } else {
        previousPointer->next = currentPointer->next;
      }

      /* Deallocate memory for the node. */
      free(currentPointer);
      return;
    }
  }
}

the printListItems function will print the content of the linked list starting from the fisrt item.

void printListItems(linked_list_t *aLinkedList);

void printListItems(linked_list_t *pt)
{
    while(pt!=NULL)
    {
        printf(" Data : %d\n",pt->data);
        printf(" Link : %d\n",pt->link);
        pt=pt->link;
    }
}

Now let’s write a simple main program to test the functions we have implemented.

 

int main(void)
{
    int           i;
    linked_list_t *myList;

    for(i=0; i<10; i++)
    {
        addItem(&myList, i);
    }
    printListItems(myList);

    for(i=2; i<5; i++)
    {
        removeItem(myList, i);
    }
    printListItems(myList);
}

Put all the code into a file named linked_list.c, open a terminal window and try to compile it with the following command:

    # gcc -o linked_list linked_list.c

Run the program issueing the following command:


    # ./linked_list


As said at the beginning of this article linked lists can be used to implement abstract data types, in the next articles we are going to implement a stack (a structure managed with a  Last In First Out policy) and a queue (a structure managed with a  First In First Out policy).

Gg1