15,999,229 members
See more: , +
I'll try to describe briefly the project I'm working on and then I'll pose my question.

Project:

Suppose you are running an online shop that connects buyers to sellers. So there is a list of ITEMS and a list of BUYERS. When the buyer is satisfied with a product he puts it in the basket and the item is removed from the available items shown to other users.

What can happen: the buyer can quit without going through the checkout so the items he selected (if any) should be available again for other users or the sell can be called off from the seller so the item is not available no more even if it was in someone's basket. Plus I could be asked to print a report of the current situation at a certain time describing for each buyer its basket.

Question: I have a list of actions that take place like "BUYER1 logs-in", "ITEM11 is for sale" or "BUYER13 puts ITEM1 in the basket" (we neglect the checkout) and I was wondering which data structure is more appropriate to handle this specific case, in particular which solution is the best in terms of time and space complexity. I should realize my project in C.

What I have tried:

Don't know if the solutions I came up with are efficient both from the time and space complexity. Could you suggest me a better solution? Thanks a lot in advance to everybody! Any help is appreciated.
Posted
Updated 8-Jul-18 8:49am
nv3 7-Jul-18 17:33pm
This whole scenario is as unrealistic as it can get. In real life, all that would take place in a database, not in in-memory data structures. Hence, the example is a bad one. And a couple of other things are unrealistic as well: You would not remove an item from your inventory until an order has been placed. And of course, you would not organize access to your items in a linear list. This is probably all not your fault, but a somehow misguided course is leading you in this direction. There are better examples for questions regarding data structures and their efficiency.

## Solution 1

I don't think I would use a list; but rather use two arrays (C allows extending an array easily) and a pointer.

One array contains Item records (int index; int available; int inventory; ...). Index is the index of the item within the array. It could also be the record id of an SQL-like record. Available contains the number of items that are on-hand and are available for sale. Inventory is the number of items that are on-hand. Available is always less than or equal to Inventory. (Note that "..." means other members in the record.)

The second array contains Buyer records (int index; string name; Cart *cart; ...). Index is the same as the Item index. Name is the buyer's name. Cart is a pointer to a Cart record.

The Cart record contains three fields (int index; int count; Cart *next; ...). Index is the Item record index of an item to be purchased. Count is the number of items to be purchased. Next is a pointer to the next item in the cart or null if there are no further records in the cart.

The advantage of using arrays is the speed of access and reduced space requirement. The only major cost is adding a new item to the Items array. But this occurs only once and can be accomplished by appending the new Item to the end of the array. Note that only one Buyer needs to exist at one time.

I'd really like to have drawn this solution but I do not know how to provide a drawing in the Solutions section.

Member 13902250 7-Jul-18 12:18pm

## Solution 2

In a real world scenario everybody would run this in a transaction based database. But the problems stays the same: if you change your big data storage on every change you loose.

Best is to NOT manipulate the data storage, but set some fields and flags in a data structure or database. Like is in a basket (id and maybe timeout). And you should also have some cache or additional storage about goods in basket for faster completion of sale or removal.

## Solution 3

Quote:
Lnked lists: how to minimize time and space complexity in a concrete case

As you have already been told, linked list is the wrong tool for this project.
You need to learn about databases, and databases design.

Linked list is in memory, it imply that if the program or server stops, everything is lost. To avoid this problem, for each operation, you have to load the list in memory and save it to file after, but there is nothing to protect from multiuser concurrency.

complexity to search 1 item in list
```Number items        1000   1000000
find an item mean    500    500000
find an item max    1000   1000000

indexed database
find an item mean     10        20
find an item max      10        20```