Reuben's Webpage

Adding elements in the middle of a list

Well, if you managed till here I must really applaud your patience. This section might be a bit tough, but I will try and keep it as simple as I can.

As usual we start off by looking at some code. This time the program actually does some useful work it is an insertion sort program. The algorithm for insertion sort is really very simple. Our program receives numbers one after another. We compare this number with the numbers we have in a list and insert it in an appropriate position. Though I must say this is not a very good sorting algorithm, performance wise. The code can be downloaded here.

1     #include<stdio.h>
2     //this macro calculates the size of the array for us
3     //for eg if you pass it 10 element array. In Linux
4     //sizeof(array) will be 40 bytes since 1 int in Linux is 4 bytes
5     //Therefore size of array will be 40/4 =10 elements
6     #define NELEM(array) (sizeof(array)/sizeof(int))
7     struct node{
8          int n;
9          struct node *next;
10     };
11     typedef struct node node;
12
13     node *Insert(node *first,int number){
14          node *new_node=(node *)malloc(sizeof(node));
15          node *temp=first;
16          node *temp1=first;
17
18          new_node->n=number;
19          new_node->next=NULL;
20
21          if(first==NULL){
22              first=new_node;
23              return first;
24          }
25
26          for(;temp!=NULL;temp=temp->next){
27              if(temp->n>number){
28                  for(;temp1->next!=temp;temp1=temp1->next);
29                  break;
30              }
31          }
32
33          if(temp==first){
34              new_node->next=first;
35              first=new_node;
36              return first;
37          }
38
39          if(temp==NULL){
40              for(;temp1->next!=temp;temp1=temp1->next);
41              temp1->next=new_node;
42              return first;
43          }
44
45          //insert element in the middle
46          new_node->next=temp;
47          temp1->next=new_node;
48          return first;
49     }
50
51     //the insertion sort function takes the first node pointer and
52     //also the list of numbers to be sorted
53     node *InsertionSort(node *first,int list[],int n){
54          int i=0;
55
56          for(i=0;i<n;i++){
57              first=Insert(first,list[i]);
58          }
59          return first;
60     }
61
62     void printList(node *first){
63          node *temp=first;
64          printf("List Contents:\n");
65          while(temp!=NULL){
66              printf("%d\n",temp->n);
67              temp=temp->next;
68          }
69     }
70
71     int main(){
72          node *first=NULL;
73      int a[]={1,453,345,356,3,65,6,4645,4};
74          first=InsertionSort(first,a,NELEM(a));
75          printList(first);
76     }

Phew! That was some bit of code. But never fear when Reuben is near. We will take that apart part by part. If you do notice this program has made use of both the concept's I've explained till now. That is inserting elements in the beginning and inserting elements at the end.

The main function

1     int main(){
2          node *first=NULL;
3      int a[]={1,453,345,356,3,65,6,4645,4};
4          first=InsertionSort(first,a,NELEM(a));
5          printList(first);
6     }

This is simple all we do here is create a pointer to hold the list, then create an array to be sorted. Line 3 calls the sort function, and ofcourse you should know what Line 4 does by now.

The InsertionSort function

The work of this function is simple it just goes through the array calling the insert function which inserts the element in the right position.

The Insert function

1      node *new_node=(node *)malloc(sizeof(node));
2      node *temp=first;
3      node *temp1=first;
4
5      new_node->n=number;
6      new_node->next=NULL;

Now we have the juicy part. This is the function where all the action happens. Let us start off by looking at the variables used. At line 0 as usual we create a new node for the list and in line 4 and 5 the assignment of the same happens. In line 1 we have the temp variable which is used to traverse the list. In line 2 we have the temp1 variable that is used to traverse the list once we have traversed the list. I'll explain that statement in a while.

1      if(first==NULL){
2          first=new_node;
3          return first;
4      }
5

The section of code above checks to see weather the element inserted is the first one or not. If it is the first one then the first pointer is made to point to it and the first pointer is returned.

1      for(;temp!=NULL;temp=temp->next){
2          if(temp->n>number){
3              for(;temp1->next!=temp;temp1=temp1->next);
4              break;
5          }
6      }

If we escape the above "if" construct unscathed we land in to this weird looking for loop. This is a more compact way of traversing the list. Since we already assigned temp to first in the begining of the function we don't need to do it again. The condition for the loop is that temp must not become NULL, and next part of the loop is the actual traversal.

In the above code segment's if construct we check whether the number stored in the node greater than the number entered. If that is the case the we use the temp1 variable to traverse the list and stop in the node before temp. Thats what I meant when I said temp1 is used traverse the list once we have traversed the list. Pictorially it can be shown as follows. SEP

1      if(temp==first){
2          new_node->next=first;
3          first=new_node;
4          return first;
5      }
6

This section of code gets control when the while loop breaks. If it happens that the temp points to the first node. The new node is inserted at the begining of this list.

1      if(temp==NULL){
2          for(;temp1->next!=temp;temp1=temp1->next);
3          temp1->next=new_node;
4          return first;
5      }

The code above should be obvious. If temp is pointing to NULL that means that we are at the end of the list. Therefore, we insert the new node at the end of the list.

1      new_node->next=temp;
2      temp1->next=new_node;
3      return first;

This is the intresting part. Here we insert the node in the middle of the list. We make new_node point to temp. Once this is done we make temp1's next pointer point to new_node. This is shown in the diagrams below.SEP

I think that all there is to the program once you have mastered this section and the previous section you should be able to write simple programs that make use of link lists. In the next few sections I will be concentrating on removing elements from a link list.

Link List Tutorial

Adding elements in the middle of a list

The main function

The InsertionSort function

The Insert function