Record transaction log

Question

I am trying to resolve following problem to improve my DS knowledge. Please advice which part of the code can be improved.

You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API:

record(order_id): adds the order_id to the log get_last(i): gets the ith last element from the log. i is guaranteed to be smaller than or equal to N. You should be as efficient with time and space as possible.

Code explanation:

I choose linked list with single pointer (prev) to keep transaction logs. I suppose it would be called Stack Linked List.

stProduct -> linked list node

stProdStack -> struct to keep database information, namely ll tail and size (N)

record() examines db information struct tail pointer and order_id within range, then calls actual method to add node to the list: add_product().

I did not implement unit testing due to limited time to seat on.

PARDON MY ENGLISH xD

Code:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//backward/stack linked list for storing transaction action log
typedef struct stProduct
{
 struct stProduct * prev;
 unsigned int order_id;
}
stProduct;
typedef struct stProdStack
{
 struct stProduct * tail;
 unsigned int size;
}
stProdStack;
stProduct* add_product(stProduct *tail, unsigned int order_id)
{
 stProduct *product = malloc(sizeof *product);
 if (!product) return NULL;
 product->order_id = order_id;
 product->prev = tail;
 return product;
}
bool record(stProdStack *stListInfo, unsigned int order_id)
{
 if (!stListInfo)
 return false;
 stProduct *tail = add_product(stListInfo->tail, order_id);
 if (tail)
 {
 stListInfo->tail = tail;
 return true;
 }
 else
 {
 return false;
 }
}
unsigned int get_last(const stProdStack *stListInfo, unsigned int i)
{
 if (!stListInfo) return 0;
 if (i > stListInfo->size) return 0;
 stProduct *current = stListInfo->tail;
 for (int j = 0; j < i - 1; j++)
 {
 current = current->prev;
 }
 return current->order_id;
}
int main(void)
{
 unsigned int N = 100;
 stProdStack product_stack = { NULL, N };
 for (unsigned int i = 0; i < 300; i++)
 {
 if (!record(&product_stack, 1000 + i))
 {
 printf("transaction log record failed\n");
 break;
 }
 }
 printf("10th last product ID: %u\n", get_last(&product_stack, 10));
}

Result: 10th last product ID: 1290

Answer 1

• The code doesn't fulfill the requirements. You are supposed to log the last N orders. Instead you log all of them. The old orders shall be removed from the list as it grows beyond N.

• Bug. The list is initialized with the size being set to N. However, at the beginning it may contain less than N elements. In the scenario

   List is empty
   An order is added
   get_last(2) is called
  

  the loop

   for (int j = 0; j < i - 1; j++)
   {
   current = current->prev;
   }
  

  is guaranteed to access a null pointer.

• The above loop complexity is \$O(N)\$.

All that said, I recommend to use not a list, but a circular buffer. No need to malloc anything, and get_last is executed in \$O(1)\$.