Ihad To Write My Own Linked List

Fairly recently, a classmate said IhadToWriteMyOwnLinkedList? with quite a bit of pride. And others near-by nodded in the yup, gotta do it way. The instructor did, too. I was too shocked to do anything but gawk. At another time, I boggled at the idea of starting to write something simple from scratch, preferring to use a library that was close enough to what I needed. The response was amazement that I would waste the time learning a library interface.

Once in a while a guy who owns a furniture factory might just want to go down the basement and build a chair. Hands on the saw, fingers stroking the wood, assessing the grain. Sanding it with his own hands, finishing it. Sweeping up the sawdust.

There's an essence to a linked list that is hard to get at in the middle of a payroll system. Once in a while you have to touch the wood with your own bare hands. -- RonJeffries

Writing it in a functional language gives you not the slightest stench of sawdust, a (single)linked list in HaskellLanguage is a oneliner:

  data List a = Nil | Cons a (List a)

That's probably why I enjoyed doing the BinarySearch exercise on wiki - a little sawdust in my nostrils. But professionally, I don't ever want to write a linked list again. Nor a transaction log, for that matter. Gimme the problem space to wrestle with, not the CS guts and feathers. (Of course, I know the world relies on people who thrive on wallowing in CS guts and feathers - they're the ones who're going to provide me with good linked lists and transaction logs and hash tables). -- AlistairCockburn

Frequent and appropriate use of hash tables is one reason why a Smalltalk application might out perform one written in a simpler language even when that language would beat Smalltalk in benchmarks. That said, if one really wants to reap the benefits of ready-made hash tables then they must understand hashing and understand how to tune a hash function. The hash functions that come with most objects are terrible. Let the reuser beware. -- WardCunningham

Funny, IhadToWriteMyOwnLinkedList about a week ago. It forms the core of a periodic event scheduler for a simulator I'm working on. There are only three procedures involved, one to reschedule the top event (which traverses the list backwards until the correct point, keeping track of how much time will be left on a given period when it reappears at the head of the list); one to look at the top event, tell the system to run for however many cycles remain, and then calls the callback in the event and has it rescheduled; and one to set the list up in the first place.

Sometimes having a library just isn't enough, there will be uses of the LinkedList pattern that simply don't work like a library would expect. While I can't see a similar problem with a HashTable, I wouldn't rule it out. Someone else probably can. -- AlastairBridgewater

Not wanting to start a PissingContest, but wouldn't a PriorityQueue have served as well? It would allow the reschedule as a built-in operation. Of course it might be more code than you need for the application. On the other hand, if one can't write a linked list, that's not so good. AnonymousCoward #471

