Necessary and Sufficient

Question: Write a C++ function that makes a deep copy of a linked list.

Answer: This is a good interview question because it examines several concepts: pointer operations, pass by reference, and stack vs heap allocation. To answer the question you need to first understand the different between deep and shallow copies.

In a deep copy, sometimes refered to as memberwise copy, the copy operation respects object semantics. That means that if the object being copied has pointers/references to other objects those objects need to be duplicated, rather than just having duplicate pointers/references to the existing dependent objects. In other words, all ties to the existing "parts" are severed.

On the other hand shallow copy, or bitwise copy, does not respect object semantics. It copies all of the objects fields but it does not create new copies of any dependent object. Instead it creates copies of the pointers/references to these dependent objects. For reference types, this is usually not what you want!

So back to our linked list problem... Each node in a linked list is a struct. To make a deep copy of the list we want to duplicate the nodes and create an entirely new linked link that strings them together in the same logical sequence as the original linked list.

Here is some C++ code (lines 27-44) to do the deep copy and also to verify the results by way of a simple count function and walking the list. It is possible to write a recursive copy function but the stack space consumed will be proportional to the length of the input list.

   1:  #include <stdio.h>

   2:  #include <stdafx.h>

   3:  #include <malloc.h>

   4:   

   5:  struct node{

   6:      int data;

   7:      node* next;

   8:  };

   9:   

  10:  void push(node** head, int data){

  11:      node* newNode = new node;    // struct keyword not reqd in C++

  12:      newNode->data = data;

  13:      newNode->next = *head;

  14:      *head = newNode;

  15:  }

  16:   

  17:  int length(node* start){

  18:      int count=0;

  19:      node* current = start;

  20:      while(current != NULL){

  21:          count++;

  22:          current = current->next;

  23:      }

  24:      return count;

  25:  }

  26:   

  27:  node* copy(node* head){

  28:      node* current = head;

  29:      node* newHead = NULL;

  30:      node* newTail = NULL;

  31:   

  32:      while(current != NULL){

  33:          if(newHead == NULL){

  34:              push(&newHead, current->data);

  35:              newTail = newHead;

  36:          }

  37:          else {

  38:              push(&(newTail->next),current->data);

  39:              newTail = newTail->next;

  40:          }

  41:          current = current->next;

  42:      }

  43:      return newHead;

  44:  }

  45:   

  46:  int main(){

  47:      

  48:      node* head2= NULL;    

  49:          

  50:      for(int i=7; i>=1;i--){

  51:          push(&head2, i);

  52:      }

  53:      

  54:      node* head = copy(head2);

  55:   

  56:      int len=length(head);

  57:      printf("Length of list is %d\n",len);

  58:   

  59:      node* current = head;

  60:      while(current != NULL)

  61:      {

  62:          printf("%d ",current->data);

  63:          current = current->next;

  64:      }

  65:  }

Question: Explain the differences between arrays and linked lists.

Answer: There are several differences which all stem from how the 2 data structures allocate memory.

An array is a linear data structure which allocates a contiguous block of memory on the heap returning a pointer to the start of this block (the base address). Because the compiler needs to know how much memory to allocate they are often fixed in size although some languages offer re-sizing functions which results in a new but bigger contiguous block of memory being allocated and the original data being copied to the new block. Arrays offer direct element addressing using the [] operator and this addressing is extremely fast because the program applies a formula as follows (for zero-based arrays):

A linked list is also a linear data structure but it overlays a structure on top of a collection of homogeneous data items. In a singularly-linked list the structure that encompasses each node/element of a linked list has a pointer/reference to the next element in the sequence. In a doubly-linked list there is also a pointer/reference to the previous element in the sequence. In marked contrast to arrays, the structure of linked lists allows a logical ordering of the elements to be defined which is different to the physical ordering. Furthermore, because the elements need not be contiguous in memory linked lists do not need to be fully provisioned up-front and can easily grow dynamically.

The disadvantage of linked lists is that, unlike arrays, you cannot directly address the i-th element. This is because of the non-contiguous use of memory.