CODEWITHSUNDEEP
c++
Surya
Surya

Reputation: 153

Implementing nested linked lists (list of lists)

My linked list is about a video store . I should make a list with video details ( I know this part) and a list of customer details. Now the CUSTOMER list (The second nodetype) is where my problem lies.

I have to display the customer's name ,acc no. etc AND the videos checked in and out by that customer (deleting and inserting videos to the customer list) So my doubt is ,how do i do this deletion and insertion of JUST videos under a single person s name..

EG: Customer list has lots of different customers with different names and acc numbers and rented videos.

One customer john rents 2 or 4 different videos and rented out some videos too.

now HOW do I show that ONLY John rented these videos (that is i ve to insert videos under his name only and not any other customer)

I hope now people got me...I want to know how this can be done?

Upvotes: 0

Views: 2966

Answers (4)

Carlos
Carlos

Reputation: 200

The customer node needs its own video list. Do this by adding a pointer to a video node as your customer node data member.

Now write a recursive procedure that takes the search term you want to use and a pointer to a customer node. It should return the customer node if it finds it. i.e.:

// New method to find the right node.
CustomerNode* find_customer( string name, CustomerNode* p_node ) {

Add a member method to the customer node that walks to the end of that customer's video list, and puts the new video at the end (alternatively, make the new video the head and append the current list to it)

// New method to add a video to the customer
void CustomerNode::add_video( VideoNode* p_video ) {

You would then use it like this in your code:

   CustomerNode* p_john = find_customer( "John", customers_head );
   if ( p_john != NULL )
      p_john->add_video( p_new_video );

Upvotes: 0

André Caron
André Caron

Reputation: 45274

If I understand correctly, this is a design question, and has nothing to do with linked lists in C++.

For the rest of the implementation, I assume the following:

  1. There are N videos.
  2. The are currently K rentals, where 0 <= K <= N.
  3. There are M customers. There is no relationship between N and M, but it would be safe to assume that there may be many more customers than videos and that most of the time, most of the videos are not rented (M much larger than N, which is much larger than K).
  4. You're starting, so you don't know about classes, std::string or std::list.

  5. You have the following struct/classes.

    struct Customer { int account_number; char * name; // ... other customer info ... };

    struct Video { char * title; // ... other video info ... };

Solution 1: per-customer list of rentals

Add a "list of rentals" your Customer class. This is convenient for listing rentals by customer, but is problematic when you need to validate that a video is not already rented. The first is constant-time, but the second is linear in M+K (loop over all customers, then each customer's rentals).

#define MAX_RENTALS 5
struct Customer {
    // regular fields, see above.
    // ...
    Video rentals[MAX_RENTALS];
    int rental_count;
};

Solution 2: per-video pointer to customer

Add a "point to customer" in your Video class. Checking if a video is not already rented is constant time (check if video->customer is set to some non-default value -- NULL in C, null in Java, None in Python, etc.), but listing movies rented by a specific customer is linear in N.

struct Video {
    // regular fields, see above.
    // ...
    Customer * rented_to;
};

Solution 3: list of rentals

Add a 3rd list to track rentals separately. Define a Rental class that has a pointer to Customer and a pointer to Video. Then, define a list of rentals. Listing all rentals by a customer and checking if a video is already rented are both linear in K.

#define MAX_RENTALS 100
struct Rental {
    Video * video;
    Customer * customer;
};
Rental rentals[MAX_RENTALS];
int rental_count = 0;

This solution gives you the best algorithmic complexity and also happens to mimic more closely what you'd do with an SQL database in a real commercial application for tracking a video store's customers, videos and rentals.

Upvotes: 2

bits
bits

Reputation: 8340

Keep a list of Video pointers in the Customer class.

As soon as a Video is rented out by a customer, append the pointer to that video in that list I mentioned above. Also Keep a single pointer of Customer type in the Video class so that you can look up from video lists about who rented it.

Upvotes: 0

Ben Voigt
Ben Voigt

Reputation: 283793

Put the head of your second list inside the structure which is the contents of your first list. Not a global variable.

Upvotes: 0

Related Questions