Archive for October, 2010

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


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

Linked List before Insertion of the new node

Linked List after Insertion of the new node

Advertisements

Leave a comment

How to insert a node in a linked list recursively?


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

Leave a comment

Deleting a node from doubly linked list


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


Leave a comment

What are Doubly Linked Lists?


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:

  1. A singly linked list allows traversal of the list in only one direction.
  2. 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.
  3. 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.

Figure 1 : Doubly Linked List as a chain

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

Figure 2 : Doubly Linked List maintained as circular list

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.

Figure 3 : A doubly linked list maintained as a circular list with a header node.

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

2 Comments

How to delete a specified node from a Linked List?


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

Figure 1 : before delete

Figure 2 : After delete

1 Comment