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.