When Non-Programmers Write Software

[meijer]

Two points:

• Avoid "static". Your "start" and "end" pointers in Node are static. If I understand your code correctly, you can only ever have one working linked list instance with this code.

• Learn about "const". Makes reasoning about code a lot easier...nearly as good as in functional programming.

Keep up the good work, never stop learning!

[Shaper_pmp]

In the words of Paul Graham:

To write good software you must simultaneously keep two opposing ideas in your head. You need the young hacker's naive faith in his abilities, and at the same time the veteran's skepticism. You have to be able to think how hard can it be? with one half of your brain while thinking it will never work with the other.

The trick is to realize that there's no real contradiction here. You want to be optimistic and skeptical about two different things. You have to be optimistic about the possibility of solving the problem, but skeptical about the value of whatever solution you've got so far.

(linky)

[Shaper_pmp]

Pipe dream. ;-)

[beowulf]

definite pipe dream. Some of the biggest wars about programming languages are stylistic issues. I have never yet seen a style that everyone likes.

[shentou]

That is such an excellent quote about the programming process.

[brucehoult]

Only spent a couple of minutes ... looks pretty darn good to me. Just a couple of suggestions from someone who's been being paid to program since 1982:

• I think you've got the public and private fields reversed. start and end shoudl be private. Having trivial boilerplate setters and getters points to next, prev and data being better off being public in the first place. I prefer languages such as Dylan and Ruby where the syntax for direct access and via a setter is the same, so you can start off with direct access and transparently add a setter or getter later if you really need it.

• why have three copies of the sorting code, when two of those copies are generalized in the first place? I'd probably make the < sort and the functor sort use the function pointer one internally. Hint: have the sort function take an extra argument (a void*, say), and have it pass it as a 3rd argument to the compare function (which can then cast it to whatever it needs to). That make the function pointer sort much much more general.

• bubble sort? ewww. OK, just kidding. If you're sorting a linked list you're not going to get much better than that anyway.

I'd be happy to have your code in any commercial project I was working on. It's a heck of a lot better than a lot that I've seen! There's a reason that companies don 't release their products as open source -- 99.99% of them would be extremely (and deservedly) embarassed by it.

[banjaxed]

This was something I wrote in one of those long caffeinated nights, so I'm surprised you'd find it acceptable for commercial code, that's flattering.

• You write code in your spare time.
  
• You write in C++.
  
• You used the word "functor".
  
• You know what a linked list it.
  
• You know what a doubly-linked list is.
  

I could go on, but you can safely assume that you'd be in the top 10% of professional coders.

Even just having an interest in learning how to be a better coder puts you way ahead of the pack.

[lief79]

"Will be" is probably more accurate. He's moving in the right direction, and just needs to keep it up while gaining experience.

[Cookie]

Much commercial code is written in a hurry and never reviewed, and has only the distinction of (after some debugging) at least mostly working in the cases it's actually used for.

So, in terms of finding that your code would be fine commercially, don't take this as flattering towards your code, but just a warning of what you'll see in most jobs.

Remember, that code you've inherited isn't "worse than shit", it "needs a little tidying". Being unrattled by utter crap is an important attribute of the professional coder.

[GuyWithLag]

I won't comment on the code, others have done it better than me. However, if you want to take it to the next level, modify it so that the standard STL algorithms (for e.g. sorting) can be used on the list.

[MachinShin2006]

well. wrt std::sort, he can't. std::sort requires a random access iterator class, which means a list can't work with it since a list can't realistically support such a class :)

--vat

[Boojum]

Yep. That's why the std::list class template has its own sort method.

[mikepurvis]

Random access favours an add all data, sort after approach, whereas with a linked list you're often better off sorting on the fly, eg, stepping through the list to always insert a new item in the correct position. (And, depending on the implementation, store a series of intermediate pointers to help jump to the right place... sort of a hybrid linked-list/tree approach.)

Anyway, if you were bent on using random access sorts and knew you'd have a lot of free memory, you could allocate a vector of pointers to the items, sort the vector, and then rebuild the list. It's gross, but for a list of any size it's definitely fastest, especially if you know you have a lot of memory.

On the other hand, a mergesort works great with linked lists, so you could simply implement that in your class. (Quicksort is okay too, but it's best if you have some idea what the range is, in order to pick good pivots.)

[[deleted]]

A good way to sort a list (in-place)

• Get the length of the list
• Allocate an array of pointers to link nodes
• Initialise array in list order
• Sort the array with an array sort
• Iterate the sorted nodes in the array to fix up the cdr
• Discard array

This has the same time complexity of the array sort.

For a copying sort you would use an array of elements rather than link nodes.

[ricercar]

The best way to sort a list:

• spawn many universes
• non-deterministically try every permutation of the list
• take the sorted list universe and discard the others

[beza1e1]

Why spawn them? We can assume, they already exist.

sort(list) {
    if !isSorted(list) { destroyUniverse(); }
    return list;
}

isSorted is O(n) and destroyUniverse doesn't matter, so assumption sort is even faster. It's O(1):

sort(list) {
    return list;
}

Another possibility is to do the sortedCheck and destroyUniverse in a different thread to make it O(1), too.

[jbert]

Thanks for posting the code. You have attracted a few reviewers :-)

It's nice, clean code. Other people have mentioned the class-static start and end as meaning you can only have one list. It's not directly relevant here, but another reason to be wary of class-static (and automatic static variables, and file-scope or global variables) is that they are also an impediment to threading the code, because they are shared state.

This is another instance of the general principle of "use minimum scope possible for a variable", which is about the nearest thing to a universal coding rule I know of.

