Given the following definition for a singly-linked list class, and assuming the createNode method has already been implemented, write an implementation for the InsertAtPosition method.

class LinkedList {
   private:
       struct ListNode {
          string key;
          ListNode *next, *prev;
       };

       // pointer to the front node of the list,
       //    null if the list is empty
       ListNode *front;

   public:
       LinkedList();  // initialize an empty list
       ~LinkedList(); // deallocate all ListNodes
       void print();  // print the list contents

       // allocate a ListNode, initialize its key with k
       ListNode* createNode(string k); 

       // insert k in the i'th position of the list,
       //    0 or negative values mean insert at the front,
       //    1 means insert after the first element,
       //    2 means insert after the second element, etc
       // insert at the end of the list if i is greater
       //    than or equal to the current size of the list
       void InsertAtPosition(int i, string k);

Sample solution
void LinkedList::InsertAtPosition(int i, string k)
{
   // try to create the node to insert
   ListNode *n = new ListNode;
   if (!n) return;
   n->key = k;
   n->next = NULL;
   n->prev = NULL;

   // determine if the node should be inserted at the front
   if ((front == NULL) || (i < 1)) {
      n->next = front;
      if (front != NULL) front->prev = n;
      front = n;
      return;
   }

   // otherwise scan through the list to the position
   //    before the insert point
   ListNode *curr = front;
   int count = 0;
   while ((curr->next != NULL) && (count < i)) {
      curr = curr->next;
      count++;
   }
   // new item goes after curr
   n->prev = curr;
   n->next = curr->next;
   if (curr->next) curr->next->prev = n;
   curr->next = n;
}