Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Teaching data structures with code is just too good an opportunity to pass up.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-28T13:27:03.923Z
Answers.Text: What is the answer? It depends strongly on the potential for cache misses.
Answers.UserDisplayName: Jive Dadson
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-28T15:35:40.290Z
Answers.Text: 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.
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-29T00:44:32.867Z
Answers.Text: @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)
Answers.UserDisplayName: Bill K
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-29T00:49:12.157Z
Answers.Text: @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)
Answers.UserDisplayName: Bill K
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-29T16:15:21.307Z
Answers.Text: Educational and valuable, but definitely not trivial.
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-30T16:08:40.013Z
Answers.Text: @MichelBillaud I can hardly come up with something easier to implement if the educator controls the feature set! An ArrayList is just a wrapped array--expose get/size(trivial) and add.  Add is only non-trivial in that you need to re-allocate the array when it grows, using a fixed size makes it trivial as well.  A LinkedList is the most simple node-based structure. In both cases picking a data type (string or int) removes all generic considerations.  Honestly, can you give me any simpler non-demo classes to teach?  Even common demo classes like Employee/Employer/Store are more complicated.
Answers.UserDisplayName: Bill K
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-05-01T21:14:08.993Z
Answers.Text: if it has a fixed size, it is not an ArrayList, but an array. I agree wrapping an array into an array is rather easy, but where's the beef ? My point is, implementing such structures require some programming skills, that have to be developed before going into it. And they'd benefit from writing interesting exemples that use ready made structures, before they are able to reimplement them.
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-05-01T21:23:27.640Z
Answers.Text: The 1 to N  association between Store and Employee is easy to implement if you have Lists/Sets/Extensible arrays... in your toolbox. add, find, remove...
Answers.UserDisplayName: Michel Billaud
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-05-01T21:44:56.990Z
Answers.Text: @MichelBillaud our only disagreements is that I think it's easier (or at worse as easy) to implement an array list (with a fixed size, say) and then use that to implement your store/employee example.  One of the greatest features of this order is that you discover new requirements in your own code as you proceed (The need for an extendable Array list, for example) and that you learn about building a usable class interface.  I guess my only point is that there is a huge benefit to real, reusable classes to build on as soon as possible, and these two are so easy that it seems to be a no-brainer.
Answers.UserDisplayName: Bill K
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-27T20:17:46.423Z
Answers.LastActivityDate: 2018-04-27T20:17:46.423Z
Answers.UserDisplayName: Bill K
Answers.Body: <p>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. </p>
  
  <p>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 <em>actual</em> goals of these tasks, and not accidentally teach them to "reinvent the wheel". </p>
  
  <p>But some things that I'd like to point out:</p>
  
  <p>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 <em>at least</em> 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!</p>
  
  <p>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, <em>and</em> how the classes that they will use work internally.</p>
  
  <hr>
  
  <p>Another nice aspect of container classes is one that I particularly liked in some of my computer science courses: </p>
  
  <p><strong>Container classes very closely resemble algebraic data types</strong>.</p>
  
  <p>You could teach your students how to write yet-another-product-and-customer-management system, or once more model the <code>Lobster extends Animal</code>-hierarchy that has been reiterated ad nauseam. But when you teach them how to implement a <code>Stack</code>, you can put emphasis on the importance of the clarity of the <em>interface</em> of a class, also in terms of behavior and testability. For example, a rigorously formal definition of a stack can consist of <code>push</code>, <code>pop</code>, <code>isEmpty</code> and <code>top</code> 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.  </p>
  
  <p>But of course, whether or not this is relevant for you may also depend on how formal you want your course to be.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-13T03:25:12.477Z
