Most beginners find the first step in the world of data structures very difficult. It reminds me of my hindi teacher who use to tell us that a kindergarten learns just alphabets for almost one year; such is difficult life. Anyways the paper i m going to write is for novices and those experienced could literally avoid it.
Before i deal with structures and self referential structures, some points about pointers.
1)A pointer is placard that holds the memory address.A declaration of pointer goes on like this
int *p; //or for that matter
File *fp;
Now the basic point to be noted is that here we declare p and fp to hold the addresses of int and FILE type.
2)When we declare a string or a structure , we can easily refer it by pointers.for eg:
char a[3]={'x','y','z'};
char *p;
p=a;
Here we have declared a string 'a' and given it to a character pointer p.
Note: Name of the array, string or structure can fetch us their first element. Thus a and a+0 and a[0] are all same refering to the first element. And if we are talking about references we can take that value in a Pointer variable, which we did through 'p'.
Enough of Pointer handling. Some thing about self referential Structures.
struct node{
char info;
struct node *next;
};
Again here we have a structure which has its element a self referential structure i.e *next.
So why do we need a self referential structure? Obviously to refer to the same kind.
Now we come to the Linked List Portion:
We will be having seven functions including main function and some globl declarations in our linked list program(with thorough explanations). Finally there will be a complete code for linked list. Some of the core modules included are :
1)Creating linked list
2)Displaying linked list
3)Inserting into linked list
4)Deleting a node from linked list
5)Sorting linked list
6)Reversing linked list
But before i delve into creating the linked list our program is having a global structure variable and creating an empty linked list 'start' from it.
struct link {
int info;
struct link *next;
};
struct link *start=NULL;
Note: if we want to declare 'start' a simple structure i.e struct link start; then we can initalize the empty linked list by start.next=NULL;
This NUlL is a macro defined in the stdio(standard input output) header file. When the start pointer is assigned NULL value the linked list created is with nothing in its entry.
1)Creating Linked List Function i.e void create_link_list(struct link *);
void create_link_list(struct link *node) {
int info;
int node_number=1;
char choice;
printf("\n\nInside create_link_list function");
printf("\nEnter n to break from the loop");
choice=getch();
node=start;
while(choice!='n') {
node->next=(struct link *)malloc(sizeof(struct link));
node=node->next;
node->next=NULL;
printf("\nEnter the value of the node%d:",node_number);
scanf("%d",&info);
node->info=info;
printf("\nEnter n to break from the loop");
choice=getch();
node_number++;
}
printf("\n\n");
}
The first thing to keep in mind is that we have to assign the start to node. This ensure the start of the node.
node=start; //This signifies the starting of the linked list.
Now breaking the line: node->next=(struct link *)malloc(sizeof(struct link));
We want to dynamically allocate memory to this self referential structure using malloc function which gives us a void pointer of addresses from the heap of memory. This need to be type casted in a suitable form.Thus we declare(struct link *).
node=node->next;
Again carefully look for the arrows and their point of origination in the above diagram.This declaration signifies that the current node is now the next node and we have a chain of nodes created.
2)Displaying the linked list: void display_link_list(struct link *);
void display_link_list(struct link *node) {
printf("\n\nInside display_link_list function");
node=start->next;
while(node) {
printf("%d\t",node->info);
node=node->next;
}
printf("\n\n");
}
node=start->next; this only signifies that the node is assigned the address of next field of start variable. Obviously the start->next is pointing to the first node of the list.Thus this declaration signifies that the node is assigned the first node .
node=node->next; Through this statement we can walk across whole of the linked list assigning the node next node.
3)Inserting into the Linked list: void insert_link_list(struct link *);
void insert_link_list(struct link *node) {
int insert_node;
int node_number=1;
struct link *new1;
printf("\n\nInside insert_link_list function");
printf("\nEnter the node number where the node is to be inserted:");
scanf("%d",&insert_node);
node=start;
while(node->next) {
if(node_number==insert_node) {
new1->next=(struct link *)malloc(sizeof(struct link));
new1->next=node->next;
node->next=new1;
printf("\nInserting the value at node%d",node_number);
printf("\nEnter the value of the new node:");
scanf("%d",&new1->info);
break;
}
else {
node=node->next;
}
node_number++;
}
printf("\n\n");
}
Note: For inserting a node into the linked list we have to break and form two links. One from the previous node to the new node and one from the new node to the next node of the linked list. I think that the diagram is self exaplanatory for the above code.
Ok friends it seems that this linked list has grown into a heavy meal already. I think i would be posting the other three module in the next one. And ya i will be welcoming any suggestions .In my College days This was the most feared topic so i tried to kill the dragon . At last i may err at times so please pardon me.
