Hello friends. I am writing a program for valet parking using Linked Lists. I am able to add the cars for parking. But when I am unparking or exiting cars, that cars aren’t getting deleted even though it shows the correct length. I check in console, it shows correct length but also shows all the cars. Please tell me how do I delete those cars?Here is the working codepen. Besides, I also want to know if this is the right way or the right data structure for this problem. And what if there is a limit on the parking size like only 4 spaces. Can I still use the Linked Lists. Kindly help me with your suggestions. Thank you!
Here is the code for exitCar.
I don’t think it is. Linked lists are great for when you want to add something to a collection dynamically and then remove the first or last item easily. You don’t want to have to iterate through the entire list just to find a particular car, you’d just use valetParking.pop() and remove the car at the top of the list without specifying a name. So, if cars can only leave in the order that they arrive, a linked list would be OK. A binary search tree would be better, but a hash map - JavaScript object or ES6 map - is the optimal data structure.
BUT
I don’t think the goal here is using an optimal data structure. It’s just learning. Since you can’t implement hash maps yourself if JavaScript, I’d suggest trying this with a binary search tree. Don’t abandon your linked list, though. If you can finish it up, then you’d be able to compare performance between the LL and BST. What better way to spend a Saturday?
This doesn’t make any sense. Your while loop does what you need, so why do you wrap it in the if statement?
while(currentCar && currentCar.carNumber !== carNumber) {//make sure you check for null!
previousCar = currentCar;
currentCar = currentCar.next;
}
// after the loop, you either have the car you're looking for, or it doesn't exist
Think about what you want to have happen when the desired car is found. Do you want to return the car after you’ve found it? What does it mean to remove an item from a linked list, and what do you need to do to keep all other link references intact? How can you ensure that this.parkLength gets decremented if and only if you remove a car from the list?
Don’t you think this wouldn’t be a Linked List but a Stack DS?
How can a BST would be better for this as it uses Binary Search Algorithm to find the required value. So using Binary Search algorithm to search the car would be a bad idea. Actually I thought Hash Tables would be a better idea but then Hash Tables has the problem of “Collisions”, as in real world there can’t be 2 cars parked at the same parking spot or space. So I dropped it. So I stuck with Linked list. But your argument of iterating through the entire list just to find a particular car is absolutely right. This makes me to think now more and more besides adding more confusions. but when discussed it could clear a lot of concepts too.
And also there is a difference between my if statement and a while loop. if statement is for, when it is for first car in the list. If it is for other cars in the list then I use a while loop to iterate through the list and find the required car.
By delete I meant returning the car to the owner or exiting from the parking space. So it obviously has to move out from the list right. So I said delete. And yes ensuring this.parkLength gets decremented only when a car is removed from the list is a challenge. Would appreciate if you could throw some light on this.
Lastly, I am a beginner and looking to learn these DS and algorithms. So let me know what is the right way to solve this problem efficiently. Thank you!
It’s not optimal, but it’s not “bad” - certainly not as bad as the linear search you’re already performing. What would lead you to believe this?
Hash collisions are extremely unlikely for the scope you’re describing. In the real world, you wouldn’t just be entering the car’s make, model, or color, but some unique identifier like a license plate or VIN. You also wouldn’t be storing more than a few hundred cars at once.
I understand your reasoning behind it, but think through the logic and you’ll see that the while loop is all you need.
The efficient solution is the one with constant time access - a hash table. These are implemented in JavaScript for you. You don’t want to make a linked list because it’s the most efficient solution to this problem, you want to learn how to make a linked list. So, you need to think a bit more about the implementation.
What does that mean? I’m not asking because I don’t know, I’m asking because you can’t complete your linked list until you know.
I think what you’re doing is great and that you’re on the right track, but I’m not giving you any answers. Think your code through. Talk to a rubber duck. You can do this.
Ok in this case then how would I apply a Binary Search algorithm to find a car? All I know is to search a number using BS algorithm. Perhaps there are ways to apply this in real world problems rather than just finding numbers and I am not aware of it.
Oh yes I so want to implement this problem using Hash Tables using car number as key. Besides, parking has a fixed size and it makes more sense to use a hash table now. Thanks for the hint. Will try it.
Ah ok got it. Yes you’re right.
Thank you for the suggestion mate. I didn’t know about rubber duck.
You can do a binary search on anything that can be sorted. Here’s an example of the logic used to sort strings. Think about how you can apply this to a binary search algorithm.
