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)\$.