Can't delete the duplicated data of doubly linked list in C

Question

I have an issue with deleting the duplicated data from a doubly linked list. So, the data element of this list is an array of numbers. I want to delete the nodes of the repetitive data with this delete_duplicates code.

I use this following print_list function to print the list. The function doesn't seem to have a bug because it prints the unsorted first list with duplicates very well.

I also use this convert_array_to_list function to make a list from the array. Again, this function doesn't seem to have a bug because the first list doesn't have any problem.

The full code of the program:

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

struct doubly_linked_list
{
    int data[200];
    struct doubly_linked_list *prev;
    struct doubly_linked_list *next;
};

void print_list(struct doubly_linked_list *list_head)
{
    int i;

    printf("\n");

    for(i=0; i<200; i++) {

        printf("%d ", list_head->data[i]);
        list_head = list_head->next;
        if (i%25 == 0 & i != 0) {
            printf("\n");
        }
    } 
}

struct doubly_linked_list *convert_array_to_list(int array[], int size, struct doubly_linked_list *list_head)
{
    struct doubly_linked_list *list_first = NULL; //as the first node
    struct doubly_linked_list *list_new = NULL; //as the current node
    int i;
    
    if (size <= 0) //just to check
    {
        printf("Error!");
    }
    
    for(i=0; i<size; i++) {
        struct doubly_linked_list *list_now = (struct doubly_linked_list*)malloc (sizeof (struct doubly_linked_list)); //as the temporary node
        list_now->data[i] = array[i];

        if (NULL == list_now) //just to check
        {
            printf("Error!\n");
            break;
        }
        
        if(list_new == NULL)
        {
            list_now->data[i] = array[i];
            list_new = list_now;
            list_new->prev = NULL;
            list_new->next = NULL;
            list_first = list_new;
            //starting the list as circular
        }
        else
        {
            list_now->data[i] = array[i];
            list_new->next = list_now;
            list_now->prev = list_new;
            list_now->next = NULL;
            list_new = list_now;
            //adding the new node to the end of the list
        }
    }

    return list_first;
}

struct doubly_linked_list *delete_duplicates(struct doubly_linked_list *list_head)
{
    int i;
    struct doubly_linked_list *left;
    struct doubly_linked_list *right;
    struct doubly_linked_list *prev;
    struct doubly_linked_list *next;
    int deleted;
    for(left = list_head;  left != NULL;  left = left->next) {
        prev = left;
        for(right = left->next;  right != NULL;  right = next) {
            next = right->next;
            deleted = 0;
            for (i = 0;  i < sizeof(left->data) / sizeof(left->data[0]);  ++i) {
                deleted = (left->data[i] == right->data[i]);
                if (deleted) {
                    break;
                }
            }
            if (deleted) {
                prev->next = next;
                free(right);
            }
            else {
                prev = right;
            }       
        }
    }
};


int *random_array_generator(int array[], int size)
{
    int i;
    for(i=0; i<size; i++) {
        unsigned short int number = rand() % 50; //the array should be from [0,49]
        array[i] = number;
    }
    return array;
};

int main()
{
    int i;
    int numbers[200];
    srand(time(0));
    
    random_array_generator(numbers, 200);
    
    struct doubly_linked_list *list_head = NULL;
    
    list_head = convert_array_to_list(numbers, 200, list_head);
    
    printf("First list with dublication: \n");
    print_list(list_head);

    printf("\n\n");
    
    list_head = delete_duplicates(list_head);
    
    printf("Second list without dublication: \n");
    print_list(list_head);
    
    return 0;
}

The output of the first list is perfect, but it doesn't print the second list. I debugged it and added watch to the left->data[i] and right->data[i] and they seem to have a problem with pointing the right data. At first, left->data[0] has the right value while right->data[0] has a nonsense big number value. Then as the loop goes forward, as i changes, the value of the left->data[i] gets the value of this nonsense big number too and the program goes to delete_duplicates function. After all, when it tries to print the second list, program gets an error called "Segmentation fault", it cannot access the list_head->data[i] value. I couldn't solve the problem, I tried so many combinations of different codes but the program always gives an error when it comes to point the next element of the array, it says it cannot access the memory or a segmentation fault. I would appreciate your help.

Answer 1

A few issues ...

