# Archive for category Data Structures

### How to sort a singly linked list?

Posted by encrypt3d in Data Structures, Linked List on November 6, 2010

Sorting a singly linked is simple. Find the method below for the same.

/* a function to sort a list */ struct node *sortlist(struct node *p) { struct node *temp1,*temp2,*min,*prev,*q; q = NULL; while(p != NULL) { prev = NULL; min = temp1 = p; temp2 = p -> link; while ( temp2 != NULL ) { if(min -> data > temp2 -> data) { min = temp2; prev = temp1; } temp1 = temp2; temp2 = temp2-> link; } if(prev == NULL) p = min -> link; else prev -> link = min -> link; min -> link = NULL; if( q == NULL) q = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q as a first node*/ else { temp1 = q; /* traverses the list pointed to by q to get pointer to its last node */ while( temp1 -> link != NULL) temp1 = temp1 -> link; temp1 -> link = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q at the end of list pointed by q*/ } }

### How to insert a node in a sorted linked list?

Posted by encrypt3d in Data Structures, Linked List on November 6, 2010

To insert a new node into an already sorted list, we compare the data value of the node to be inserted with the data values of the nodes in the list starting from the first node. This is continued until we get a pointer to the node that appears immediately before the node in the list whose data value is greater than the data value of the node to be inserted.

/* a function to sort a list */ struct node *sortlist(struct node *p) { struct node *temp1,*temp2,*min,*prev,*q; q = NULL; while(p != NULL) { prev = NULL; min = temp1 = p; temp2 = p -> link; while ( temp2 != NULL ) { if(min -> data > temp2 -> data) { min = temp2; prev = temp1; } temp1 = temp2; temp2 = temp2-> link; } if(prev == NULL) p = min -> link; else prev -> link = min -> link; min -> link = NULL; if( q == NULL) q = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q as a first node*/ else { temp1 = q; /* traverses the list pointed to by q to get pointer to its last node */ while( temp1 -> link != NULL) temp1 = temp1 -> link; temp1 -> link = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q at the end of list pointed by q*/ } } return (q); }

### How to insert a node after a specified node in a linked list?

Posted by encrypt3d in Data Structures, Linked List on October 30, 2010

To insert a new node after the specified node in a singly linked list, first we get the number of the node in an existing singly linked list after which the new node is to be inserted. This is based on the assumption that the nodes of the list are numbered serially from 1 to n. The list is then traversed to get a pointer to the node, whose number is given. If this pointer is x, then the link field of the new node is made to point to the node pointed to by x, and the link field of the node pointed to by x is made to point to the new node.

Figure 1 and 2 show the list before and after the insertion of the node, respectively.

/* a function which inserts a newly created node after the specified node */ struct node * newinsert ( struct node *p, int node_no, int value ) { struct node *temp, * temp1; int i; if ( node_no <= 0 || node_no > length (p)) { printf("Error! the specified node does not exist\n"); exit(0); } if ( node_no == 0) { temp = ( struct node * )malloc ( sizeof ( struct node )); if ( temp == NULL ) { printf( " Cannot allocate \n"); exit (0); } temp -> data = value; temp -> link = p; p = temp ; } else { temp = p ; i = 1; while ( i < node_no ) { i = i+1; temp = temp-> link ; } temp1 = ( struct node * )malloc ( sizeof(struct node)); if ( temp == NULL ) { printf ("Cannot allocate \n"); exit(0) } temp1 -> data = value ; temp1 -> link = temp -> link; temp -> link = temp1; } return (p); }

### How to insert a node in a linked list recursively?

Posted by encrypt3d in Data Structures, Linked List on October 30, 2010

A linked list is a recursive data structure. A recursive data structure is a data structure that has the same form regardless of the size of the data. If you haven’t already gone through the concepts of a linked list, I recommend you to go through my previous article on linked list first.

The recursive method for inserting a node in a singly linked list is simple and given below:

struct node *insert(struct node *p, int n) { struct node *temp; if(p==NULL) { p=(struct node *)malloc(sizeof(struct node)); if(p==NULL) { printf("Error\n"); exit(0); } p-> data = n; p-> link = NULL; } else p->link = insert(p->link,n);/* the while loop replaced by recursive call */ return (p); }

### Deleting a node from doubly linked list

Posted by encrypt3d in Data Structures, Linked List on October 5, 2010

How do you delete a node from doubly linked list? This is basically manipulations of links and freeing the memory for deleted node. If you are not already familiar with concepts of doubly linked lists, I would recommend you go through that first.

Deleting a node from doubly linked list.

struct dnode * delete( struct dnode *p, int node_no, int *val) { struct dnode *temp ,*prev=NULL; int i; if ( node_no <= 0 || node_no > nodecount (p)) { printf("Error! the specified node does not exist\n"); exit(0); } if ( node_no == 0) { temp = p; p = temp->right; p->left = NULL; *val = temp->data; return(p); } else { temp = p ; i = 1; while ( i < node_no ) { i = i+1; prev = temp; temp = temp-> right ; } prev->right = temp->right; if(temp->right != NULL) temp->right->left = prev; *val = temp->data; free(temp); } return (p); }