CODEWITHSUNDEEP
cdoubly-linked-list
mualloc
mualloc

Reputation: 523

How to split doubly linked list alternately

OK. I have an assignment in c programming course. I need to implement a function prototype which is: 

void split(node* head, node **first, node **second)

This function splits the doubly-linked list pointed by head to two lists first and second.

Assume that head holds the elements F0,S0,F1,S1,F2,S2,...

Then:

Do not make any allocations or deallocations (malloc, calloc, realloc, free). Only update pointers. Do not change node data.

Restrictions: Do not use malloc(), calloc(), realloc(),free().

I am stuck, I can't produce any algorithm. PLease, help!

typedef struct node
{
    int data;
    struct node *prev;
    struct node *next;
} node;

EDIT FOR SOLUTION:

    #define DATA(p) ((p)->data)
    #define NEXT(p) ((p)->next)
    #define PREV(p) ((p)->prev)



    void split ( node* head, node **first, node **second )
    {
        node* firstCurrent = head;
        node* secondCurrent = NULL;
        node* dummyforbprev = NULL;

        if ( firstCurrent )
        {
            secondCurrent = NEXT(firstCurrent);
            if(secondCurrent)
                PREV(secondCurrent)=NULL;
        }

        *first = firstCurrent;
        *second = secondCurrent;

        while ( firstCurrent && secondCurrent )
        {
            NEXT(firstCurrent) = NEXT(secondCurrent);
            dummyforbprev = PREV(firstCurrent);
            firstCurrent = NEXT(firstCurrent);
            if(firstCurrent)
                PREV(firstCurrent) = PREV(secondCurrent);

            if ( firstCurrent )
                NEXT(secondCurrent) = NEXT(firstCurrent);
            PREV(secondCurrent) = dummyforbprev;
            secondCurrent = NEXT(secondCurrent);
        }

        if ( firstCurrent )
            NEXT(firstCurrent) = NULL;

        if ( secondCurrent )
            NEXT(secondCurrent) = NULL;
    }

Upvotes: 0

Views: 2573

Answers (2)

J Doe
J Doe

Reputation: 1

We can also use queue operations and bool or int variable to
switch between destination lists

altsplit(L:List;var L1,L2:List)
   L1.head = NIL;
   L1.tail = NIL;
   L2.head = NIL;
   L2.tail = NIL;
   s = false
   while not isEmpty(L) do
        x = dequeue(L)
        if not s then
             enqueue(L1,x)
        else
             enqueue(L2,x);
        s := not s;

Note that we dont need to allocate memory for new nodes
We simply set pointers in the same way like in queue

Upvotes: 0

paxdiablo
paxdiablo

Reputation: 882326

Without allocating any new nodes for the new lists, it's a matter of simply adjusting pointers to form the new lists, keeping in mind that this, by necessity, modifies the list you pass in.

Starting with a list like:

head -> 1 -> 2 -> 3 -> 4 -> 6 -> null

it's relatively easy to work in groups of two nodes and allocate them to the new lists. You basically start by ensuring there are two or more nodes in the list, otherwise the first list returned is the original anfd the second list is empty.

Once you've checked that, set up head pointers for the lists to return, as well as roving pointers to keep track of the last item in each list:

second ------|
first --|    |
head -> 1 -> 2 -> 3 -> 4 -> 6 -> null
fEnd ---|    |
sEnd --------|

Then, simplistically, you perform the following steps:

  • Set the fEnd next value to be the sEnd next value (so 1 now points to 3) then advance the fEnd pointer to 3.
  • Set the sEnd next value to be the fEnd next value (so 2 now points to 4) then advance the sEnd pointer to 4.

Now you have this situation:

sEnd --------------------|
fEnd ---------------|    |
           ________ |    |
          /        \     |
first/ -> 1    2    3 -> 4 -> 6 -> null
 head          |\        /
               | \______/
second --------|

where you can see the front part of the list has been split and the pointers have been advanced to the remainder of the list.

You simply carry on doing this until you reach the end of the list.

Now you'll notice the word "simplistically" mentioned above. While the concept explained here is simple, there are a couple of complicating factors.