1. The code does not break out of the i loop after deleting the node on a single match of a char in the data element, so it's trying to delete the same node up to 200 times.
2. I think [I didn't look super closely] that: After a given node is deleted, doing list_head->next->next is a "use after free" bug. We need to grab the value before the delete (e.g.) next = list->next
3. To compare every node against every other node, we need a second nested loop for the node compares.
4. list_head can never be deleted as a duplicate, so no need to have a return list_head; as list_head will not change.
5. Although we can have a separate delete_node function [for other purposes], the actual deletion is so trivial that it's easier if delete_duplicates just does it inline.
6. In delete_duplicates, we already know what the previous node is, so it is faster to not use delete_node (as it must rescan the entire list to find the previous node).
7. The criteria for selecting a duplicate is unclear. With the existing code, if any element in data matches, the node is deleted. While this is a valid thing to do, the more usual is to delete a node if all elements match. However, I've left the original intent.

Here is the refactored code. It is annotated:

#include <stdlib.h>

struct doubly_linked_list {
    int data[200];
    struct doubly_linked_list *prev;
    struct doubly_linked_list *next;
};

struct doubly_linked_list *
delete_duplicates(struct doubly_linked_list *list_head)
{
    int i;
    struct doubly_linked_list *left;
    struct doubly_linked_list *right;
    struct doubly_linked_list *prev;
    struct doubly_linked_list *next;
    int del;

    for (left = list_head;  left != NULL;  left = left->next) {
        prev = left;

        for (right = left->next;  right != NULL;  right = next) {
            // point to next node:
            // (1) prevents "use after free" by the iteration expression above
            // (2) more efficient
            next = right->next;

            // say _not_ a duplicate
            del = 0;

            // scan buffer for a match
            for (i = 0;  i < sizeof(left->data) / sizeof(left->data[0]);  ++i) {
                del = (left->data[i] == right->data[i]);
                if (del)
                    break;
            }

            // delete duplicate node
            if (del) {
                prev->next = next;
                free(right);
            }

            // advance previous node
            else
                prev = right;
        }
    }

// NOTE/BUG: list_head will never change so this isn't needed
    return list_head;
}

---

UPDATE:

Thank you all for your answers. Dear Craig Estey, I used the refactored code you wrote but the output was like, it prints the first element right but then all of the remaining elements were printed as 0. By the way I don't know why my question is closed because of debugging details, I'm still new here though :) – Ozdamar Kevser

Sometimes, people here can be overzealous with close votes, particularly if the OP doesn't repond to comments requesting clarification. But, here this answer was already up.

As I mentioned, I wrote [and compiled] the above code but didn't test it.

I've created a test program to verify things. It appears that my refactored function does work but I didn't set the prev pointers in the nodes [because I thought it was a singly linked list--now fixed]. But, I don't think that would caused an issue if printing the list in the forward direction.

So, it may be something about the way you're creating or printing the list.

Here is the fully refactored code with a test program:

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

// NDATA -- number of elements in array
#ifndef NDATA
#define NDATA   200
#endif

// ALLMATCH -- duplicate detection critera
//   0=any element can match (original)
//   1=all must match (suitable for testing)
#ifndef ALLMATCH
#define ALLMATCH    1
#endif

typedef struct node node_t;
struct node {
    node_t *prev;
    node_t *next;
    int idx;                                // easy identifier for debug
    int data[NDATA];
};

node_t *global_head;

unsigned int opt_R;                         // random number seed
int opt_N;                                  // number of nodes to generate

// print_node -- print a node
void
print_node(node_t *head)
{
    int totlen = 0;

    for (int dataidx = 0;  dataidx < NDATA;  ++dataidx) {
        if (dataidx == 0)
            totlen += printf(" NODE  ");

        totlen += printf(" %6d",head->data[dataidx]);

        if (totlen >= 60) {
            printf("\n");
            totlen = 0;
        }
    }

    totlen += printf(" [%d]",head->idx);

    if (totlen > 0)
        printf("\n");
}

// print_list -- print list of nodes
void
print_list(node_t *head,const char *who)
{

    printf("\n");
    printf("%s:\n",who);

    for (;  head != NULL;  head = head->next)
        print_node(head);
}

