One Directional Bi Linked List
home top contents previous up next

There are following scenarios possible when cloning linked list of size L.

1. Cloning with data and not.

We consider a latter: data are not copied.

2. List occupies sequential area in memory (2.1) or random (2.2).

2.1.1. Top and size of sequential area are known.
   In this case, cloning is trivial, linear by time by list size and takes not additional memory.
   Algorithm: scan area and convert pointers.
2.1.2. Top and size of sequential area are not known.
   Algorithm: start from entry node.
              set two memory areas "up" and "down".
              items with addresses below(above) entry node address put to down(up) branch.
              fill the gabs with items with null pointers.
              always remember two extreme addresses in up and down branch
              scan original gabs, convert pointers, keep updating extreme addresses
              continue until process ends.

              elapsed time t=N*Ct+N*Cn, 
                where N processed nodes,
                Ct - time to convert pointers for each node, 
                Cn to set a node with null pointers.
2.2 Random.
    There is no way to know addresses of items except to traverse an entire tree.
2.2.1 One directional (possibly multilinked) list.

    A. There can be one order-branch (call it "next-branch") which covers an entire tree.
       It will be sufficient to traverse this branch.

    B. If no such branch, there are two problems:
       a. we have to make back trips. In other words, have to memorize paths.
          Can be done with function recursion or arrays which requires stack memory in worse
          case proportional to L.
       b. we have to memorize all traversed nodes, in order to not duplicated them.
          This requires additional L-size space.
2.2.2 Bidirectinal lists.
    We don't need a stack. But apparently, still need L-memory if no "next-branch".

Copyright (C) 2009 Konstantin Kirillov