Answers.Text: 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.
Answers.UserDisplayName: Ben Voigt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-13T13:44:34.663Z
Answers.Text: @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.
Answers.UserDisplayName: Marco13
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-13T16:14:19.877Z
Answers.Text: 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.
Answers.UserDisplayName: Ben Voigt
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-17T20:33:59.133Z
Answers.Text: "Importance of clean interfaces" is completely lost on people trained to "write assignment, get grade, next".
Answers.UserDisplayName: vonbrand
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-17T23:40:53.877Z
Answers.Text: @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.
Answers.UserDisplayName: Marco13
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-04-28T22:08:45.980Z
Answers.LastActivityDate: 2018-05-13T13:36:56.313Z
Answers.LastEditDate: 2018-05-13T13:36:56.313Z
Answers.UserDisplayName: Marco13
Answers.Body: <p>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 <em>must see.</em> Peruse the [C++] tagged questions on StackOverflow, and you will find that most of the beginner questions involve operator <code>new</code>, 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.</p>
  
  <p>Even the graduates often do not know how to write production code. Everything they do is an orgy of wheel-reinvention. </p>
  
  <p>I don't think I have used <code>new</code> since 1997, unless it was immediately wrapped in a unique_ptr or shared_ptr.</p>
  
  <p><a href="https://youtu.be/YnWhqhNdYyk" rel="nofollow noreferrer">https://youtu.be/YnWhqhNdYyk</a></p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-28T13:24:12.760Z
Answers.LastActivityDate: 2018-04-28T14:20:15.497Z
Answers.LastEditDate: 2018-04-28T14:20:15.497Z
Answers.UserDisplayName: Jive Dadson
Answers.Body: <p>There is one aspect not yet mentioned, though the first two answers are excellent. </p>
  
  <p>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 <em>bespoke</em> data structures. Sometimes you want a specialized version of a data structure to be able to optimize an important algorithm. So being a <em>tool builder</em> is an important skill that isn't exactly the same as that of being a <em>tool user</em>. </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T13:35:56.837Z
Answers.LastActivityDate: 2018-04-26T13:35:56.837Z
Answers.UserDisplayName: Buffy
Answers.Body: <p><em>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.</em></p>
  <h3>Understanding computational complexity</h3>
  <p>That may be covered by your &quot;understand better how these structures behave&quot;, but it important enough to deserve its own place.</p>
  <p>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 &quot;O(log n)&quot; or &quot;O(container size)&quot; or in &quot;amortized linear time&quot;. 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.</p>
  <p>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 <em>Certainty about behavior</em>).</p>
  <h3>General knowledge about writing containers</h3>
  <p>(mostly inspired by Buffy's answer)</p>
  <p>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 &quot;internal&quot; perspective certainly helps.</p>
  <h3>Certainty about behavior</h3>
  <p>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 &quot;canonical&quot; structures. They differ in details.</p>
  <h3>Avoiding over-complex library APIs</h3>
  <p>Library containers not only may behave in &quot;non-canonical&quot; 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.</p>
  <h3>De-mistyfying library code</h3>
  <p>Direct answer for question &quot;why do we have to do this&quot;: <strong>to see that there is no magic</strong>. 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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T13:20:49.087Z
Answers.Text: That is a great point about the complexity of the data structure API.  And yes, C# is the same. ArrayList (https://msdn.microsoft.com/en-us/library/system.collections.arraylist(v=vs.110).aspx) having 40+ functions.
Answers.UserDisplayName: nycynik
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T15:01:55.997Z
Answers.Text: 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.
Answers.UserDisplayName: Walfrat
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T16:41:08.257Z
Answers.Text: 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.
Answers.UserDisplayName: mbomb007
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-27T10:59:46.003Z
Answers.Text: @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,
Answers.UserDisplayName: Frax
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-27T11:04:05.350Z
Answers.Text: @mbomb007 Added "perhaps", and something about learning general patterns of writing containers. But the point is, the experience is important even though there is a fair chance of actually never writing a container again. I mean, I don't think "you should learn it because you may need to write that very structure" is a valid point.
Answers.UserDisplayName: Frax
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-30T09:39:22.343Z
Answers.Text: +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.
Answers.UserDisplayName: TripeHound
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T13:15:18.310Z
Answers.LastActivityDate: 2018-04-27T10:56:42.523Z
Answers.LastEditDate: 2020-06-18T08:36:57.023Z
Answers.UserDisplayName: Frax
Answers.Body: <p>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. </p>
  
  <p>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). </p>
  
  <p>So I would recommend teaching it in that order, have them implement it first.  </p>
  
  <p><em>Some motivation for teaching it</em></p>
  
  <p>Here are some drawbacks:</p>
  
  <ul>
  <li>Some students will know about the built-in versions and ask "Why are we not using them?"</li>
  <li>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.</li>
  </ul>
  
  <p>Here are some reasons to teach it:</p>
  
  <ul>
  <li>It's a common question for interviews, software developers are often asked about it.  </li>
  <li>It's a common question on exams.  Either asking about the behaviors, trade-offs or actual implementation/complexity questions.</li>
  <li>It is a difficult task, but achievable task.  Students who achieve it will have the satisfaction of completing a non-trivial problem.</li>
  <li>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. </li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T13:17:49.153Z
