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

Question

0.00/5 (No votes)

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:

I came up with two possible solutions: I could store items data in a linked list of structures (with fields like Id, price etc.) named "available items" and store buyers data in a linked list of structures that contains a field named let's say "basket" which is a linked list of items and when a buyers puts a product in the basket the item is removed from the "available items" and appended to the "basket". The issue could be that when a sell is called off I don't know who put the item in the basket so I should go through the list of buyers and for each of them through their basket to delete the product. Or I could add a field to the items struct named let's say "buyerID" where I could change the value from 0 (the item is available) to the ID of the buyer that put the item in the basket but when I have to print a report for each buyer I have to go through the list of items to know what he is buying.

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 7-Jul-18 2:53am

Member 13902250

Updated 8-Jul-18 8:49am

Add a Solution

Comments

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.

3 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

gggustafson · Answer 1 · 2018-07-07T06:07:00

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.

KarstenK · Answer 2 · 2018-07-08T07:54:00

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.

Patrice T · Answer 3 · 2018-07-08T08:49:00

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.

Why linked list is wrong?
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
Linked list
load/save list      1000   1000000
find an item mean    500    500000
find an item max    1000   1000000

indexed database
load/save list        no need
find an item mean     10        20
find an item max      10        20

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

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

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

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us