// delete_duplicates -- delete duplicate nodes in list
void
delete_duplicates(node_t *list_head)
{
    int i;
    node_t *left;
    node_t *right;
    node_t *prev;
    node_t *next;
    int del;

    for (left = list_head;  left != NULL;  left = left->next) {
        prev = left;

        for (right = left->next;  right != NULL;  right = next) {
            // point to next node:
            // (1) prevents "use after free" by the iteration expression above
            // (2) more efficient
            next = right->next;

            // say _not_ a duplicate
#if ALLMATCH
            del = 1;
#else
            del = 0;
#endif

            // scan buffer for a match
            for (i = 0;  i < NDATA;  ++i) {
                // original -- delete if _any_ element matches
#if ! ALLMATCH
                del = (left->data[i] == right->data[i]);
                if (del)
                    break;
                // modified -- delete if _all_ element matches
#else
                if (left->data[i] != right->data[i]) {
                    del = 0;
                    break;
                }
#endif
            }

            // delete duplicate node
            if (del) {
                printf("delete_duplicates: %d is dup of %d\n",
                    right->idx,left->idx);

                prev = right->prev;

                // cross link previous and next nodes (eliminating current)
                if (prev != NULL)
                    prev->next = next;
                if (next != NULL)
                    next->prev = prev;

                free(right);
            }
        }
    }
}

// select_node -- select a random previous node
node_t *
select_node(node_t *head,int count)
{
    int lstidx = rand() % count;

    for (;  lstidx > 0;  --lstidx)
        head = head->next;

    if (head == NULL) {
        printf("find_dup: null head\n");
        exit(1);
    }

    return head;
}

// generate_list -- generate a list with a random number of duplicates
node_t *
generate_list(int count)
{
    node_t *head = NULL;
    node_t *prev = NULL;
    node_t temp;
    int dupcnt = 0;

    for (int lstidx = 0;  lstidx < count;  ++lstidx) {
        int dupflg = (rand() % 100) < 20;

        if (lstidx == 0)
            dupflg = 0;

        node_t *dup;

        // find a node that we'll duplicate
        if (dupflg) {
            dup = select_node(head,lstidx);
            ++dupcnt;
        }

        // generate new random node
        else {
            dup = &temp;
            for (int dataidx = 0;  dataidx < NDATA;  ++dataidx)
                dup->data[dataidx] = rand() & 0xFFFF;
        }

        node_t *newnode = malloc(sizeof(*newnode));

        // copy in the data
        for (int dataidx = 0;  dataidx < NDATA;  ++dataidx)
            newnode->data[dataidx] = dup->data[dataidx];

        // set the node id and links
        newnode->idx = lstidx;
        newnode->prev = prev;
        newnode->next = NULL;

        // append to tail of list
        if (prev != NULL)
            prev->next = newnode;

        // start new list
        else
            head = newnode;

        prev = newnode;
    }

    printf("generate_list: %d dups of %d total nodes\n",dupcnt,count);

    return head;
}

int
main(int argc,char **argv)
{

    --argc;
    ++argv;

    opt_N = 20;
    opt_R = 1;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        cp += 2;
        switch (cp[-1]) {
        case 'N':
            opt_N = (*cp != 0) ? atoi(cp) : 50;
            break;

        case 'R':
            opt_R = (*cp != 0) ? atoi(cp) : time(NULL);
            break;
        }
    }

    printf("N = %d\n",opt_N);

    printf("R = %u\n",opt_R);
    srand(opt_R);

    global_head = generate_list(opt_N);
    print_list(global_head,"ORIGINAL");

    delete_duplicates(global_head);
    print_list(global_head,"NODUP");

    return 0;
}

Here is the program output for -DNDATA=1:

N = 20
R = 1
generate_list: 2 dups of 20 total nodes

ORIGINAL:
 NODE     9158 [0]
 NODE    18547 [1]
 NODE    23807 [2]
 NODE    22764 [3]
 NODE    31949 [4]
 NODE    55211 [5]
 NODE     7931 [6]
 NODE    57670 [7]
 NODE    25282 [8]
 NODE    10232 [9]
 NODE    25282 [10]
 NODE    17293 [11]
 NODE     9562 [12]
 NODE    29283 [13]
 NODE    55199 [14]
 NODE     1946 [15]
 NODE    23858 [16]
 NODE    55223 [17]
 NODE    58456 [18]
 NODE    23858 [19]
