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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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).

Answer 8

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.

Answer 9

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.)

Answer 10

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

Answer 11

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.

Answer 12

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.