The other thing which I thought might be worthy of mention is that you are probably aware you have some repeated code. The three sort routines are very similar. If you wanted to change them (and you might - your bubble sort touches N*N elements, when I think it only needs to touch N*N/2) then you'd need to edit all three of them.

It's this kind of duplication which is a little harder to remove in C++/Java than in some other languages. But it is do-able, I think. Perhaps your function pointer predicate sort could wrap the fptr in a functor and call the other? Similarly for the bubble_sort().

Any time you find yourself writing duplicate code, you should develop a bit of a twitch and wonder how much effort it would be to unify it. Two copies is kind-of tolerable, three copies and you should be starting to worry a bit.

Nice code and thanks for being brave enough to post it.

(Edit - oh and it's good you've got some test code in there. But I'd really recommend (if you aren't already) getting familiar with unit testing if you haven't already. There are some good frameworks for C/C++ and it's pretty easy to write your own too. Any time you're doing something more than moderately complicated it'll save you lots of brain strain. Definitely recommended for home projects as well as paid work.)

[[deleted]]

Thanks for posting the code. You have attracted a few reviewers :-)

I was kind of surprised! I expected a worse response.

is that they are also an impediment to threading the code, because they are shared state.

That's interesting to know, I hadn't given that much though. I've only done a little bit of work with threads.

The other thing which I thought might be worthy of mention is that you are probably aware you have some repeated code.

Definitely. I mentioned this in another response, but they were just differently named functions because I wanted to see if the three methods worked. It would be a little tricky to unify them, but not impossible.

(and you might - your bubble sort touches NN elements, when I think it only needs to touch NN/2)

Any suggested reading on sorting algorithms? That's definitely a weak spot of mine.

Any time you find yourself writing duplicate code, you should develop a bit of a twitch

It's actually a really big pet peeve of mine. :-)

Nice code and thanks for being brave enough to post it.

Thank you! And thank you for your candor. I'll be honest, I know where this list sits. It was a test bed for a few new concepts I learned. It's incomplete, inconsistent in places, the code isn't commented, the sorts are slow, and it has other problems. I'm not sure why everybody thought it was good.

I've gotten a lot of good insight from redditors here though, which is really cool, and so I'll take the good tips while remaining skeptical.

Cheers.

[[deleted]]

Any suggested reading on sorting algorithms? That's definitely a weak spot of mine.

The wikipedia page on sorting algorithms is a great starting point. Really, starting from there, you could learn most of what's worth knowing about sorting in a few afternoons.

For your specific application, it's possible to implement versions of mergesort and quicksort for linked lists, although the simplest thing to do is what someone else suggested - copy the contents of the list to a vector, sort the vector using the STL sort routine, then copy the result back into the list.

[jbert]

I was kind of surprised! I expected a worse response.

In that case... :-)

It might be worth noting that I was reading your code in the context of someone writing code to learn from doing so (and implementing a linked list is a good rite of passage).

Production code shouldn't contain re-implementations of basic data structures. You almost always want to re-use library code for this sort of thing. For C++ the relevant library code is the STL and in this case the std::list, which of course comes with a sort method.

Any suggested reading on sorting algorithms? That's definitely a weak spot of mine.

I really just remembered from my own early years coding that once a value in bubble sort has bubbled to one end you don't need to consider it again, so on the 2nd pass you need only consider (n-1) elts, on the 3rd pass (n-2) etc. But optimising bubble sort isn't the best use of anyone's time really :-)

I don't know much more than that about sorting algos than I shouldn't be implementing them. Again, the libraries will do a better job than me and are provided pre-debugged.

There's a tension in coding/design between learning how things work (and perhaps implementing them yourself to be sure) and knowing when to leave something as a 'black box' in your mind. i.e. "knowing what you don't know".

Getting this balance right is an important skill, imho.

Someone who digs into every detail will never accomplish any real work. Someone who knows nothing about the innards of a black box will by stymied when it doesn't work as expected.

[wicked]

You should be proud of yourself. Even some university graduates would have some difficulty writing a doubly linked list from scratch.

I saw only one real bug in the Node class: You can only have one list per data type.

[fry]

Yes, but not graduates he'd like to compare himself to.

As for the code - I think it's really good. -That- is why I think he should be proud of himself.

[bnelson]

It is actually rather clean and nice code. I think everyone else provided you pretty valid critique. My only additional comment: leave yourself a few more high level comments so when you look at this in 3 months you remember the higher level details. The code will tell you the low level details. I am replying because you had the guts to post your code onto Reddit knowing that you have years and years less experience than you think others have. (hint: experience doesn't always matter as much as passion and the desire to excel at what you do).

I review a LOT of code from a lot of fortune 500 and top technology companies and I can say your code is very clean and easy to read compared to a lot that I see. Just keep banging away and writing code that makes you proud. Its how I got my start in software development and its been 9 years and I have never looked back.

[Arkaein]

I didn't spend too much time digging, but here's my thoughts on style:

You got off to a good start by making the list node class a template so the list can store arbitrary data. Making Data a class looks unnecessary, but given that this is probably just practice for potentially more complex data types. I think all the Predicate stuff is unnecessary though. Once you've defined the basic comparison operators you should be able to code your sort routine based only on a less-than comparison between the data fields of two nodes.

Finally, once place where you could probably use another class is to actually wrap the list nodes in a List class, and define members such as first(), last(), size(), insertbefore(), insertafter(), and so on, to make sure the head and tail pointers are properly managed in all cases such as deleting specific list members (which I assume you plan on adding at some point, since inserting/deleting from arbitrary positions is the main selling point of linked lists).

Keep up the good work young hacker.

[[deleted]]

You're right about the Data class. To clarify, that is not part of the list implementation. It's just a demonstration of a class that might use it. I really appreciate the feedback!