delete_duplicates: 10 is dup of 8
delete_duplicates: 19 is dup of 16

NODUP:
 NODE     9158 [0]
 NODE    18547 [1]
 NODE    23807 [2]
 NODE    22764 [3]
 NODE    31949 [4]
 NODE    55211 [5]
 NODE     7931 [6]
 NODE    57670 [7]
 NODE    25282 [8]
 NODE    10232 [9]
 NODE    17293 [11]
 NODE     9562 [12]
 NODE    29283 [13]
 NODE    55199 [14]
 NODE     1946 [15]
 NODE    23858 [16]
 NODE    55223 [17]
 NODE    58456 [18]

---

UPDATE #2:

So I tried to use your test program in my computer but it didn't work well, it can't escape from printing the list like an infinite loop or so.

I'm not seeing that issue when I run the above program [from my first update]. Please be sure that you're using my latest example exactly.

I'm using gcc under [fedora] linux. Most other systems should be fine as well:

1. Other linux distros or *BSD systems should have no problems.
2. MacOS can be quirky in how it builds (since the compiler is clang and the OS's different relocatable/executable formats).
3. Windows (visual studio) can be problematic but is usually okay as well.
4. Windows (either cygwin or mingw) should be even better

The only other issue might be your system's rand implementation producing different random numbers that expose a flaw in my algorithm because the test values used are different.

And about my program, I tried so many options to delete the duplicates but still couldn't figure out. I edit my question and add the full program so you could debug it that way.

I haven't seen your latest update for your latest full program.

I use the same printing function so it doesn't seem to have a problem at all, the poblem occurs when I try to delete the duplicated data. Thanks a lot. – Ozdamar Kevser

Some possible debugging ideas:

1. Running the program under a debugger (e.g. gdb)
2. Running the program under valgrind
3. Compiling the program with -fsanitize=address

Also, what is the exact nature of the "problem"?

The only other thing I can think of that might be different from my program is the use of the head as a list.

There are two uses:

1. head is the first valid node of the list (which is what I did).
2. head is a pointer to a "dummy" node. prev is the list head and next is the list tail. IMO, this is "poor man's" implementation of a "list" struct.

Personally, I dislike both options (especially (2)). To make things clearer and more flexible, I prefer to create a separate list struct (distinct from the node struct). This is similar to (2), but is cleaner and more explicit. It also allows extra information, such as the list count.

Here is a further refactored version that does that. It also runs the test multiple times with different random values:

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

#define sysfault(_fmt...) \
    do { \
        printf(_fmt); \
        exit(1); \
    } while (0)

// NDATA -- number of elements in array
#ifndef NDATA
#define NDATA   1
#endif

// ALLMATCH -- duplicate detection critera
//   0=any element can match (original)
//   1=all must match (suitable for testing)
#ifndef ALLMATCH
#define ALLMATCH    1
#endif

typedef struct node node_t;
struct node {
    node_t *prev;
    node_t *next;
    int idx;                                // easy identifier for debug
    int data[NDATA];
};

typedef struct list {
    int count;
    node_t *head;
    node_t *tail;
} list_t;

list_t *global_list;                        // list that may have duplicates
list_t *nodup_list;                         // same list _without_ duplicates

int opt_N;                                  // number of nodes to generate
unsigned int opt_R;                         // random number seed
int opt_T;                                  // number of tests

// node_print -- print a node
void
node_print(node_t *cur)
{
    int totlen = 0;

    for (int dataidx = 0;  dataidx < NDATA;  ++dataidx) {
        if (dataidx == 0)
            totlen += printf(" NODE  ");

        totlen += printf(" %6d",cur->data[dataidx]);

        if (totlen >= 60) {
            printf("\n");
            totlen = 0;
        }
    }

    totlen += printf(" [%d]",cur->idx);

    if (totlen > 0)
        printf("\n");
}

// list_print -- print list of nodes (forward)
void
list_print(list_t *list,const char *who)
{
    node_t *cur;

    printf("\n");
    printf("%s: (%d elements)\n",who,list->count);

    for (cur = list->head;  cur != NULL;  cur = cur->next)
        node_print(cur);
}

// list_rprint -- print list of nodes (reverse)
void
list_rprint(list_t *list,const char *who)
{
    node_t *cur;

    printf("\n");
    printf("%s: (%d elements)\n",who,list->count);

    for (cur = list->tail;  cur != NULL;  cur = cur->prev)
        node_print(cur);
}

// node_equal -- compare two nodes
// RETURNS: 0=mismatch, 1=equal
int
node_equal(node_t *lhs,node_t *rhs)
{
    int match;

    // say _not_ a match
#if ALLMATCH
    match = 1;
#else
    match = 0;
#endif

    // scan buffer for a match
    for (int dataidx = 0;  dataidx < NDATA;  ++dataidx) {
        // original -- delete if _any_ element matches
#if ! ALLMATCH
        match = (lhs->data[dataidx] == rhs->data[dataidx]);
        if (match)
            break;

        // modified -- delete if _all_ element matches
#else
        if (lhs->data[dataidx] != rhs->data[dataidx]) {
            match = 0;
            break;
        }
#endif
    }

    return match;
}

// list_unlink -- unlink node from list
node_t *
list_unlink(list_t *list,node_t *del)
{
    node_t *prev;
    node_t *next;

    next = del->next;
    prev = del->prev;

    // cross link previous and next nodes (eliminating current)
    if (prev != NULL)
        prev->next = next;
    if (next != NULL)
        next->prev = prev;

    if (list->head == del)
        list->head = next;

    if (list->tail == del)
        list->tail = prev;

    list->count -= 1;

    free(del);

    return next;
}

// delete_duplicates -- delete duplicate nodes in list
void
delete_duplicates(list_t *list)
{
    node_t *left;
    node_t *right;
    node_t *next;
    int del;

    for (left = list->head;  left != NULL;  left = left->next) {
        for (right = left->next;  right != NULL;  right = next) {
            // decide if the node is a duplicate
            del = node_equal(left,right);

            // delete duplicate node
            if (del) {
                printf("delete_duplicates: %d is dup of %d\n",
                    right->idx,left->idx);
                next = list_unlink(list,right);
            }

            // advance to next node
            else
                next = right->next;
        }
    }
}

// list_select -- select a random previous node
node_t *
list_select(list_t *list)
{
    int lstidx = rand() % list->count;
    node_t *cur = list->head;

    for (;  lstidx > 0;  --lstidx)
        cur = cur->next;

    if (cur == NULL)
        sysfault("list_select: null cur\n");

    return cur;
}

// list_append -- append to list
void
list_append(list_t *list,node_t *src)
{
    node_t *newnode = malloc(sizeof(*newnode));

    // copy in the data
    for (int dataidx = 0;  dataidx < NDATA;  ++dataidx)
        newnode->data[dataidx] = src->data[dataidx];

    node_t *tail = list->tail;

    // set the node id and links
    newnode->idx = list->count++;
    newnode->prev = tail;
    newnode->next = NULL;

    // start of new list
    if (list->head == NULL)
        list->head = newnode;

    // set tail's forward link
    if (tail != NULL)
        tail->next = newnode;

    // set new node's backward link
    newnode->prev = tail;

    // make new node the tail of the list
    list->tail = newnode;
}

// list_generate -- generate a list with a random number of duplicates
void
list_generate(int count)
{
    node_t temp;
    int dupcnt = 0;

    // list that can have dups
    global_list = calloc(1,sizeof(*global_list));

    // list without dups
    nodup_list = calloc(1,sizeof(*nodup_list));

    for (int lstidx = 0;  lstidx < count;  ++lstidx) {
        int dupflg = (rand() % 100) < 20;

        if (lstidx == 0)
            dupflg = 0;

        node_t *cur;

        // find a node that we'll duplicate
        if (dupflg) {
            cur = list_select(global_list);
            ++dupcnt;
        }

        // generate new random node
        else {
            cur = &temp;
            for (int dataidx = 0;  dataidx < NDATA;  ++dataidx)
                cur->data[dataidx] = rand() & 0xFFFF;

            list_append(nodup_list,cur);
        }

        list_append(global_list,cur);
    }

    printf("list_generate: %d dups of %d total nodes\n",dupcnt,count);
}

// list_destroy -- destroy a list
list_t *
list_destroy(list_t *list)
{

    // free all nodes in list
    node_t *next;
    for (node_t *cur = list->head;  cur != NULL;  cur = next) {
        next = cur->next;
        free(cur);
    }

    // free the list itself
    free(list);

    list = NULL;

    return list;
}

// list_compare -- compare two lists
void
list_compare(list_t *lhslist,list_t *rhslist)
{
    node_t *lhs = lhslist->head;
    node_t *rhs = rhslist->head;

    if (lhslist->count != rhslist->count)
        sysfault("list_compare: count mismatch -- lhs=%d rhs=%d\n",
            lhslist->count,rhslist->count);

    while (1) {
        if (lhs == NULL)
            break;
        if (rhs == NULL)
            break;

        int same = node_equal(lhs,rhs);

        if (! same) {
            printf("list_compare: mismatch\n");
            node_print(lhs);
            node_print(rhs);
            sysfault("list_compare: aborting\n");
        }

        lhs = lhs->next;
        rhs = rhs->next;
    }

    printf("list_compare: complete\n");
}

// dotest -- do a test
void
dotest(int tstno)
{

    if (tstno > 1)
        printf("\n");
    for (int sep = 1;  sep <= 80;  ++sep)
        fputc('-',stdout);
    fputc('\n',stdout);

    printf("TEST %d of %d\n",tstno,opt_T);

    list_generate(opt_N);

    list_print(global_list,"global_list/ORIGINAL");
    list_print(nodup_list,"nodup_list");

    delete_duplicates(global_list);
    list_print(global_list,"global_list/NODUP");
    list_rprint(global_list,"global_list/REVERSE");

    printf("\n");
    list_compare(global_list,nodup_list);

    global_list = list_destroy(global_list);
    nodup_list = list_destroy(nodup_list);
}

int
main(int argc,char **argv)
{

    --argc;
    ++argv;

    opt_N = 20;
    opt_R = 1;
    opt_T = 5;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        cp += 2;
        switch (cp[-1]) {
        case 'N':
            opt_N = (*cp != 0) ? atoi(cp) : 50;
            break;

        case 'R':
            opt_R = (*cp != 0) ? atoi(cp) : time(NULL);
            break;

        case 'T':
            opt_T = (*cp != 0) ? atoi(cp) : 10;
            break;
        }
    }

    printf("N = %d\n",opt_N);

    printf("R = %u\n",opt_R);
    srand(opt_R);

    if (opt_T <= 0)
        opt_T = 1;
    printf("T = %d\n",opt_T);

    for (int tstno = 1;  tstno < opt_T;  ++tstno)
        dotest(tstno);

    return 0;
}

