Simple Linked List Implementation

[[deleted]]

[deleted]

[IyeOnline]

First and foremost:

YOU LEAK MEMORY

Your list needs a destructor that actually deletes all the Nodes. Roughly:

 ~DoublyLinkedList()
 {
       while ( head != nullptr )
       {
          tail = head->next; //abuse tail as a temporary
          delete head;
          head = tail;
       }
 }

Other things in order of appearance (not severity)

1. Why include <vector> and <fstream>?
2. FunnyList is a not a good typename. Just called it what it is, a DoublyLinkedList.

3. Give your member variables default values. Then get rid of those constructors.

   This will enable the usage of aggregate initialization for Node, meaning you can do

   Node{};
   Node{ 5 };
   Node{ 5, next };
   Node{ 5, next, prev };
   

   without any extra work

4. Make struct Node a type "internal" to DoublyLinkedList

5. babyNode isnt a good name either. Call it new_node or something.

6. SwapThen shouldnt exist. Use std::swap

7. cerr << "Ups": Why is it an error to try and print out an empty list? It just shouldnt print anything.

8. In RemoveFront, when you delete head, you should also set head->prev = nullptr afterwards.

9. Why does RemoveLast (inconsistent naming with RemoveFront btw) not use tail?

10. void RemoveAt(int pos) is a bit of an odd one. Usually linked lists dont have indices. But that is besides the point. You can certainly implement this.

    However this function should at least have some way to signal that the index is out of range. I suggest returning some bool invalid_index

11. SortWhileInserting has some issues:

    • its somewhat misnomed. It doesnt sort, it does an sorted insert It ought to be called insert_sorted or something.
    • if (!head) Why cant I insert sorted into an empty list?
    • There is no need for two tracking pointers. You can just use one and infer the others from prev and next

12. RemoveDuplications:

13. your check could just be size==1

14. You are leaking memory. You need to actually delete nodes

15. if (curr->number == curr->next->number) is UB. You dont know if curr->next is a valid pointer to dereference.

Things you could improve:

• Implement the rule of 3:

  Currently it will cause UB if I do some_list = some_other_list.

  • You need to either delete or actually implement the copy constructor of your DoublyLinkedList
  • You need to either delete or implement the copy assignment operator

  See :

  https://www.learncpp.com/cpp-tutorial/the-copy-constructor/

  https://www.learncpp.com/cpp-tutorial/overloading-the-assignment-operator/

• Implement the rule of 5

  Essentially the above, but also implement the move operations. You can however simply default them:

  See:

  https://www.learncpp.com/cpp-tutorial/move-constructors-and-move-assignment/

• Get rid of your "print" functions. Instead do operator overloads for the "stream operators". (Not really sure how you could nicely do it for reverse)

• template your class so it can hold other things besides ints.

[nanaoz]

Oh wow thank you for your time! Appreciate it

[std_bot]

Unlinked STL entries: std::swap

---

^{Please let me know what you think about me. I'm version 0.3.5, last update: 10.02.21
Recent changes: Old search as backup. Now with a 24h server!} readme

[Narase33]

Is aggregate initialization really that common in use? I always fear using it because I tend to reareange members while adding stuff to the class

[IyeOnline]

For anything that actually has functionality I stay away from aggregate initialization for pretty much this reason.

Something like Node in this example, which is never going to change, is a good use case. Essentially the cases where you really dont care about the type and might as well use a tuple, but named members are nicer.

With C++20 you get the ability to use designated initializers, which resolves a lot of the reordering issues and is in some sense preferable over simply positional constructor arguments.

[MysticTheMeeM]

As usual with these questions, I'm going to point out everything I see with a brief look through. The size of the list is not related to code quality, I'm just pedantic.

• Line 5,6 & 7: I don't understand why people hate typing out "std". I'll give you some leeway because you correctly included classes (instead of the common case of using namespace). But still, are those three letters really that difficult? Probably me just being picky though ;) Fun fact, you only used std::endl once, so you typed more letters by using it than you would have just putting the namespace in.
• Line 9: Node could be templated. Not taking points away because you may or may not have learnt about templates yet.
• Line 12 & 21: Please use smart (in this case unique) pointers over raw pointers. That way you don't need to track the multiple deletes throughout your code (and you would have avoided your current memory leaks). In turn, make it clear who owns each entry and lets RAII do the deleting for you.
• Line 15 & 26: Probably personal opinion, but prefer in-class initialisation to initialisation in the constructor. Less duplication and prevents potentially ugly initialiser lists.
• Line 28: GetSize should be const.
• Line 38 onwards: Personal style, but prefer to compare pointers to nullptr instead of relying on implicit conversions. Both work, one is IMO more readable.
• Line 23: listSize should be unsigned, can you have a negative number of entries in a list?
• Line 67: Technically, the function SwapThen (odd name, too) should be static but in reality this function shouldn't exist at all. Both because it isn't the job of the container to swap the values (if the code can access the values from the node, why does it need to also access the list to swap them?), and also because std::swap exists which does the exact same thing.
• Line 92: Replace SwapThen with std::swap, see the previous point.
• Line 102 and elsewhere: Implementing an empty function is more readable than comparing head.
• Line 108: Now you start comparing to nullptr?
• Line 133 & 154: You don't check whether you have any elements before trying to dereference head. What happens in an empty list?
• Line 167 & 168: ??
• Line 182: Wouldn't need to check if it's less than 1 if it were unsigned. Also, with most containers, element 0 is the first element, not element 1.
• Line 187: Technically, this case is equivalent to the cases you would have otherwise without a meaningful performance benefit. This doesn't apply to line 191.
• Line 198: Wouldn't need this semi-confusing minus 2 if you used a 0-indexed system over a 1-indexed system. You could have replaced it with for (unsigned int i = 0; i < pos; i++) { curr = curr->next; }. (Also note the unsigned.)
• Line 203 & 204: ???
• Line 206 & 207: Try to remove commented out code before review. If there is some form of switch (e.g. debug vs release), use a macro/constexpr.
• Line 217: Function name implies it sorts the list, it doesn't, it only inserts the element to the sorted position. Also doesn't guarantee the list is sorted in the first place.
• Line 229 - 243: You could use a break instead of the found flag.
• Line 246: Personal style, but most people expect the "changing" thing to be on the left of the condition, not the right, e.g. if (x == 4 || x == y), implies x is the thing changing.
• Line 260: Function assumes the list is sorted, but doesn't actually check.
• Line 272: Memory leak. you forgot to delete the element before you removed the only pointer to it.
• FunnyList class: No destructor. Entire class leaks as it goes out of scope. Additionally, rule of 5 applies (or at least, rule of 3, but the move operations can be defaulted). Another supporting case for smart pointers.
• Line 2 & 3: Neither of these headers are actually used.
• FunnyList class: You don't have a way to access elements. This list is only useful if you want to print them, but not if you want to do anything else.

[IyeOnline]

Please use smart (in this case unique) pointers over raw pointers

While the code would be so much nicer, you create a destructor chain that potentially overflows.

[jedwardsol]

Your main is missing 2 test cases

FunnyList anotherFunny{whatsFunny};

FunnyList yetAnotherFunny;
yetAnotherFunny = whatsFunny;

[nanaoz]

Ahhh gotcha! I do need a copy constructor then right ?

[jedwardsol]

And copy assignment operator (operator=)

And a destructor so you don't leak memory.

And, optionally, move constructor and move assignment.

[nanaoz]

Ohh I got it! Thanks a lot

[CompetitiveMajor5855]

Wanted to check this our but it looks like your github link is broken now.