Answers.Text: Nice. Emphasize that you aren't teaching them a particular language or library. You are teaching them _how to think_.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T13:42:47.283Z
Answers.Text: 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.
Answers.UserDisplayName: IllusiveBrian
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T15:08:19.350Z
Answers.Text: 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.
Answers.UserDisplayName: Philipp
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T23:06:23.630Z
Answers.Text: `"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.
Answers.UserDisplayName: Ray
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-28T19:09:13.127Z
Answers.Text: @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.
Answers.UserDisplayName: nycynik
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T13:10:36.080Z
Answers.LastActivityDate: 2018-04-26T13:17:24.980Z
Answers.LastEditDate: 2018-04-26T13:17:24.980Z
Answers.UserDisplayName: nycynik
Answers.Body: <p>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.</p>
  
  <p>However, that's not the point of the lesson. The point of the lesson is to learn how to make a tool.</p>
  
  <blockquote>
    <p>Think of it this way: </p>
    
    <p>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.</p>
  </blockquote>
  
  <p>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.<br>
  You're <strong>not</strong> 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.</p>
  
  <p>Let me put you in the role of the students, and teach you something about my company:</p>
  
  <blockquote>
    <ul>
    <li>We have managers, developers, accountants, reception staff and janitorial staff.</li>
    <li>The managers are paid a salary.</li>
    <li>The developers are paid a salary.</li>
    <li>The reception staff are paid a salary.</li>
    <li>[censored]</li>
    <li>[censored]</li>
    </ul>
  </blockquote>
  
  <p>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 <strong>you extrapolated a global idea from a collection of examples</strong>.</p>
  
  <p>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.  </p>
  
  <p>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.</p>
  
  <hr>
  
  <p>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].  </p>
  
  <p>The Karate Kid is one such example that argues the importance of mastering the seemingly unnecessary and outdated basics.</p>
  
  <p>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.</p>
  
  <p>Funnily enough, I had written the above Karate Kid example before looking up if it was defined as a trope. <a href="http://tvtropes.org/pmwiki/pmwiki.php/Main/WaxOnWaxOff" rel="nofollow noreferrer">It is, and it's called "Wax On, Wax Off" in reference to the Karate Kid.</a>.</p>
  
  <blockquote>
    <p>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. <strong>Always dismissed as a waste of time early on, but appreciated later</strong>. </p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-27T07:56:12.070Z
Answers.LastActivityDate: 2018-04-27T08:05:07.413Z
Answers.LastEditDate: 2018-04-27T08:05:07.413Z
Answers.UserDisplayName: Flater
Answers.Body: <p>I've seen too many students implementing linked lists, and then using linked lists of chars as buffers...</p>
  
  <p>Of course at some point students have to understand how things work.</p>
  
  <p>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.</p>
  
  <p>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.  </p>
  
  <p>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.</p>
  
  <p>Warning about complexity: insist on the fact it is an <em>asymptotic</em> 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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-27T06:57:58.847Z
Answers.LastActivityDate: 2018-04-27T11:49:08.660Z
Answers.LastEditDate: 2018-04-27T11:49:08.660Z
Answers.UserDisplayName: Michel Billaud
Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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. </p>
  
  <p>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.</p>
  
  <p>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 <em>on</em> 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.</p>
  
  <p>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.</p>
  
  <p>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 <em>are</em> very young, give them a few handy pointers, like the names of the relevant packages/modules in the library or something like that).</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T14:14:27.080Z
Answers.LastActivityDate: 2018-04-26T14:14:27.080Z
Answers.UserDisplayName: AnoE
Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-30T10:38:53.807Z
Answers.LastActivityDate: 2018-04-30T10:38:53.807Z
Answers.UserDisplayName: Helge Hafting
Answers.Body: <p>Let me answer from the perspective of someone who recently completed a Data Structures and Algorithms course.</p>
  
  <h2>Background</h2>
  
  <p>My Data Structure course was taught using java applets <strong>two years ago</strong>. 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.</p>
  
  <hr>
  
  <p>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. </p>
  
  <h2>tl;dr</h2>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T23:54:41.573Z
Answers.Text: 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.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T23:58:03.137Z
Answers.Text: 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!
Answers.UserDisplayName: jfh
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-27T11:34:29.807Z
Answers.Text: I love this idea.  Good one.
Answers.UserDisplayName: Java Jive
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-28T08:51:48.467Z
Answers.Text: "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...
Answers.UserDisplayName: Maja Piechotka
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-28T11:35:24.820Z
Answers.Text: 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?
Answers.UserDisplayName: jfh
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-28T11:39:33.017Z
Answers.Text: I can amend my answer for clarity but I felt that a senior level course teaching a Hello World type application is pretty clearly a waste of time. I felt like it was safe to make such an assumption given everyone’s experience with CS here as well.
Answers.UserDisplayName: jfh
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-26T23:32:43.363Z
Answers.LastActivityDate: 2018-04-26T23:32:43.363Z
Answers.UserDisplayName: jfh
Answers.Body: <p>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.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-08T00:42:58.263Z
Answers.LastActivityDate: 2018-05-08T00:42:58.263Z
Answers.UserDisplayName: hotpaw2
Body: <p>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.</p>
  
  <p>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?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-26T15:00:02.420Z
Comments.Text: 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.
Comments.UserDisplayName: Walfrat
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-26T18:08:35.207Z
Comments.Text: 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.
Comments.UserDisplayName: StackOverthrow
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-27T11:38:21.987Z
Comments.Text: @TKK, are you saying that new grads who know how to implement their own data structures are prone NOT to use built-ins?  If so, can you conjecture on why that is true?  Are they over confident?  Are they trying to be heroes?
Comments.UserDisplayName: Java Jive
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-27T16:39:22.947Z
Comments.Text: @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.
Comments.UserDisplayName: StackOverthrow
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-27T22:02:35.087Z
Comments.Text: 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.
Comments.UserDisplayName: Barmar
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-28T13:49:47.813Z
Comments.Text: @Barmar - They have a point.
Comments.UserDisplayName: Jive Dadson
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-28T20:50:16.070Z
Comments.Text: @JiveDadson the only point they have is that it's annoying to do that in C++, but that's not a valid point on the general principle. :P
Comments.UserDisplayName: Andrea Lazzarotto
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-28T20:52:03.967Z
Comments.Text: 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".
Comments.UserDisplayName: Andrea Lazzarotto
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-29T17:54:24.180Z
Comments.Text: @AndreaLazzarotto that's... a bold claim. An overwhelmingly large portion of people who receive CS education do not need to know the answer to this question for their career, except to pass interviews (which  is ironic). This won't be as true if someone wants to go into academia.
Comments.UserDisplayName: enderland
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-29T18:45:55.410Z
Comments.Text: @enderland no, it's not bold. There is a minimum threshold of knowledge if you want to be called "computer scientist", and **fundamental** data structures are included. Most people who work as programmers are *not* computer scientist and it's fine. Even among developers, some are not (for instance, they can be engineers or they can have other backgrounds). You are confusing "working in IT" with "being a computer scientist". You might work in healthcare, but you are not a doctor if you do not know how a kidney works.
Comments.UserDisplayName: Andrea Lazzarotto
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-30T10:48:40.283Z
Comments.Text: "fundamental IO routines"? That would be a useful practice, honestly, but luckily we have engineers for those matters. BTW whatever you "expect" from people, implementing the standard data structures is an essential step in understanding how they work in practice, how space is used in memory and so on. Computer scientists are going to need more advanced, custom data structures in their jobs... And how are they going to implement them if they don't even know the basics?
Comments.UserDisplayName: Andrea Lazzarotto
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-30T12:52:26.193Z
Comments.Text: @Hurkyl as a nice anecdote, while working on an iOS app in Swift I just realized the iOS SDK does not provide stacks and queues. I am going to implement them myself, obviously, but this is only possible because I *did* study them while attending university.
Comments.UserDisplayName: Andrea Lazzarotto
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-30T23:05:55.097Z
Comments.Text: @AndreaLazzarotto There are computer scientists, and there are real programmers. You can take a kid off the street and turn him into a real programmer in six months. Or you can take a CS grad and spend at least a year unschooling him before you can even start to make him a real programmer. I don't know of any other professional field where the education system has failed more disastrously.
Comments.UserDisplayName: StackOverthrow
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-30T23:37:37.173Z
Comments.Text: ROTFL yeah sure.
Comments.UserDisplayName: Andrea Lazzarotto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-17T21:30:14.027Z
Comments.Text: Isn't reimplementing stacks and queues a total waste of time? Can't you find a library for this?
Comments.UserDisplayName: Michel Billaud
Tags: <data-structure>
Title: What are the advantages/disadvantages of teaching how to implement Nodes, Linked Lists, Stacks, and Queues before showing built-in implementations?
ThreadText: # What are the advantages/disadvantages of teaching how to implement Nodes, Linked Lists, Stacks, and Queues before showing built-in implementations?
  
  (Asked by: username_0 on 2018-04-26)
  
  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?
  
  **Tags:** data-structure
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_2**: 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.  
  > **username_0**: @TKK, are you saying that new grads who know how to implement their own data structures are prone NOT to use built-ins?  If so, can you conjecture on why that is true?  Are they over confident?  Are they trying to be heroes?  
  > **username_2**: @username_0 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.  
  > **username_3**: 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.  
  > **username_4**: @username_3 - They have a point.  
  > **username_5**: @username_4 the only point they have is that it's annoying to do that in C++, but that's not a valid point on the general principle. :P  
  > **username_5**: 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".  
  > **username_6**: @username_5 that's... a bold claim. An overwhelmingly large portion of people who receive CS education do not need to know the answer to this question for their career, except to pass interviews (which  is ironic). This won't be as true if someone wants to go into academia.  
  > **username_5**: @username_6 no, it's not bold. There is a minimum threshold of knowledge if you want to be called "computer scientist", and **fundamental** data structures are included. Most people who work as programmers are *not* computer scientist and it's fine. Even among developers, some are not (for instance, they can be engineers or they can have other backgrounds). You are confusing "working in IT" with "being a computer scientist". You might work in healthcare, but you are not a doctor if you do not know how a kidney works.  
  > **username_5**: "fundamental IO routines"? That would be a useful practice, honestly, but luckily we have engineers for those matters. BTW whatever you "expect" from people, implementing the standard data structures is an essential step in understanding how they work in practice, how space is used in memory and so on. Computer scientists are going to need more advanced, custom data structures in their jobs... And how are they going to implement them if they don't even know the basics?  
  > **username_5**: @Hurkyl as a nice anecdote, while working on an iOS app in Swift I just realized the iOS SDK does not provide stacks and queues. I am going to implement them myself, obviously, but this is only possible because I *did* study them while attending university.  
  > **username_2**: @username_5 There are computer scientists, and there are real programmers. You can take a kid off the street and turn him into a real programmer in six months. Or you can take a CS grad and spend at least a year unschooling him before you can even start to make him a real programmer. I don't know of any other professional field where the education system has failed more disastrously.  
  > **username_5**: ROTFL yeah sure.  
  > **username_7**: Isn't reimplementing stacks and queues a total waste of time? Can't you find a library for this?  
  
  ---
  
  ## 12 answers
  
  ### Answer by username_12 on 2018-04-26. Score: 31
  
  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 by username_13 on 2018-04-26. Score: 28
  
  *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 username_12'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.
  
  > **Comments:**
  > **username_14**: That is a great point about the complexity of the data structure API.  And yes, C# is the same. ArrayList (https://msdn.microsoft.com/en-us/library/system.collections.arraylist(v=vs.110).aspx) having 40+ functions.  
  > **username_1**: 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.  
  > **username_15**: 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.  
  > **username_13**: @username_1 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,  
  > **username_13**: @username_15 Added "perhaps", and something about learning general patterns of writing containers. But the point is, the experience is important even though there is a fair chance of actually never writing a container again. I mean, I don't think "you should learn it because you may need to write that very structure" is a valid point.  
  > **username_16**: +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.  
  
  ---
  
  ### Answer by username_14 on 2018-04-26. Score: 13
  
  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.
  
  > **Comments:**
  > **username_12**: Nice. Emphasize that you aren't teaching them a particular language or library. You are teaching them _how to think_.  
  > **username_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.  
  > **username_18**: 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.  
  > **username_19**: `"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.  
  > **username_14**: @username_19 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.  
  
  ---
  
  ### Answer by username_20 on 2018-04-27. Score: 4
  
  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.](http://tvtropes.org/pmwiki/pmwiki.php/Main/WaxOnWaxOff).
  
  > 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 by username_7 on 2018-04-27. Score: 4
  
  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 by username_23 on 2018-04-26. Score: 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 username_21'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 username_21 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.
  
  > **Comments:**
  > **username_12**: 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.  
  > **username_23**: 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!  
  > **username_0**: I love this idea.  Good one.  
  > **username_24**: "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...  
  > **username_23**: 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?  
  > **username_23**: I can amend my answer for clarity but I felt that a senior level course teaching a Hello World type application is pretty clearly a waste of time. I felt like it was safe to make such an assumption given everyone’s experience with CS here as well.  
  
  ---
  
  ### Answer by username_21 on 2018-04-26. Score: 3
  
  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 by username_22 on 2018-04-30. Score: 3
  
  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 by username_25 on 2018-05-08. Score: 2
  
  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 by username_4 on 2018-04-28. Score: 1
  
  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 by username_8 on 2018-04-27. Score: 0
  
  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.
  
  > **Comments:**
  > **username_4**: What is the answer? It depends strongly on the potential for cache misses.  
  > **username_7**: 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.  
  > **username_8**: @username_4 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)  
  > **username_8**: @username_7 the above comment to username_0 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)  
  > **username_7**: Educational and valuable, but definitely not trivial.  
  > **username_8**: @username_7 I can hardly come up with something easier to implement if the educator controls the feature set! An ArrayList is just a wrapped array--expose get/size(trivial) and add.  Add is only non-trivial in that you need to re-allocate the array when it grows, using a fixed size makes it trivial as well.  A LinkedList is the most simple node-based structure. In both cases picking a data type (string or int) removes all generic considerations.  Honestly, can you give me any simpler non-demo classes to teach?  Even common demo classes like Employee/Employer/Store are more complicated.  
  > **username_7**: if it has a fixed size, it is not an ArrayList, but an array. I agree wrapping an array into an array is rather easy, but where's the beef ? My point is, implementing such structures require some programming skills, that have to be developed before going into it. And they'd benefit from writing interesting exemples that use ready made structures, before they are able to reimplement them.  
  > **username_7**: The 1 to N  association between Store and Employee is easy to implement if you have Lists/Sets/Extensible arrays... in your toolbox. add, find, remove...  
  > **username_8**: @username_7 our only disagreements is that I think it's easier (or at worse as easy) to implement an array list (with a fixed size, say) and then use that to implement your store/employee example.  One of the greatest features of this order is that you discover new requirements in your own code as you proceed (The need for an extendable Array list, for example) and that you learn about building a usable class interface.  I guess my only point is that there is a huge benefit to real, reusable classes to build on as soon as possible, and these two are so easy that it seems to be a no-brainer.  
  
  ---
  
  ### Answer by username_9 on 2018-04-28. Score: 0
  
  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.
  
  > **Comments:**
  > **username_10**: 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.  
  > **username_9**: @username_10 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.  
  > **username_10**: 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.  
  > **username_11**: "Importance of clean interfaces" is completely lost on people trained to "write assignment, get grade, next".  
  > **username_9**: @username_11 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.  
  
  ---
  
  