Below is the program output.

Note that I also built/ran the program under:

1. valgrind with no errors
2. Compiled with -fsanitize=address (no errors)

N = 20
R = 1
T = 5
--------------------------------------------------------------------------------
TEST 1 of 5
list_generate: 2 dups of 20 total nodes

global_list/ORIGINAL: (20 elements)
 NODE     9158 [0]
 NODE    18547 [1]
 NODE    23807 [2]
 NODE    22764 [3]
 NODE    31949 [4]
 NODE    55211 [5]
 NODE     7931 [6]
 NODE    57670 [7]
 NODE    25282 [8]
 NODE    10232 [9]
 NODE    25282 [10]
 NODE    17293 [11]
 NODE     9562 [12]
 NODE    29283 [13]
 NODE    55199 [14]
 NODE     1946 [15]
 NODE    23858 [16]
 NODE    55223 [17]
 NODE    58456 [18]
 NODE    23858 [19]

nodup_list: (18 elements)
 NODE     9158 [0]
 NODE    18547 [1]
 NODE    23807 [2]
 NODE    22764 [3]
 NODE    31949 [4]
 NODE    55211 [5]
 NODE     7931 [6]
 NODE    57670 [7]
 NODE    25282 [8]
 NODE    10232 [9]
 NODE    17293 [10]
 NODE     9562 [11]
 NODE    29283 [12]
 NODE    55199 [13]
 NODE     1946 [14]
 NODE    23858 [15]
 NODE    55223 [16]
 NODE    58456 [17]
