How to Create an Instant Copy of a Linked List
Linked lists are data structures that are dynamically created while a computer is running. This means memory was not allocated before the program started, and the program created the structure as it was needed. Often you will need to create a copy of a linked list to work with on a particular problem without destroying the original. The following procedure should only be attempted by those with experience in computer data structures.
Other People Are Reading
Instructions
-
-
1
Request a new pointer to start building your instant copy. Pointers are words in memory that are just big enough to contain memory addresses. Make the new pointer the entry point to your instant copy, no matter the structure of the linked list you are copying. Once you have the starting pointer, you will go through the linked list making an instant copy of everything that is encountered.
-
2
Link the nodes of your instant copy by having the pointers in one node contain the address of the next node in the list. Put the data that goes in the linked list in the nodes. For example, in a database at the IRS, the nodes might contain records of citizens, with one record for each citizen. Put one or more pointers in each record, such as addresses of other records. Put one pointer in each record if you want the linked lists to be actual lists, queues, or some other sort of linear structure. Put more than one pointer in each record if you are building a tree. Use the layout of the linked list you are copying to make your instant copy.
-
-
3
Request a new address. The method for doing this depends on the language you use. The operating system on you computer supplies new chunks of memory, along with the address of the chunk so it can be referenced. Your new address points to a blank record. Copy the information from the first record in the old linked list into the first record in the new linked list you are making (except for the pointer). When you get to the pointer, request a new pointer and put that in the linked list you are creating. Follow the pointer in the old list. Follow the new pointer to a new blank record and copy the information from record to record as before. Keep doing this until the entire list is copied.
-
1
Tips & Warnings
Write the linked list copying procedure as a function. The input to the function is the address of the linked list you want to copy. The output of the function will be the address of the copy. If you write the function recursively, the function will mostly consist of instructions to copy data from one record to another.
If your linked list is a tree like structure, records might contain more than one pointer. You must make one recursive call for each pointer. This will ensure that the entire tree is copied.
References
Resources
- Photo Credit John Rowley/Digital Vision/Getty Images
