Skip to content

@nesteruk /gist:1632784
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Random list generation program (with comments :)
#include <iostream>
using namespace std;
struct list_item
{
list_item *next;
list_item *rand;
};
void deep_copy(list_item* src, list_item* &dst)
{
// interleave src with dst such that src_1-->dst_1-->src_2-->dst_2 etc.
list_item *current = src, *temp;
dst = NULL;
while (current != NULL)
{
// allocate a matching dst element
list_item* li = new list_item;
// if it's the first ever, assign it as the output
if (dst == NULL)
dst = li;
// assign the element's next, but null the rand for now
li->next = current->next;
li->rand = NULL;
// rearrange the pointers for src_n->dst_n and move on
current->next = li;
current = li->next;
}
// for a given src element, its rand->next is the projected dst element
for (current = src; current != NULL; current = current->next->next)
{
// guard against the (unlikely) case of the rand not pointing anywhere :)
if (current->rand != NULL)
current->next->rand = current->rand->next;
}
// now separate the src|dst list into two lists
for (current = src; current != NULL;)
{
// cache the next item's address (it may very well be NULL)
temp = current->next->next;
// is there a next src+dst pair?
bool have_next = temp != NULL;
// if there is, do the forward pointers, otherwise null
current->next->next = have_next ? temp->next : NULL;
current->next = have_next ? temp : NULL;
// move forward
current = temp;
}
}
// utility function for deleting a list
void delete_list(list_item* first)
{
if (first->next != NULL)
delete_list(first->next);
delete first;
}
void main()
{
cout.setf(ios_base::boolalpha);
// test 1 - copy single element with rand=null
list_item* first = new list_item;
first->next = first->rand = NULL;
list_item* copied;
deep_copy(first, copied);
cout << "test 1 - copy single element with rand=null: " << (copied->next == NULL) << " " << (copied->rand == NULL) << endl;
delete_list(first);
delete_list(copied);
// test 2 - copy single element with rand=self
first = new list_item;
first->next = NULL;
first->rand = first;
deep_copy(first, copied);
cout << "test 2 - copy single element with rand=self: " << (copied->next == NULL) << " " << (copied->rand == copied) << endl;
delete_list(first);
delete_list(copied);
// test 3 - copy two elements with mutually referencing rand's
first = new list_item;
list_item* second = new list_item;
first->next = first->rand = second;
second->next = NULL;
second->rand = first;
deep_copy(first, copied);
cout << "test 3 - copy two elements with mutually referencing rand's: " <<
(copied->rand == copied->next) << " " <<
(copied->next->next == NULL) << " " <<
(copied->next->rand == copied) << " " << endl;
delete_list(first);
delete_list(copied);
getchar();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.