# Archive for October, 2010

### 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); }

### What are Doubly Linked Lists?

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

After reading this article you should be able to answer the following questions.

- What are doubly linked lists?
- How doubly linked lists are implemented?
- What are the applications for doubly linked lists?
- How doubly linked lists are different than singly-linked lists?

**Introduction**

The following are problems with singly linked lists:

- A singly linked list allows traversal of the list in only one direction.
- Deleting a node from a list requires keeping track of the previous node, that is, the node whose link points to the node to be deleted.
- If the link in any node gets corrupted, the remaining nodes of the list become unusable.

These problems of singly linked lists can be overcome by adding one more link to each node, which points to the previous node. When such a link is added to every node of a list, the corresponding linked list is called a doubly linked list. Therefore, a doubly linked list is a linked list in which every node contains two links, called left link and right link, respectively.

The left link of the node points to the previous node, whereas the right points to the next node. Like a singly linked list, a doubly linked list can also be a chain or it may be circular with or without a header node. If it is a chain, the left link of the first node and the right link of the last node will be NULL, as shown in Figure 1.

If it is a circular list without a header node, the right link of the last node points to the first node. The left link of the first node points to the last node, as shown in Figure 2

If it is a circular list with a header node, the left link of the first node and the right link of the last node point to the header node. The right link of the header node points to the first node and the left link of the header node points to the last node of the list, as shown in Figure 3.

Therefore, the following representation is required to be used for the nodes of a doubly linked list.

struct dnode { int data; struct dnode *left,*right; };

Inserting into a doubly linked list is done as :

struct dnode *insert(struct dnode *p, struct dnode **q, int n) { struct dnode *temp; /* if the existing list is empty then insert a new node as the starting node */ if(p==NULL) { p=(struct dnode *)malloc(sizeof(struct dnode)); /* creates new node data value passed as parameter */ if(p==NULL) { printf("Error\n"); exit(0); } p->data = n; p-> left = p->right =NULL; *q =p; } else { temp = (struct dnode *)malloc(sizeof(struct dnode)); /* creates new node using data value passed as parameter and puts its address in the temp */ if(temp == NULL) { printf("Error\n"); exit(0); } temp->data = n; temp->left = (*q); temp->right = NULL; (*q)->right = temp; (*q) = temp; } return (p); }

### How to delete a specified node from a Linked List?

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

**Deleting a specified node from a linked List**

To delete a node, first we determine the node number to be deleted (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, as well as a pointer to a node that appears before the node to be deleted. Then the link field of the node that appears before the node to be deleted is made to point to the node that appears after the node to be deleted, and the node to be deleted is freed.

Implementation :

struct node *delet ( struct node *p, int node_no ) { struct node *prev, *curr ; int i; if (p == NULL ) { printf("There is no node to be deleted \n"); } else { if ( node_no > length (p)) { printf("Error\n"); } else { prev = NULL; curr = p; i = 1 ; while ( i < node_no ) { prev = curr; curr = curr-> link; i = i+1; } if ( prev == NULL ) { p = curr -> link; free ( curr ); } else { prev -> link = curr -> link ; free ( curr ); } } } return(p); } /* a function to compute the length of a linked list */ int length ( struct node *p ) { int count = 0 ; while ( p != NULL ) { count++; p = p->link; } return ( count ) ; }