delete_duplicates: 10 is dup of 8
delete_duplicates: 19 is dup of 16

global_list/NODUP: (18 elements)
 NODE     9158 [0]
 NODE    18547 [1]
 NODE    23807 [2]
 NODE    22764 [3]
 NODE    31949 [4]
 NODE    55211 [5]
 NODE     7931 [6]
 NODE    57670 [7]
 NODE    25282 [8]
 NODE    10232 [9]
 NODE    17293 [11]
 NODE     9562 [12]
 NODE    29283 [13]
 NODE    55199 [14]
 NODE     1946 [15]
 NODE    23858 [16]
 NODE    55223 [17]
 NODE    58456 [18]

global_list/REVERSE: (18 elements)
 NODE    58456 [18]
 NODE    55223 [17]
 NODE    23858 [16]
 NODE     1946 [15]
 NODE    55199 [14]
 NODE    29283 [13]
 NODE     9562 [12]
 NODE    17293 [11]
 NODE    10232 [9]
 NODE    25282 [8]
 NODE    57670 [7]
 NODE     7931 [6]
 NODE    55211 [5]
 NODE    31949 [4]
 NODE    22764 [3]
 NODE    23807 [2]
 NODE    18547 [1]
 NODE     9158 [0]

list_compare: complete

--------------------------------------------------------------------------------
TEST 2 of 5
list_generate: 5 dups of 20 total nodes

