DS - LINKED LISTS 1

What is Linked list??

Linked list is data structure used for storing collections of data. It has following features.
* Each item in the list points to next item.
* Last item of the list points to NULL.
* It can grow or shrink during execution of a program.
* There is no wastage of memory space.
* Can be made just as long as required.

To access array element, address of that element is computed by one multiplication and one addition.
The index of the required element will be known. This index is multiplied with the size of array element. The result will be added to base address of the array.
Since these two operations take constant time, we can say the array access can be performed in constant time.

Singly Linked list::

declaration:



struct trynode{
int data;
struct trynode *ptr_to_node;
};
typedef struct trynode* NODE;


data will hold the actual data of the each node and
ptr_to_node points to next item in the linked list.

Various operations that can be performed on the singly linked list:
1. Insert the node at the front end
2. Insert the node at rear end
3. Insert the node at specified position.
4. Delete the node from the front end
5. Delete the node from rear end
6. Delete the node from specified position.
7. Display the content of linked list.


1. Insert the node at the front end.

NODE front_insert(NODE first, int d){
NODE temp;
temp=(NODE)malloc(sizeof(struct trynode));
temp->data=d;
temp->ptr_to_node=first;
return temp;
}

2. Insert the node at rear end

NODE rear_insert(NODE first, int d){
NODE cur,temp;
temp=(NODE)malloc(sizeof(struct trynode));
temp->data=d;
temp->ptr_to_node=NULL;
if(first==NULL)
return temp;
cur=first;
while(cur->ptr_to_node!=NULL)
{
cur=cur->ptr_to_node;
}
cur->ptr_to_node=temp;
return first;
}



3. Insert the node at specified position.

NODE pos_insert(NODE first, int d,int pos){
NODE temp,cur,prev;
temp=(NODE)malloc(sizeof(struct trynode));
temp->data=d;
temp->ptr_to_node=NULL;
cur=first;
for(i=0;i<pos;i++)
{
 prev=cur;
cur=prev->ptr_to_node;
}
prev->ptr_to_node=temp;
temp->ptr_to_node=cur;
return first;
}

4. Delete the node from the front end
5. Delete the node from rear end
6. Delete the node from specified position.

NODE delete(NODE first,int pos){
NODE prev,temp,cur;
cur=first;
for(i=1;i<pos;i++){
prev=cur;
cur=cur->ptr_to_node;
}

temp=cur->ptr_to_node;
printf("\n ::: deleted is %d :: \n",cur->data);
prev->ptr_to_node=temp;
free(cur);
return first;
}


7. Display the content of linked list.

void display(NODE first){
NODE temp;
  if(first==NULL)
    printf("\nList is empty");
else{
    temp=first;
    printf("\n content is :: \n");
 while(temp!=NULL)
      {
       printf("%d\n",temp->data);
       temp=temp->ptr_to_node;
      }
}
}


for complete program see DS - LINKED LISTS 2
http://dharmanath1244.blogspot.in/2015/07/ds-linked-lists-2.html