The first is the fact that you may not be able to process groups of two nodes, simply because there may be an odd number of nodes in the list. Secondly, there's the usual problems with dealing with the ends of linked lists where you have to be careful with things like:

node->next->prev = node;

where node may be at the end, something likely to cause crashes as you dereference node->next.

Still, that's just a little bit of extra safety built in to the functions. You can see a complete program below which illustrates how to do it, firstly the headers, node structure and a helper function for dumping a list in readable form (and ensuring it's not corrupted):

#include <stdio.h>
#include <stdlib.h>

typedef struct sNode {
    int value;
    struct sNode *next;
    struct sNode *prev;
} tNode;

static void dump (char *desc, tNode *head) {
    printf ("Dumping %s: ", desc);
    tNode *p = head;
    while (p != NULL) {
        if ((p != head) && (p->prev->next != p)) {
            printf ("double-link error\n");
            exit (1);
        }
        printf ("%d -> ", p->value);
        p = p->next;
    }
    puts ("NULL");
}

Secondly, the "meat" of the solution, a split() function as per your requirements, which takes a single list and returns two lists each with alternating values from the original:

void split (tNode* head, tNode **pFirst, tNode **pSecond) {
    // Must have two elements or more to split.

    if ((head == NULL) || (head->next == NULL)) {
        *pFirst = head;
        *pSecond = NULL;
        return;
    }

    // Set up list heads and roving pointers.

    tNode *first = head, *second = head->next;
    tNode *fEnd = first, *sEnd = second;

    // Do whole list in groups of two, but check to ensure
    //   no crashes due to invalid pointer dereferences.

    while (fEnd != NULL) {
        // First in group of two.

        if (sEnd != NULL) {
            fEnd->next = sEnd->next;
            if (fEnd->next != NULL)
                fEnd->next->prev = fEnd;
        }
        if (fEnd != NULL)
            fEnd = fEnd->next;

        // Second in group of two.

        if (fEnd != NULL) {
            sEnd->next = fEnd->next;
            if (sEnd->next != NULL)
                sEnd->next->prev = sEnd;
        }
        if (sEnd != NULL)
            sEnd = sEnd->next;
    }

    // Return lists to caller.

    *pFirst = first;
    *pSecond = second;
}

As mentioned earlier, that function also affects the original list since it has to use the original nodes, and changing the next/prev values within those nodes morphs the original list as well.

The final bit of code is the test harness, which simply gives you a list of increasing integers in each node (the size being based on whatever argument you give, or ten if you give none).

It constructs the list and outputs it, then calls the split() function and shows you the results:

int main (int argc, char *argv[]) {
    int quant = (argc > 1) ? atoi (argv[1]) : 10;
    tNode *head = NULL, *first, *second;

    for (int i = quant - 1; i >= 0; i--) {
        tNode *add = malloc (sizeof (*add));
        add->value = i + 1;
        add->next = head;
        add->prev = NULL;
        if (head != NULL) head->prev = add;
        head = add;
    }

    dump ("before", head);
    split (head, &first, &second);
    dump ("after (first) ", first);
    dump ("after (second)", second);

    return 0;
}

The output of that program can be seen in the following transcript:

$ ./testprog 0
Dumping before: NULL
Dumping after (first) : NULL
Dumping after (second): NULL

$ ./testprog 1
Dumping before: 1 -> NULL
Dumping after (first) : 1 -> NULL
Dumping after (second): NULL

$ ./testprog 2
Dumping before: 1 -> 2 -> NULL
Dumping after (first) : 1 -> NULL
Dumping after (second): 2 -> NULL

$ ./testprog 3
Dumping before: 1 -> 2 -> 3 -> NULL
Dumping after (first) : 1 -> 3 -> NULL
Dumping after (second): 2 -> NULL

$ ./testprog
Dumping before: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> NULL
Dumping after (first) : 1 -> 3 -> 5 -> 7 -> 9 -> NULL
Dumping after (second): 2 -> 4 -> 6 -> 8 -> 10 -> NULL

$ ./testprog 9
Dumping before: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL
Dumping after (first) : 1 -> 3 -> 5 -> 7 -> 9 -> NULL
Dumping after (second): 2 -> 4 -> 6 -> 8 -> NULL

Upvotes: 1

Related Questions