# What are the advantages/disadvantages of teaching how to implement Nodes, Linked Lists, Stacks, and Queues before showing built-in implementations?

I'd like to introduce my students to Nodes and then require them to implement their own Linked Lists, Queues, and Stacks before showing them that their language (C#) provides implementations of these data structures. I suppose my motivation is that they will 1) understand better how these structures behave; 2) gain general language practice; and 3) appreciate libraries and be more motivated to search for an implementation before writing their own.

Is my motivation valid? What are other reasons to ask them to implement these data structures? Is there any reason NOT to ask them to do this? Would I be wasting my and their time?

• I'm not sure that worth an answer on his own but I would try to insist on your last point : writing proper specific component (be Data Manipulation or Graphic components) that behave perfectly is in fact hard/very time consuming, and that's why it is always recommanded to search before rolling it's own. Apr 26 '18 at 15:00
• Experience working with new CS grads suggests exactly the opposite of (3). So much so that this is one of the main disadvantages of ever teaching these things. Apr 26 '18 at 18:08
• @JavaJive I think the simple explanation is that if a student has only been taught to write code, of course their inclination will be to solve every problem by writing code. From my informal surveys of CS grads, the skill of identifying suitable third party solutions (features, quality, licensing, etc.) is not something that is taught at all. It comes down to whether you're primarily teaching an academic subject or a trade skill. Apr 27 '18 at 16:39
• This reminds me of all the questions on SO where a student is implementing a C++ vector class. Someone will always comment "Why don't you just use std::vector?". When I point out that this is just an exercise in learning how data structures work, they'll say that it's a stupid exercise. Apr 27 '18 at 22:02
• BTW, the answer is quite simple actually. If you want to teach computer science, students must learn implementations of data structures and also they have to know fundamental algorithms. If they don't, they won't be able to call them "computer scientists"... rather, they might call themselves "amateur coders". Apr 28 '18 at 20:52

## 12 Answers

There is one aspect not yet mentioned, though the first two answers are excellent.

Libraries usually contain only the most common data structures and those that can be used in some generic way (pun intended, I guess). But there are other data structures that you may need in your work that aren't in the library you have available. The tools you need for building the standard data structures are likely the same (or a subset) as you need for the bespoke data structures. Sometimes you want a specialized version of a data structure to be able to optimize an important algorithm. So being a tool builder is an important skill that isn't exactly the same as that of being a tool user.

Note: Initially my answer was just about computational complexity, but then it grew a bit, so I broke it into multiple sections and tweaked each a bit. Thanks to commenters for pointing out the details to fix.

### Understanding computational complexity

That may be covered by your "understand better how these structures behave", but it important enough to deserve its own place.

It is very hard to appreciate the computational complexity behind a library structure operations. You don't need or should care how things work under the hood, you should be happy with information that given operation is guaranteed to run in "O(log n)" or "O(container size)" or in "amortized linear time". But to get a good grasp what all that O-speak means, you should actually write the code that iterates over a linked list or finds stuff in a BST.

Once you have some well set expectations of how things work, you can move on and perhaps never write own containers again - but you will forever remember what happens under the hood when you call some random library method (or at least have a rough estimate, see Certainty about behavior).

### General knowledge about writing containers