global_list/ORIGINAL: (20 elements)
 NODE    35165 [0]
 NODE    41751 [1]
 NODE    23273 [2]
 NODE    43220 [3]
 NODE    23273 [4]
 NODE    41751 [5]
 NODE    40628 [6]
 NODE    34321 [7]
 NODE     7554 [8]
 NODE    34369 [9]
 NODE    41751 [10]
 NODE    61575 [11]
 NODE    56809 [12]
 NODE    54433 [13]
 NODE    34321 [14]
 NODE     9063 [15]
 NODE    24321 [16]
 NODE    35165 [17]
 NODE    19164 [18]
 NODE    30614 [19]

nodup_list: (15 elements)
 NODE    35165 [0]
 NODE    41751 [1]
 NODE    23273 [2]
 NODE    43220 [3]
 NODE    40628 [4]
 NODE    34321 [5]
 NODE     7554 [6]
 NODE    34369 [7]
 NODE    61575 [8]
 NODE    56809 [9]
 NODE    54433 [10]
 NODE     9063 [11]
 NODE    24321 [12]
 NODE    19164 [13]
 NODE    30614 [14]
delete_duplicates: 17 is dup of 0
delete_duplicates: 5 is dup of 1
delete_duplicates: 10 is dup of 1
delete_duplicates: 4 is dup of 2
delete_duplicates: 14 is dup of 7

global_list/NODUP: (15 elements)
 NODE    35165 [0]
 NODE    41751 [1]
 NODE    23273 [2]
 NODE    43220 [3]
 NODE    40628 [6]
 NODE    34321 [7]
 NODE     7554 [8]
 NODE    34369 [9]
 NODE    61575 [11]
 NODE    56809 [12]
 NODE    54433 [13]
 NODE     9063 [15]
 NODE    24321 [16]
 NODE    19164 [18]
 NODE    30614 [19]

global_list/REVERSE: (15 elements)
 NODE    30614 [19]
 NODE    19164 [18]
 NODE    24321 [16]
 NODE     9063 [15]
 NODE    54433 [13]
 NODE    56809 [12]
 NODE    61575 [11]
 NODE    34369 [9]
 NODE     7554 [8]
 NODE    34321 [7]
 NODE    40628 [6]
 NODE    43220 [3]
 NODE    23273 [2]
 NODE    41751 [1]
 NODE    35165 [0]

list_compare: complete

--------------------------------------------------------------------------------
TEST 3 of 5
list_generate: 3 dups of 20 total nodes

global_list/ORIGINAL: (20 elements)
 NODE    42040 [0]
 NODE    20010 [1]
 NODE    31920 [2]
 NODE    31920 [3]
 NODE    52399 [4]
 NODE    36692 [5]
 NODE     6936 [6]
 NODE    42076 [7]
 NODE    18458 [8]
 NODE    47939 [9]
 NODE     9978 [10]
 NODE    49978 [11]
 NODE    42281 [12]
 NODE    16358 [13]
 NODE    42040 [14]
 NODE    51092 [15]
 NODE    18458 [16]
 NODE    43105 [17]
 NODE    59897 [18]
 NODE     9915 [19]