Hrm... Another concept to look up (easy now there's a WikiPage for it). Meanwhile, the linked list was the first thing I thought of, and I can't think of any way to make it simpler. -- AB (I wonder if that's my BloodType? as well?)

I don't believe there is such code for a PriorityQueue in libc (the only library I can rely on), and if there was, it probably wouldn't have handled the timing information I have to keep track of. And I doubt there will be more than 5 items in the list for quite a while (current maximum is 3, below that there isn't any incentive to switch from the for loop I was using earlier (and still am in places)). -- AB

One of the big problems with declaring, "this <insert data structure or algorithm> will last through the ages," is that most data structures and algorithms are designed to optimize given a set of constraints. That set is not universal, so you may have to write yet another data structure or algorithm later on. Also, some elemental data structures like linked lists and trees map well directly onto several problems, and you may not want to place the objects in an external container (say, there is no external container). Say, a DelegatePattern? (linked list) or the CompositePattern (tree). What's more fun, is that the more elemental the structural relationship, the more likely it is to be applied fractally throughout the system. Big objects link to other big objects, which have containers inside them, etc.

If you're adamant about complaining about writing yet another template<>d linked list, you probably didn't look hard enough for an existing one. -- SunirShah

The assumption that one can has support for template<>s in the first place is a CppCulturalAssumption?, isn't it?

Not really. It was just a specific example. It extends to other languages. -- ss

Uh, guys, sometimes a class has the requirements "contains pointer to own type", and "controls lifetime of owned object on that pointer". For whatever reason. If you get that requirement, type in the freaking primitive Linked List. Don't featurize it (sort, traverse, remove node) unless those features are required too.

You might find yourself immediately, or subsequently, replacing the primitive Linked List with list<>. Or leaving it alone. Or removing features so it's just a link. What matters is you know how to use the canned STL list<>, and you know how to roll your own full-featured linked list (because you have a bachelor's degree), and you know how to fulfill requirements. -- PhlIp

Perhaps beginners are more excited about programming for its own sake, so they're willing to put up with assignments such as writing their own linked list ... And when they get older, perhaps this interest is slowly replaced by a higher-level view of building systems that do radically new things, or building systems that do old things in much less time. LifesJustTooShort, after all.

After ten years of professional work, I would love it if I could spend the next couple of years implementing linked lists, dynamic memory allocation, garbage collection, compilers, relational databases, and other "computer sciency" things. As others have mentioned, there's something about solving these "pure" problems that is refreshing. I'm really tired of writing code that simply reads fields from forms, and sends data through umpteen layers of middleware. -- KrisJohnson

I totally agree. The worst hell for a professional developer is doing web searches on controls/libraries. If you like to code, then you like to code, not research. Perhaps this phenomenon contributes to some anti-VB sentiment. When VB has the most utility - i.e. its component model allows you to totally reuse some one else's code - you have the least fun. This poisons your attitude toward VB, so that you are even more annoyed by VB's real shortcomings (lack of good books on OO features, for example). I am not a full-time VB programmer, though; I suspect as you get to know the components better, you build bigger and better apps, and do a lot more coding, and a lot less researching. -- SteveHowell

I got to implement my own linked list just recently -- as part of a modified hash table implementation no less. I'd say that it was because I'm doing systems level programming (where it's hardly ever too early to optimize), but the algorithm I wrote would probably be useful in business applications as well (it hashes on a two part key and tolerates missing parts so long as there is an unambiguous result that can be found from the remaining partial key). Perfectly good library code is great, but only if it actually is perfectly good for the job you are doing. -- PhilGoodwin

For embedded systems programming, you often want to even optimize even further, so that each byte in a data structure must be maximized in usefulness. This usually means it will depend on the code using it. So, you're unlikely to write much of a data structure library. But the corollary is that you aren't likely to have much data, so you won't have many data structures. -- Mr. Every two bytes count SunirShah

I have found many occasions to write my own implementation of a data structure. Some libraries just look at a data structure and do the ExtremeProgramming you will not need it approach or fail to supply such commonly useful data structures as an n-tree. Then a problem arises that could be solved with some simple, extensible data structures, and I find the library implementation wanting (current issue -- need to create an OrthogonalList? because an implementation in the desired programming language does not exist that does intersections and the database performance is horrid). Some languages implement standard data structures in a very non-extensible manner (*cough* Java *cough*).

"Top, if you don't shape up, I am going to take your nimble tables away and you will have to write linked lists by hand!"

"No, please, no, not that! Anything but that."

I find it amusing within the Java programming language that people seem to take for granted that one needs to write the same code over and over and over for the application of algorithms to data structures when in the C++ STL it was so simple, easy, and mathematically elegant to apply an algorithm to any data structure, including arrays.

We are probably starting a giant flamewar here, but I think Java'ers don't care because Java results in such bloated, long-winded code that iterating over and traversing structures STILL looks small in comparison to all the rest of the bloat.

I find that the Linked List is the only DataStructure I ever have to implement myself - mostly as an optimization. Very often I find that I need to create a stack where objects are capable of deleting themselves from the stack - and said deletion is an extremely common operation. In that case, the objects need a pointer to their own cell (or need to subclass the cell) and for some reason most "enterprise"-style container libs avoid letting you fidget with the cells to do that sort of thing - they expect you to provide an index or something. If I'm feeling impatient I'll do this with a Vector, but the solution is actually _more_ complex because you have to keep track of how middle-deletion will affect the indices of every other object.

This isn't like implementing RedBlackTrees or something equally horrific - LinkedLists are practically trivial in almost every language.

See TwoPointersInOneWord

CategoryDataStructure