C Programming - Copy Linked List (including arbitrary pointer)

Given a Linked List of node structure as

struct Node {
    type element;
    Node *next;
    Node *arb;
};

You are asked to create an exact copy this linked list. Pointer arb points to an arbitrary node with in the Linked List.

Solution:

Suppose the original linked list is like
X1->X2->X3->....->NULL we are supposed to create another Linked List like Y1->Y2->Y3->....->NULL.
First we modify the Source Linked list to look like
X1->Y1->X2->Y2->X3->Y3->.....->NULL, during which we only copy the data element. In another loop we obtain the value of arb by considering the fact the Xn's arb's next will be Yn's arb. Then we reverse back the Source Linked list along with destination linked list to the orginal structure.

Code:

#include < iostream >
#define ARRAY 2,1,3,4,2,3,4,5,6,7,1
using namespace std;

typedef struct NODE {
    int data;
    struct NODE *next;
    struct NODE *arb;
} Node;


Node *head1 = NULL;
Node *head2 = NULL;

/* Create a Link List which has to be copied */
void vCreateLL(Node **head)
{
    int nArb[] = { ARRAY };
    Node *temp = NULL;
    int i;

    /* Creating LL and filling data element */
    for(i = 0; i < sizeof(nArb)/sizeof(nArb[0]); i++ ) {
        Node *tmp = (Node *) malloc(sizeof(Node));
        tmp->data = rand() % 10;
        tmp->arb = NULL;
        tmp->next = NULL;
        if(*head == NULL ) *head = tmp;
        else temp->next = tmp;
        temp = tmp;
    }

    /* Filling up arb with node location given in an array nArb */
    temp = *head;
    for(i = 0; i < sizeof(nArb)/sizeof(nArb[0]); i++ ) {
        Node *tmp = *head;
        for(int j = 0; j < nArb[i]; j++ ) {
            tmp = tmp->next;
            if ( tmp == NULL)
                tmp = *head;
        }
        temp->arb = tmp;
        temp = temp->next;
    }
}

/* Print the LL along with node pointed by arb */
void vPrintLL(Node *head)
{
    for(Node *tmp = head; tmp != NULL; tmp = tmp->next) {
        printf("[ %d->%d ] ",tmp->data,tmp->arb->data);
    }
    printf("\n");
}

/* Copy Function which copies the LL 
 *which starts with head1 to head2 
 */

void vCopyLL(Node *head1,Node**head2)
{
    Node *tmp;
    Node *tmp1 = NULL;
    for(tmp = head1; tmp!= NULL; tmp = tmp1) {
        Node *temp = (Node *) malloc(sizeof(Node));
        temp->data = tmp->data;
        temp->arb = NULL;
        temp->next = tmp->next;
        tmp->next = temp;
        tmp1 = temp->next;
        if ( *head2 == NULL )
            *head2 = temp;
    }

    for(tmp = head1; tmp!= NULL; tmp = tmp->next->next) 
        tmp->next->arb = tmp->arb->next;

    for(tmp = head1; tmp!= NULL; tmp = tmp->next) {
        tmp1 = tmp->next;
        tmp->next = tmp->next->next;
        if (tmp1->next != NULL ) 
            tmp1->next = tmp1->next->next;
        else
            tmp1->next = NULL;
    }
}

int main()
{
    vCreateLL(&head1);
    vPrintLL(head1);

    vCopyLL(head1,&head2);
    vPrintLL(head2);
    return 0;
}

Labels:

About this entry

You’re currently reading “C Programming - Copy Linked List (including arbitrary pointer),” an entry on ANOOB BACKER Technical Blog

Published:
8:59 pm
by -