Array, Linked List, or Binary Tree?

Alright, I have a program for school that asks that I use arrays, linked lists, and a binary tree. This program is used as a database to hold data for a movie rental store. Of course the store has inventory, employees, and no successful store doesn't have customers as well.

My first attempt at designing a structure for the customers and employees was to use a binary tree. I'd been told that a BST could search through large amounts of data quickly. Then I realized that all of the data access requirements for the customers and employees included having them sorted by an identification number. This would be all well and good except for the fact that each new account would come in already sorted from the lowest number to the highest.

I determined a binary tree to be a very bad idea because it would degrade into an inefficient linked list. I could write balancing routines but that would make for very complex code to fix a problem that could be solved by a different data structure.

I then tried designing for the customers and employees by using a linked list. All in all it worked much better in theory than the tree, and I was saved the problem of complicated code. I remembered reading that it's a good idea to use a linked list when the size of the list changes constantly and you find yourself inserting and deleting data from anywhere not on the end of the list. Another study of my requirements told me that there was not supposed to be an option to insert an account in the middle nor even an option to delete an account at all, just a flag to tell if the account is active.

So I said to myself, since I'm not going to need to deal with the complicated parts of a linked list, that data structure doesn't solve problems I have. It just makes the code more complicated that it could be, and not being very experienced I need my code as simple as possible to get it to work.

My next step was looking at a resizable array. I needn't be bothered with sorting it because the data comes in sorted, so that's always a plus as sorting takes a lot of time. I don't need to insert data in the middle of the array so there's no problem with shuffling an array that causes the choice of a linked list. I don't need to delete any accounts so the array will never shrink and need to be resorted or shufled...so far so good. I don't even have to worry about the extra memory usage of a pointer to the next element in the array, what little they take up anyway, so an array is more memory efficient. From this data structure I couldn't see any downside when designing the code and reading my requirements.

Then came the inventory of the store. This was harder because there is indeed an option to remove a movie. I took it one step further and chose to implement a way to delete one of several of the same movie. If there's more than one I have a counter to determine how many there are and if one is deleted I decrement it until there is only one left in which I delete the node. I thought a linked list would work for this but because this is a school project I felt that I would need to use a binary tree or get a lower grade. I believe that a linked list is far superior in this case because the only time I need to search the structure is to print out every item in it. That's just a traversal and a binary tree doesn't solve any problems here.

My question is this. Am I on the right track so far and can I get away with what I believe is the more efficient and compact program? Or do I need to do it exactly as the requirements ask and create an obviously inferior program due to larger size, greater chances for bugs, worthless and long code that solves problems I don't need to even code, etc...

I'm hoping that if I use a binary tree for the inventory I'll have met the requirements enough to squeak by and still get a perfect score, and maybe some bonus points for coming up with a better way to do it.

I know this isn't the type of question you're used to, but if you can't help me with my second problem, I'd at least like comments on how I'm doing with the structure.

> I have a program for school that asks that I use arrays, linked lists, and a binary tree.
Guess you need to use all three then
My guess is you have to decide which one is best for each of employees, customers and inventory

I have decided which is best, but that leaves out a binary tree. So I'm at the point where I have to choose between a tree and a linked list.

If i understand your post correctly you want to place customers and employee's into an array. Then use either a linked list or binary tree for the inventory.
I am assuming they you are going to have to mark a customers account when they are renting a movie, so you can use a binary search algo on the array,becuase you said it is already sorted, as you read in the data.
My idea for the inventory data base is to have a simple struct

struct InventoryStruct
{
string MovieName;
int TotalCount;
int RentedOut;
};

Make a binary tree to hold the inventory, so you can quickly find movies.

Look closer at the project specifications and see what other functions you have to do on the customers and employees.
Some may be more efficent with a tree or list. You can always go to your teacher before you code this, and ask him how the grading will be done. And explain to him/her what you think will be more efficent.

Hmm, I'm not too sure from your post... if the inventory needs to be sorted, then I do suggest using a binary tree for it. If, however, it is neccisary to remove elements from the tree, then you may either want to use a different structure, or be very careful about how you make your tree.

Here is a suggestion however, you may want to use a binary tree to keep track of your customers by name, while your array can keep track of them by ID#. Since you already have all the customers allocated in memory in the array, you can just use their id numbers as the elements of the tree, instead of having to store all the customer information in the tree as well.

The inventory doesn't need to be sorted, and I will need to delete nodes eventually which will cause problems with searching and rebalancing. I really really really really don't want to write balancing routines, nor do I see any real need for a tree because this program is going to stay small enough for a linear search of a linked list to be efficient enough for my needs. The big question is can I write this without a tree and still get a decent score, because the project says "using arrays, linked lists, and a binary tree".

If I use a tree then that makes for easier searching but if I delete a node from the tree then I have to rebalance it and that's just short of a nightmare at my skill level. So a linked list is really better since this is the last project before I graduate. What I'm going to do is ask my professor if I can write it with just a linked list and dynamic arrays or if I have to have a binary tree. What I'd like to know is which option you guys would take.

Seriously, here's what I suggest...
array for customers and employees
linked list for inventory
binary tree for customers and employess by name

The binary tree will just contain the ID#s, sorted by the name of the customer or employee they refer to (since you have them as an array, the lookup shouldn't be costly). Truth is, if the assignment asks for a binary tree, then you really should go ahead and put it in somewhere, although I doubt that the inventory is the place for it.