Clone a doubly linked list efficiently

Posted: June 15, 2010 in algorithms, data structures, programming
Tags: ,

Consider a doubly linked list whose structure of the node looks like this:


struct node
{
 struct node *arbitrary; /* can point to any node, including self or NULL */
 int data;
 struct node *next;      /* always points to the next node */
};

The next pointer points to its immediate next node, unless it is the last node, which obviously points to NULL. The arbitrary node can point to any other node in the list, including itself or NULL. We need to create a clone of the original doubly linked list – this will mean, the clone should preserve the structure / connectivity of the original, as well as the data.

Upon trying to understand the problem and to start thinking about the solution, we might initially feel an O(n) solution is not possible, or we might need to use a Hash data structure, and all such strange thoughts. The arbitrary field of first node can point to last node, the last node’s arbitrary can point to second node. How to bookkeep such information? The length of the list can be thousand or million or more.

So, this problem need to be solved without using temporary variables / arrays, and should run in time polynomial to length of list, ie. with space complexity O(1) and time complexity O(n).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s