C Linked Lists

The concept of linked lists is one of the powerful features in C. It will also bring to you some of the powerful features of pointers. Now let us go back to the arrays we have previously said that if an array of 100 elements are is to be declared, the compiler catches hold of 100 consecutive memory locations and marks them as the elements of the array. Whenever an element is to be visited, it’s address is calculated based on the offset from the base element (see the previous post).

Herein lies a problem. Suppose, we need an array of 10,000 elements. Sometimes, it may not be possible to get 10000 successive locations in the memory. Then, even though 10,000 locations are there ( spread all over the memory) just because they are not in consecutive locations(in one place). We will have to say it is not possible to allocate the array.

We have not addressed one or two other issues with the arrays. Let us say, suppose,we want to rename the 20th element & shift the other elements back.

Then what we have to do is to shift the 21st element to the 20th location. 22nd element to 21st location etc.. etc.. suppose the array is 1000 elements long. It is still possible but takes an enormous amount of effort.

Similar is the case, if we want to insert an element we have to push the 1000th element to ( 1001th place ( if there is space) and push 999th to 1000th place etc.. And if the array is just declared as only a 1000 element one, then we cannot do the operation all. We have to create a new array, ( a longer one) and copy these elements to the new one.

i.e if, beforehand, we are not sure of the actual size of the array elements, it is difficult to manage the array. All these difficulties lead us to the concept of “dynamic” allocation. (Arrays are supposed to be static: you declare them at one time, that is it). Look at the following figure. A is an array with 5 elements.

Now I cannot add a new element to this, because of the reasons described above, I can delete an element, but it needs some effort on my part. Now consider the same data represented as follows:

The second is what is called a “ linked list” a list of linked elements. Each “ node” has 2 elements one is a data element and the other a pointer to the next node. Your knowledge of structures should immediately indicate to you that this can be declared as a structure. Once done, go back to the difficulties of using arrays, which we had listed above. Because we are using pointers, the nodes need not be consecutive. We need not even know beforehand how many nodes we need. As and when we want to add new elements, we can keep creating new nodes and keep connecting them using pointers.

i.e create a new node, make the pointer of node 3 points to the new node and make the pointer of the new node and make the pointer of the new node point to node4. Similarly, if we want to delete node2, all that we have to do is to make the pointer of node1 point to node3.

The following examples illustrate how to create & traverse such linked lists.

linked lists

main()
{
    struct entry
   {
       int value;
       struct entry *next;
   };
    struct entry n1,n2,n3;
    int i;
    n1.value = 100;
    n2.value = 200;
    n3.value = 300;
    n1.next = &n2;
    n2.next = &n3;
    i = n1.next->value;
    printf (“%d “,i);
    printf(%d\n”, n2.next->value);
}

OUTPUT:

200 300

List traversal

main()
  {
     struct entry
    {
        int value;
        struct entry *next;
    };
    struct entry n1,n2,n3;
    struct entry *list_pointer = &n1;
    n1.value = 100;
    n1.next = &n2;
    n2.value = 200;
    n2.next = &n3;
    n3.value = 300;
    n3.next = (struct entry *) 0;
    while (list_pointer != (struct entry *) 0)
    {
        printf (“%d\n”, list_pointer->value);
        list_pointer = list_pointer->next;
    }
}

OUTPUT:

100
200
300

In fact, these is a lot of literature available on linked lists, but we stop at this stage and move on to the other use of pointers.