Reuben's Webpage

Adding a node to the front of the list

This is probably the first operation you have to be through with. Once this is understood throughly the rest would be a pushover. Take a look at code below this is a program that is used to add elements to the begining of the list.

1     #include
2
3     //single node is going to look like this
4     struct node{
5          int element;
6          struct node *next;
7     };
8
9     typedef struct node node;
10
11     node* addToBegining(node *first,int num){
12          node *new_node=(node *)malloc(sizeof (node));
13
14          new_node->element=num;
15          new_node->next=NULL;
16
17          //if first is null make the new node the first node
18          if(first==NULL){
19              first=new_node;
20              return first;
21          }
22
23          //else add the node to the begining of the list
24          new_node->next=first;
25          first=new_node;
26
27          return first;
28     }
29
30     void printList(node *first){
31          node *temp=first;
32
33          //traverse the list till you manage to get the NULL
34          while(temp!=NULL){
35              printf("%d\n",temp->element);
36              temp=temp->next;
37          }
38     }
39
40     int main(){
41          node *first=NULL;
42          int i=0;
43          for(i=0;i<50;i++){
44              first=addToBegining(first,i);
45          }
46          printList(first);
47      }

In the program we have 2 functions apart from main. SEP node* addToBegining(node *first,int num) This function actually adds the node to the begining of the list. I won't explain the arguments and the return types since they should be obvious. SEP void printList(node *first) This function prints the contents of the list. SEP

This program can be downloaded from here

The addToBegining Function

Here I will explain how this function works. First thing in a function which adds anything to a link list we need to create a new node which will be added to the list. This is done by allocating memory using the malloc call. This call allocates a block of memory for the node. This happens in line number 11.

Now that we have the block of memory we have to initialise it to the necessary to the data this is done in lines 13 and 14.

The next segment of code is interesting. Here we check to see if the first element of the list is NULL. If that is that case then we make the first point to the newly allocated node. The image below shows the same in a pictorial form.SEP

If First is not NULL, then the pointer from the new node is made to point to the node which is pointed to by first. Once this is done. First is made to point to the new node and is returned as a result we have new element attached to the start of the list. This is shown pictorially below SEP

As a warning don't mix up Line 23 and 24. The reason is that if you first point the "first" pointer to the new node you will lose the address of the next node. Ergo, you will have nowhere to point the new node to.

the printList() Function

This is the most standard way you would be traversing any linked list. So make sure you understand this well. We make a temporary pointer point to the first element of the list. In the while loop we check to see if the temporary pointer has become NULL. If it has not we continue. In the loop we print the number in the node. The next statement is again interesting. Here we actually do the traversing. The temporary pointer is made to point to the node pointed by the "next" field of the node. As a result the temporary pointer moves to the next node. This goes on till the "temp" pointer hits NULL.

Try solving this...

Now you write a program to read in names and numbers of 5 people and attach them to the front of a linklist.

Try your best to solve the problem above. Only as the last resort use this solution. If you have a problem you can see how to debug it here

Link list tutorial

Adding a node to the front of the list

The addToBegining Function

the printList() Function

Try solving this...