Skip to main content
Code Review

Return to Answer

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1

Naming

#Naming GenerallyGenerally when I think of a linked list I don't think of a list of links. I think of a list of nodes which are linked to each other (via next and/or previous pointers). For that reason, I wouldn't call your class Link, I'd call it Node. The link in your class is the next pointer.

Do you need setValue?

#Do you need setValue? IsIs there a reason why you need a setValue() method in Link? It's only called from the constructor. You could simply move the code for it into the constructor and get rid of the public function. (If you added a next parameter to the constructor you could make the class immutable which is helpful for multithreading, though it would involve changing some of the logic of updating the list.)

Encapsulation

#Encapsulation II don't generally like friend functions. People will say that operator<<() is always a friend function. But here you're careful to keep the Link parameter const and it only calls the (also const) getValue() method. There's nothing here that requires it be a friend function, so I say get rid of the friend designation. Just make it a free function in the header.

Double-ended Queue

#Double-ended Queue WhatWhat you've created actually has a name other than "linked list". It's often called a double-ended queue or deque for short. They have several useful characteristics such as being O(1) for insertion and deletion at the ends, as you've no doubt discovered. There is a standard container called std::deque that implements this. (Though I realize you tagged this as "reinventing the wheel", which is always good for learning!)

Avoid raw pointers

#Avoid raw pointers II agree with others that you could implement this with a vector or array (or deque) if you wanted to. But whatever you do, you should avoid using raw pointers. They have so many potential pitfalls that they're really not worth it. I recommend using either std::unique_ptr or std::shared_ptr depending on the situation. They help avoid a large class of resource management errors.

Symmetry

#Symmetry YouYou should strive to make the interface for your classes symmetrical to make them easier to use and understand. By that I mean that if you have an insert() method that does one thing, the remove() or delete() method should do the opposite. In LRU you've overridden insert() to do things like increment the max_len counter. But then in access() you have to manually decrement it after calling deleteKey(). You should also override deleteKey() to call the base class and decrement max_len so that someone updating access() doesn't have to know this fact in the future. They can simply call deleteKey() and not worry about it.

#Naming Generally when I think of a linked list I don't think of a list of links. I think of a list of nodes which are linked to each other (via next and/or previous pointers). For that reason, I wouldn't call your class Link, I'd call it Node. The link in your class is the next pointer.

#Do you need setValue? Is there a reason why you need a setValue() method in Link? It's only called from the constructor. You could simply move the code for it into the constructor and get rid of the public function. (If you added a next parameter to the constructor you could make the class immutable which is helpful for multithreading, though it would involve changing some of the logic of updating the list.)

#Encapsulation I don't generally like friend functions. People will say that operator<<() is always a friend function. But here you're careful to keep the Link parameter const and it only calls the (also const) getValue() method. There's nothing here that requires it be a friend function, so I say get rid of the friend designation. Just make it a free function in the header.

#Double-ended Queue What you've created actually has a name other than "linked list". It's often called a double-ended queue or deque for short. They have several useful characteristics such as being O(1) for insertion and deletion at the ends, as you've no doubt discovered. There is a standard container called std::deque that implements this. (Though I realize you tagged this as "reinventing the wheel", which is always good for learning!)

#Avoid raw pointers I agree with others that you could implement this with a vector or array (or deque) if you wanted to. But whatever you do, you should avoid using raw pointers. They have so many potential pitfalls that they're really not worth it. I recommend using either std::unique_ptr or std::shared_ptr depending on the situation. They help avoid a large class of resource management errors.

#Symmetry You should strive to make the interface for your classes symmetrical to make them easier to use and understand. By that I mean that if you have an insert() method that does one thing, the remove() or delete() method should do the opposite. In LRU you've overridden insert() to do things like increment the max_len counter. But then in access() you have to manually decrement it after calling deleteKey(). You should also override deleteKey() to call the base class and decrement max_len so that someone updating access() doesn't have to know this fact in the future. They can simply call deleteKey() and not worry about it.

Naming

Generally when I think of a linked list I don't think of a list of links. I think of a list of nodes which are linked to each other (via next and/or previous pointers). For that reason, I wouldn't call your class Link, I'd call it Node. The link in your class is the next pointer.

Do you need setValue?