nodup_list: (17 elements)
 NODE    42040 [0]
 NODE    20010 [1]
 NODE    31920 [2]
 NODE    52399 [3]
 NODE    36692 [4]
 NODE     6936 [5]
 NODE    42076 [6]
 NODE    18458 [7]
 NODE    47939 [8]
 NODE     9978 [9]
 NODE    49978 [10]
 NODE    42281 [11]
 NODE    16358 [12]
 NODE    51092 [13]
 NODE    43105 [14]
 NODE    59897 [15]
 NODE     9915 [16]
delete_duplicates: 14 is dup of 0
delete_duplicates: 3 is dup of 2
delete_duplicates: 16 is dup of 8

global_list/NODUP: (17 elements)
 NODE    42040 [0]
 NODE    20010 [1]
 NODE    31920 [2]
 NODE    52399 [4]
 NODE    36692 [5]
 NODE     6936 [6]
 NODE    42076 [7]
 NODE    18458 [8]
 NODE    47939 [9]
 NODE     9978 [10]
 NODE    49978 [11]
 NODE    42281 [12]
 NODE    16358 [13]
 NODE    51092 [15]
 NODE    43105 [17]
 NODE    59897 [18]
 NODE     9915 [19]

global_list/REVERSE: (17 elements)
 NODE     9915 [19]
 NODE    59897 [18]
 NODE    43105 [17]
 NODE    51092 [15]
 NODE    16358 [13]
 NODE    42281 [12]
 NODE    49978 [11]
 NODE     9978 [10]
 NODE    47939 [9]
 NODE    18458 [8]
 NODE    42076 [7]
 NODE     6936 [6]
 NODE    36692 [5]
 NODE    52399 [4]
 NODE    31920 [2]
 NODE    20010 [1]
 NODE    42040 [0]

list_compare: complete

--------------------------------------------------------------------------------
TEST 4 of 5
list_generate: 6 dups of 20 total nodes

global_list/ORIGINAL: (20 elements)
 NODE    15513 [0]
 NODE    16533 [1]
 NODE    13803 [2]
 NODE    20659 [3]
 NODE    20659 [4]
 NODE    48896 [5]
 NODE    60065 [6]
 NODE     2789 [7]
 NODE    20659 [8]
 NODE    13803 [9]
 NODE      583 [10]
 NODE    38589 [11]
 NODE    38589 [12]
 NODE    40616 [13]
 NODE    20659 [14]
 NODE    64965 [15]
 NODE    31603 [16]
 NODE    15513 [17]
 NODE     9035 [18]
 NODE    12131 [19]

nodup_list: (14 elements)
 NODE    15513 [0]
 NODE    16533 [1]
 NODE    13803 [2]
 NODE    20659 [3]
 NODE    48896 [4]
 NODE    60065 [5]
 NODE     2789 [6]
 NODE      583 [7]
 NODE    38589 [8]
 NODE    40616 [9]
 NODE    64965 [10]
 NODE    31603 [11]
 NODE     9035 [12]
 NODE    12131 [13]
delete_duplicates: 17 is dup of 0
delete_duplicates: 9 is dup of 2
delete_duplicates: 4 is dup of 3
delete_duplicates: 8 is dup of 3
delete_duplicates: 14 is dup of 3
delete_duplicates: 12 is dup of 11

global_list/NODUP: (14 elements)
 NODE    15513 [0]
 NODE    16533 [1]
 NODE    13803 [2]
 NODE    20659 [3]
 NODE    48896 [5]
 NODE    60065 [6]
 NODE     2789 [7]
 NODE      583 [10]
 NODE    38589 [11]
 NODE    40616 [13]
 NODE    64965 [15]
 NODE    31603 [16]
 NODE     9035 [18]
 NODE    12131 [19]

global_list/REVERSE: (14 elements)
 NODE    12131 [19]
 NODE     9035 [18]
 NODE    31603 [16]
 NODE    64965 [15]
 NODE    40616 [13]
 NODE    38589 [11]
 NODE      583 [10]
 NODE     2789 [7]
 NODE    60065 [6]
 NODE    48896 [5]
 NODE    20659 [3]
 NODE    13803 [2]
 NODE    16533 [1]
 NODE    15513 [0]

list_compare: complete