A person one year into the industry (comp sc degree and all) recently tried to reverse a linked list by copying the contents from one node to another. While I do admire the ingenuity in thinking to go against the conventional wisdom of thought, i felt that a certain lack of grasp of the underlying structure was to blame for this excessiveness in thinking.

Link list is one of the most sloppy data structure that can be used for organizing data. But it is one of the most convenient (coz it is sloppy and most dynamic) for re-arranging data.

Data when put in a link list looks something like this

  1. You can insert anything anywhere
  2. You can take out anything from anywhere without disturbing the overall structure (just as messy as before)
  3. You can take one item out and put it anywhere else.
  4. You can always view the top of the shelf as the start and the bottom of the shelf as the start – or vice-versa. Nothing major needs to be done to achieve this exept chaning the direction in which you “traverse”
  5. Any order present in the items inside would be self impossed (eg programmer considers everything on list A as “Things to be done” vs list B “Things already done”.

Compare it with say a vector which might look something like this

However make no mistake. Link lists can be improved in a variety of ingenious ways as no doubt all of us have found out during college years, to catalogue and find the items in it much faster. Their flexbility and removal of all order in ts structure allows creative minds to apply all sorts of ingenuity and bring out grand solutions for specific problems. So to speak, link list is a grand daddy for many super structures available for use (Binary Tree, RB Tree etc)

Computer Science

Once the weak analogy has softened the concept, let me try to address why really the link list is considered in-efficient and sloppy.

Memory Cost aka Latency

Link list concists of independent pieces of memory with links to other pieces, that allows one to JUMP from one piece to another much like a treasure hunt progresses.

Inside the computer memory this would be how the link list is arranged.

But the real memory which is but a collection of circuits on your computers motherboard is shown below. Where in it do you think are the addresses 10, 15 200 and 4000 going to be at?

These addresses will be mapped to some RANDOM position inside the physical memory, and would be in most likely situation be places quite far apart in different pieces of the memory circuits.

Memory is slow

The modern processors work at 3 Ghz and the best server memory modules (PC memory might be faster) can work at 800 Mhz or so. The processor would have to wait for a long time if it where to fetch the contents of the memory for every instruction it operates on. This would have effectively brought back the speed of your processor to the 800 Mhz Pentium III era.

Therefore jumping around in memory is physcally or rather computationally extremely costly. (note that there are caches that sits in between the CPU and memory in the hope of reducing cost. This doesnt help us either, unless the data that we required are situated close to each other)

Implications of memory latency for link list

  1. Traversing the link list,  JUMPING from one item to another is expensive (memory wise ie latency wise ie slow)
  2. However re-arranging items is easy – all you have to do is change one link to point to another.
  3. There is extreme flexibility in adding items to the list as you do not need contigous area in memory to store the data. All you require are bits and pieces that can be used to fit things in.

Code

Here is a piece of code to perform a doubly link list (nodes have pointers to previous node as well as the next for obvious flexibility reasons in traversal) reversal in C.


void ReverseDoublyLinkedList(Node* & phead)
   {
   Node * pNode = NULL;

      if (!phead)
          {
          printf( "Bad head pointer");
          return;
          }

     pNode  = pHead;

    while (pTemp = pNode -> pNext)
          {
         /* switch the previous and the next */
          pNode -> pNext     = pNode -> pPrevious;
          pNode -> pPrevious = pTemp;

          pPrevNode = pNode;
          pNode        = pTemp;
          }

   /* Handle the switching of the last node too */
    pNode -> pNext     = pNode -> pPrevious;
    pNode -> pPrevious = NULL;

    /* Change the head node such that the end becomes the new head */
    pHead = pNode;   

    return;
    }

ps : If you are curious about what the impressive looking equipment from the second picture is, they are a set of micro phones using in this MIT project

Advertisements