Is there a reason why you need a setValue() method in Link? It's only called from the constructor. You could simply move the code for it into the constructor and get rid of the public function. (If you added a next parameter to the constructor you could make the class immutable which is helpful for multithreading, though it would involve changing some of the logic of updating the list.)

Encapsulation

I don't generally like friend functions. People will say that operator<<() is always a friend function. But here you're careful to keep the Link parameter const and it only calls the (also const) getValue() method. There's nothing here that requires it be a friend function, so I say get rid of the friend designation. Just make it a free function in the header.

Double-ended Queue

What you've created actually has a name other than "linked list". It's often called a double-ended queue or deque for short. They have several useful characteristics such as being O(1) for insertion and deletion at the ends, as you've no doubt discovered. There is a standard container called std::deque that implements this. (Though I realize you tagged this as "reinventing the wheel", which is always good for learning!)

Avoid raw pointers

I agree with others that you could implement this with a vector or array (or deque) if you wanted to. But whatever you do, you should avoid using raw pointers. They have so many potential pitfalls that they're really not worth it. I recommend using either std::unique_ptr or std::shared_ptr depending on the situation. They help avoid a large class of resource management errors.

Symmetry

You should strive to make the interface for your classes symmetrical to make them easier to use and understand. By that I mean that if you have an insert() method that does one thing, the remove() or delete() method should do the opposite. In LRU you've overridden insert() to do things like increment the max_len counter. But then in access() you have to manually decrement it after calling deleteKey(). You should also override deleteKey() to call the base class and decrement max_len so that someone updating access() doesn't have to know this fact in the future. They can simply call deleteKey() and not worry about it.

Source Link
user1118321
user1118321
  • 11.8k
  • 1
  • 19
  • 46

This is a really useful thing to implement! Good choice of projects. Here are some thoughts on how you could improve it:

#Naming Generally when I think of a linked list I don't think of a list of links. I think of a list of nodes which are linked to each other (via next and/or previous pointers). For that reason, I wouldn't call your class Link, I'd call it Node. The link in your class is the next pointer.

The distinction between push_back() and insert() is unclear. In the base class there doesn't appear to be a difference as insert() simply calls push_back(). If I make an LRU object and call push_back() what are the consequences? (Or push_front() for that matter?) Perhaps LRU shouldn't make the methods of LinkList public. Also, renaming insert() to add_new_cache_item() would make clear which a caller should be using given a particular use case.

Related method names should follow the same pattern. You have insert() but then its opposite is called deleteKey(). Presumably that's because delete is a keyword so you couldn't call it that. I'd either rename insert() to insertKey() or rename deleteKey() to simply remove().

#Do you need setValue? Is there a reason why you need a setValue() method in Link? It's only called from the constructor. You could simply move the code for it into the constructor and get rid of the public function. (If you added a next parameter to the constructor you could make the class immutable which is helpful for multithreading, though it would involve changing some of the logic of updating the list.)

#Encapsulation I don't generally like friend functions. People will say that operator<<() is always a friend function. But here you're careful to keep the Link parameter const and it only calls the (also const) getValue() method. There's nothing here that requires it be a friend function, so I say get rid of the friend designation. Just make it a free function in the header.

#Double-ended Queue What you've created actually has a name other than "linked list". It's often called a double-ended queue or deque for short. They have several useful characteristics such as being O(1) for insertion and deletion at the ends, as you've no doubt discovered. There is a standard container called std::deque that implements this. (Though I realize you tagged this as "reinventing the wheel", which is always good for learning!)

#Avoid raw pointers I agree with others that you could implement this with a vector or array (or deque) if you wanted to. But whatever you do, you should avoid using raw pointers. They have so many potential pitfalls that they're really not worth it. I recommend using either std::unique_ptr or std::shared_ptr depending on the situation. They help avoid a large class of resource management errors.

#Symmetry You should strive to make the interface for your classes symmetrical to make them easier to use and understand. By that I mean that if you have an insert() method that does one thing, the remove() or delete() method should do the opposite. In LRU you've overridden insert() to do things like increment the max_len counter. But then in access() you have to manually decrement it after calling deleteKey(). You should also override deleteKey() to call the base class and decrement max_len so that someone updating access() doesn't have to know this fact in the future. They can simply call deleteKey() and not worry about it.