(mostly inspired by Buffy's answer)

If you ever happen to actually write a container (e.g. one missing in given language), you will not only benefit from specific knowledge about containers you wrote, but, more importantly, from general knowledge about writing containers. There are several reoccurring patterns about containers design, and knowing them from the "internal" perspective certainly helps.

### Certainty about behavior

That one may be important for educational value. Only writing your own structure or algorithm gives you certainty that it behaves as you expect. Built-in structures may often contain extra optimizations and don't necessarily implement any "canonical" structures. They differ in details.

### Avoiding over-complex library APIs

Library containers not only may behave in "non-canonical" way. Their APIs usually contain many additional functions that, while useful in production code, for learning are just unnecessary distraction. E.g. in C++ containers have multiple variants of every method just to allow optimized memory management, or some syntax shortcuts. C# is not very different.

### De-mistyfying library code

Direct answer for question "why do we have to do this": to see that there is no magic. You can do all that things, using libraries is mostly just about saving time. Debugging your own components will likely help you appreciate that libraries are well tested and patched, but should also show that writing similar code isn't something unreachable.

• That is a great point about the complexity of the data structure API. And yes, C# is the same. ArrayList (msdn.microsoft.com/en-us/library/…) having 40+ functions. Apr 26 '18 at 13:20
• using libraries is not only about saving time, it is also to reduce the source of bugs in the application and improving maintenability, unless you're writing your own library, you won't put the same effort in rolling your own component while developping a business application than those who have written proper livrary. In the big scheme you could eventually resume all to "it save time" but I think it's worth to develop it a little. Apr 26 '18 at 15:01
• I don't think "never write own containers again" is necessarily something to take away. Rather, they should learn how to properly implement those structures. That way, if they want to implement a structure for a language that doesn't have such a library, they can. Apr 26 '18 at 16:41
• @Walfrat True, but it's a bit beside the point. After all, the question is about reasons to not use library code. Added some mention about libraries being tested and patched though,
– Frax
Apr 27 '18 at 10:59
• +1 for all points, but especially "appreciating complexity". I have seen some horrible use of built-in/library code where – because it's "just a simple call" – the user clearly has no idea of what complexity lies beneath. While it's not impossible to gain that appreciation without having had a stab at writing your own implementation, doing so (I think) helps enormously. Apr 30 '18 at 9:39

In my experience, it is typical to have students make their own implementation first so that they understand what is going on "under the hood," so that they can make better choices for which structure to use when they need to use a standard library. It helps them to understand the complexity of an algorithm.

I have seen where the standard implementation is used first, and then students are asked to make their own version of it so that they can understand it better. I have never taught it that way, but I think that would work very well with motivated students who are interested in computer science in general. But for many students that might demotivate them, as they will not want to implement something that already exists and that they might feel intimidated (Becuase their work will probably not be at the level of the library given time constraints that are sure to exist).

So I would recommend teaching it in that order, have them implement it first.

Some motivation for teaching it

Here are some drawbacks:

• Some students will know about the built-in versions and ask "Why are we not using them?"
• The implementations that the students provide are never at the quality of the built-in language implementation. There are always going to be reasons why the built-in will outperform their algorithm.

Here are some reasons to teach it:

• It's a common question for interviews, software developers are often asked about it.
• It's a common question on exams. Either asking about the behaviors, trade-offs or actual implementation/complexity questions.
• It is a difficult task, but achievable task. Students who achieve it will have the satisfaction of completing a non-trivial problem.
• Data structures are not the same in all languages, so it is very helpful to have implemented it yourself so that when you transition to another language, you will know what to expect.
• Nice. Emphasize that you aren't teaching them a particular language or library. You are teaching them how to think. Apr 26 '18 at 13:17
• A subpiece of the last point is that while the structures are the same, the names and interface of the same structure may be different between languages. It's a lot simpler to understand that Java HashMaps and C# Dictionaries work basically the same way and accomplish basically the same thing if you understand how a Map works. Apr 26 '18 at 13:42
• Another thing you might want to add is that the students might one day have to work in a programming language where the data structure they need is not built-in and they will be forced to implement it on their own. Apr 26 '18 at 15:08
• "The implementations that the students provide are never at the quality of the built-in language implementation" Don't be so sure of that. The standard library versions frequently have to be super-generic in order to work with all the functions defined over them, and to work with any datatype. It's not that unusual for an implementation tuned to its specific use-case to be able to outperform them.
– Ray
Apr 26 '18 at 23:06
• @Ray Yes, I totally agree with that! If you remove the requirement for generic, you often come up with something easier to implement and more efficient. But generally there is a lot of people and time spent on the generics in languages, so for that reason it is hard to beat. Apr 28 '18 at 19:09

Let me answer from the perspective of someone who recently completed a Data Structures and Algorithms course.

## Background

My Data Structure course was taught using java applets two years ago. My design pattern course last year was the first class many of my peers were exposed to Git (or any version control for that matter), and SOLID design principles were multiple choice questions to answer, rather than industry paradigms which we would be expected to use going forward; in fact in my current courses applying these design patterns would be suicide due to the strict time requirements. In my 400-level Operating Systems course, our first assignment was fibonacci in C, and I can promise you your students are going to go on and have incompetent professors who fail to prepare them for the realities of software development.

It is imperative that you teach these students how to use industry standards and built-ins side by side with theory i.e. IMO, design and implementation go hand in hand. I would argue that AnoE's assertion that "they will be able to find out how to use the API of their language of choice just by reading the reference documentation" makes a very dangerous assumption: that it is not your job to teach these students to be good programmers, rather just good computer scientists. Many students who enter into CS programs do so not aware that Computer Science =/= Software Engineering (although some design patterns and modern day paradigms are included in the curriculum). I will however agree with AnoE vehemently that knowing how these technologies work is infinitely more beneficial to them than the syntax of how to use them, but not teaching them how to use these constructs which are so widely used, which may very well cost you your time in grading and critiquing, is instrumental in producing quality programmers as far as I am concerned.

## tl;dr

My personal advice? Have them write their own Linked Lists, Stacks and what-have-yous, then for part two of the assignment modify their existing codebase to use standard library built-ins, whilst adding some other functionality (threading, pipes, etc., what the assignment calls for). Alternatively, splitting these up into two different assignments works just as well, although may crunch for time.

• One option is to extract an interface (formal or informal) from a library class and have the students implement (and use) their implementation. Then switching to the standard class will be fairly painless. It interface need not even be complete - just enough to be useful. Apr 26 '18 at 23:54
• That also works perfectly well, if not better. Perhaps making it an requirement to switch between the two and retain functionality (if possible) would make for a good inheritance exercise while also teaching design and implementation. Good addition!
– jfh
Apr 26 '18 at 23:58
• I love this idea. Good one. Apr 27 '18 at 11:34
• "In my 400-level Operating Systems course, our first assignment was fibonacci in C" - I'm not sure I'm following the example. It seems that you describe how mismatched your courses were from real-life... but C is for beter or worse lingua franca of system programming - with dose of assembler where required and maybe with C++ thrown in here and there. Maybe in 20 years we will move to Rust or something but as far as OS goes C/C++ has no practical alternative. Assuming you had no exposure to C/C++ Fibbonaci doesn't seem that bad of Hello World... Apr 28 '18 at 8:51
• Let me explain: a 400 level course is a senior level course, as in we don’t need “Hello World” anymore. My main point being that OP’s pupils will likely receive subpar education from their future educators, and that the better of a job he does at teaching them, the less likely they’ll absorb the poor habits of unmotivated professors. I feel though that you may have missed this but I am speaking from my own experiences, where I’ve felt underprepared due to my own professors and OP has a chance to break that cycle for his students. Is that a bit clearer?
– jfh
Apr 28 '18 at 11:35

Assuming they will have a career in C#, you're right to assume that your students will likely never have to make their own queue or stack.

However, that's not the point of the lesson. The point of the lesson is to learn how to make a tool.

Think of it this way:

Every programmer starts off with a "Hello World" application. There is likely never going to be a time where they will professionally have to develop an application that outputs a hardcoded message. But that's not the point of the training exercise. The point of the exercise is to learn how to run a basic application.

You're using the example of stacks and queues as an exercise, because stacks and queues are relatively simple concepts that are easy to grasp.
You're not using the example of stack and queues as an exercise because the industry is relying on these students developing a solution to an ongoing problem.

Let me put you in the role of the students, and teach you something about my company:

• We have managers, developers, accountants, reception staff and janitorial staff.
• The managers are paid a salary.
• The developers are paid a salary.
• The reception staff are paid a salary.
• [censored]
• [censored]

Without me explicitly telling you so, you're likely already assuming that the [censored] parts were supposed to tell you that the accountants and the janitorial staff are paid a salary. You expect this, because you extrapolated a global idea from a collection of examples.

This is what you're trying to get your students to do. You're showing them examples of understanding a problem, accurately defining it, and working towards a solution.

Given enough examples, your studens will learn to distill a generalized approach. With this approach, they will be able to create tools (that do not yet exist!) on their own, without relying on what has already been created.

Somewhat offtopic, you can actually see this principle at play for a lot of cliché action movies. The hero at one point loses access to [advanced thing] and is forced to use [basic thing]. In the end, he masters [basic thing] to a degree where he can outclass those who use [advanced thing] but don't know anyting about [basic thing].

The Karate Kid is one such example that argues the importance of mastering the seemingly unnecessary and outdated basics.

This is essentially what you're teaching your students. While they may be equivalent to their colleagues who use the existing .NET framework; they will leave their colleagues in the dust once they reach uncharted territory and have to create their own data structures.

Funnily enough, I had written the above Karate Kid example before looking up if it was defined as a trope. It is, and it's called "Wax On, Wax Off" in reference to the Karate Kid..

An odd form of training passed off by an unorthodox master on a skeptical student. Sometimes comes disguised as a set of chores, but just as often is a general exercise that promotes a valuable physical or mental attribute in a strange way. Always dismissed as a waste of time early on, but appreciated later.

I've seen too many students implementing linked lists, and then using linked lists of chars as buffers...

Of course at some point students have to understand how things work.

But novice programmers have to learn to think first in terms of abstractions they need in their programs (Example: I have to add/remove/etc. names, so I need some representation of a "set of names"). And then choose a component in a library or implement it.

At some point the students will ask you when and why they should use, say, an HashSet or a TreeSet (in Java), because they are implementing the same API. Or an ArrayList.

So the time comes where you explain how things work: the extensible array for ArrayList, hashing and binary trees. And why they were designed that way, with complexity considerations.

Warning about complexity: insist on the fact it is an asymptotic property. You have to be more pragmatic for small values of n. An extensible array is probably by large the most effective implementation for a set of 0-5 strings. So first think about the amount of data your program will process, and how often.

It find it extremely important to teach them the principles behind those (or similar) data structures first, and I'd go so far as to pick any one of the more complex ones as well (0/1-trees or even B-Trees etc.), just for fun (maybe skipping some details, if time is an issue). I'd also stress some "outliers" like ones that have O(1) in some of their operations; or at least one that is good not only for fast random access, but also for storage on slow media.

You did not tell us which kind of students you have (high school? University? CS or "Programming"? I'll assume CS at a beginner level.). But they will be able to find out how to use the API of their language of choice just by reading the reference documentation (or, alas, these days, more likely, some online "tutorial", which leaves away all but the barest syntactical information). The reference documents will also tell them a little bit about when to use which, but not quite in a way that compares all of the (theoretically possible) structures side-to-side.

That's your job: show them what the world has to offer, and have them get a gut feeling for when to use which. There are several aspects: O-complexities of the operations (insert, delete, search, ...); space-usage aspects; aspects related to storage (i.e., is random access cheap or not?) and so on.

I find it very important that you are able to teach them on a board or paper; i.e., draw boxes, draw lines and so on, so they really get an intuitive feeling about all of this. After that, the actual implementation of most structures and operations should be a snap; and using pre-made libraries even more so.

Whatever you teach them in this way will stay valid and useful until the end of their lives. It gives a good foundation and reinforces structural thinking, branching out to the algorithms later working on those data structures. It's the same reason why one would rather teach a handful of abstract sort algorithms instead of the Java SDK functions for sorting.

For me, a solid knowledge about data structures is one of the few parts of my CS education (which is a few decades gone) that stays with me until today, and has almost everyday applications in both software development, analysis, design, architectural work etc.; and I have certainly, in the past, implemented complicated data structures without having to resolve to libraries (when there were none in the language at hand) with confidence, having a sound background about these topics.

I see no disadvantage with teaching how to implement those structures, whatsoever. I'd rather have someone teach only structures with not a single line of code; than a lot of code in a language or library which is likely obsolete in short time anyway, and no solid foundation for it. Have them find out how to use the API of their choice in their homework assignments; they should definitely be able to do that with any modern, well documented language (and if they are very young, give them a few handy pointers, like the names of the relevant packages/modules in the library or something like that).

Understanding the structures is indeed important. They will often use a library, but should then have a good idea of what the library does. The only argument I see against coding basic structures in programming exercises, is if the time could be better spent doing something else. But my experience is that students starting at "too high a level", tend to make mistakes based on not understanding the containers well. Such as repeatedly sorting a container in order to extract the minimum element, getting slow programs due to the complexity. Such inefficient code is easier to write than the simple iteration loop that find the minimum. Or even proving that the container stays sorted and won't need re-sorting the way they use it.

Also, some are going to maintain the libraries, and some will have to re-implement libraries for the next decade's fancy new language. Understanding the basics is therefore not a waste of time.

Finally, it sometimes possible to do better than a library. I let my students implement their own hashtable, about half of them out-perform Java's HashMap in a simple timing test. It takes the magic out of libraries, and gives some confidence. And it exposes a tradeoff: libraries generally saves development time, but sometimes you need the speed of handcrafted code.

Writing your own code may allow special optimizations. A (long) doubly linked list can be inserted into another in O(1) time. A library container backed by doubly linked lists may be able to do that; but when you make your own, you may decide exactly were one list is inserted into the other. This might save a sorting step later, or optimize for future searches.

Programmers who learn only how to use libraries, without having even an inkling of what’s inside them or how they might be constructed, often become apprentice magicians throwing together opaque incantations. The habit of throwing together sequences of magic incantations to solve problems often has negative consequences (mobile and data center power consumption, cache thrashing, demons stealing one’s firstborn child, and etc.)

Kate Gregory makes a very strong case that the first introduction to C++ should resolutely avoid such things at the start, and instead use standard containers as if they were built in to the language. I completely agree. Her talk, linked below is a must see. Peruse the [C++] tagged questions on StackOverflow, and you will find that most of the beginner questions involve operator new, raw C-style arrays[], and pointers. Teaching students to roll-their-own is teaching them habits that they will need to unlearn. There are plenty of challenging problems to assign that were not solved in the 1960's. Rather than requiring students to implement standard containers and algorithms (badly), show them (when it's time) how the standard features work, and teach how the inner workings affect big-O performance and cache locality.

Even the graduates often do not know how to write production code. Everything they do is an orgy of wheel-reinvention.

I don't think I have used new since 1997, unless it was immediately wrapped in a unique_ptr or shared_ptr.

https://youtu.be/YnWhqhNdYyk

Data structures should absolutely be taught this way and it should be one of the earlier programming classes a student takes. The reasons are that the problems are isolated and therefore easily designed, it introduces you to the subtle complexities that can be hidden by pre-made implementations, and they are fairly fun to implement.

One interview question we ask for java positions is currently "Why would you use a linked list over an ArrayList" You would be truly amazed how many applicants can't answer this most basic of all data structure questions.

Forcing them to make their own data structures then uses them throughout the rest of the year can be the first time they start thinking about "real" software and how it is developed.

Teaching data structures with code is just too good an opportunity to pass up.

• What is the answer? It depends strongly on the potential for cache misses. Apr 28 '18 at 13:27
• I think the question is when to teach common data structures implementation. I doubt you can explain to novices why extensible arrays (ArrayList, vector,...) have an amortized O(1) cost for add() with the capacity-doubling strategy for reallocation. Apr 28 '18 at 15:35
• @JiveDadson You shouldn't use array lists for inserts or additions to the front, only the end. You shouldn't use linked lists when you want to index to the middle often like list.get(500), use an array list for that. I once fixed a program that was taking 8+ hours to insert-sort into an arrayList by simply changing the list type to a linked list, then it took seconds (I actually re-wrote it correctly later, but the initial speed difference from just changing the collection type was staggering) Apr 29 '18 at 0:44
• @MichelBillaud the above comment to jive becomes amazingly clear if you have implemented a linked list and an array list, they are trivial for even a beginner to implement and doing so is extremely educational. I admit that waiting to implement a sorted tree or hash map might be more useful if you've had a year or so of practice) Apr 29 '18 at 0:49
• Educational and valuable, but definitely not trivial. Apr 29 '18 at 16:15

There already are some excellent answers, covering most of the points that I'd also consider as arguments for teaching these basics at the beginning.

Of course, one has to be careful: Depending on the level of the course and the familiarity of the students with programming in general, it could be important to emphasize the actual goals of these tasks, and not accidentally teach them to "reinvent the wheel".

But some things that I'd like to point out:

Software development requires some level of understanding of the foundations that software is built upon. I won't dare to postulate what the "right" level of abstraction could be here. Whether it's electrical engineering, gates and circuits, machine instructions or language constructs. But considering that the building blocks of software (in terms of libraries) become increasingly larger, I think that one should at least have an idea about what the most basic libraries do internally, in terms of the language constructs. The reason for that is simple: That's the level at which software development takes place!

Others have already framed this differently, e.g. by saying that people will occasionally have to craft their own collection/container classes. But I think that it is important to point out that the techniques for developing these basic classes are essentially the same as the techniques that will be used for creating higher-level classes, where the existing container/collection classes serve as building blocks. So you're killing two birds with one stone: Showing them how to develop "proper" classes, and how the classes that they will use work internally.

Another nice aspect of container classes is one that I particularly liked in some of my computer science courses:

Container classes very closely resemble algebraic data types.

You could teach your students how to write yet-another-product-and-customer-management system, or once more model the Lobster extends Animal-hierarchy that has been reiterated ad nauseam. But when you teach them how to implement a Stack, you can put emphasis on the importance of the clarity of the interface of a class, also in terms of behavior and testability. For example, a rigorously formal definition of a stack can consist of push, pop, isEmpty and top methods. You can argue about why this set of methods that is sufficient to operate properly. And the methods have clearly defined relationships and semantics, and therefore simple (yet exhaustive) unit tests.

But of course, whether or not this is relevant for you may also depend on how formal you want your course to be.

• You may be able to formally define and show correctness of that set of methods, but you can't prove they are minimal. In fact, it turns out that push and tryPop (and optionally, blockingPop) are a much more useful public API for a stack or queue. May 13 '18 at 3:25
• @BenVoigt Right, I removed the "minimal" part. Regarding "useful": Of course, one could say e.g. that top can be emulated with tryPop and push (or isEmpty is just top==null or so). (And whether the operation should be blocking is another dimension of the design space). The main point was that 1. there could be a set of methods that resembles the operations that one can apply to a real stack (e.g. a deck of cards), and 2. the set of methods should be small, formal, and sufficient in order to navigate through the state space of the object that they operate on. May 13 '18 at 13:44
• Well the problem with separating isEmpty, top, and pop operations is the TOCTOU window. Even before students start using parallel algorithms, it's useful to start thinking in operations that won't break in an interruptible context. May 13 '18 at 16:14
• "Importance of clean interfaces" is completely lost on people trained to "write assignment, get grade, next". May 17 '18 at 20:33
• @vonbrand Agree. I'm not sure how to convey this importance to CS learners. I think that the idea of Classes being DataTypes being part of an Algebra might help, as well as thinking about what is the minimal set of methods that is necessary to operate properly. (This could be aligned to the language. Roughly: In Java, I tend to always write only interfaces to flesh out the structure (even if there may be an abstract class that implements some convenience methods). But that's a broad topic, and likely discussed in other questions in more detail. May 17 '18 at 23:40