Why are novice programmers forced to learn linked lists?

[LB]

Linked lists are an optimization technique used in only a few specialized cases, such as when the objects in the linked list are large and expensive to copy. Even prior to move semantics, contiguous lists like std::vector dramatically out-perform linked list structures like std::list, even with decently large elements.

Learning about linked lists is an import step to becoming a better programmer, but I definitely think it should be taught much later than it is being taught currently. We see threads on these forums all the time where people who haven't even been doing C++ for a full year yet are forced to create and use linked lists - some are even under the impression that their code will run slower otherwise. The assignments we see use elements that are very small.

So, why are so many novice programmers being forced to learn linked lists as such an early point in their programming education? (Try to avoid morphing the question into "Why do professors teach C++ as if it were C?" or "Why do professors teach the standard library classes later?")

I assume a large culprit is a class which, at my university, is called "Algorithms and Data Structures". I will be taking it next semester to find out first-hand...

EDIT: Question changed to: Why do educators try to use bottom-up instead of top-down education systems?

[z05DSL3A]

Is it the linked list that you are learning when you are asked to implement it?

[LB]

Good point, but good or evil intentions do not always result in good or evil outcomes.

[z05DSL3A]

Back in the day, my lecturer was clear that the reason for doing linked lists and our own string classes was more to practice the other things we were learning. They were also longer running projects. I found it very useful.

[ResidentBiscuit]

We only went over them in our data structures course. And the professor was very clear that the grand majority of the time, linked lists suck. But the ideas of linked lists are used for more advanced data structures. It's just one of the basic data structures that people should know.

[Disch]

This is the age old question of whether or not people learn top-down or bottom-up.

Yes, the concepts you learn when learning how to create a linked list, or writing your own string class can be helpful at teaching you certain skills. But are they the best way to learn those skills?

I never thought so. I'd say it's much better to teach something more practical and build your skills off that. In this sense, I was always an advocate of top-down learning.

Personally, I was never asked to write a linked list/string class.... and by the time the topic ever came up, I already knew enough so that I could do it without difficulty. So I developed my skills elsewhere, and it had more or less the same result. Though I like to think the stuff I did while learning was much more practical than creating dumb utility stuff nobody would ever use.



Then again I think most of how programming everything is taught in school is stupid. The best way to get people to learn is to make the subject matter interesting. With programming this is incredibly easy... probably easier than any other subject. For crying out loud... you're teaching people how to make a computer do anything they want... and you pick "make a linked list"? Booooooooring.

Everyone loves to learn new things. School should be about teaching you new things. So logically, everyone should love school. Yet the reality is, most people hate it. We approach education all wrong.

[LB]

I agree 100% with Disch here. I too advocate top-down learning and think the education system is broken in more ways than one, for more subjects than one.

I guess at this point I should change my question:

Why do educators try to use bottom-up instead of top-down education systems?

[Disch]

I think educators should take some kind of prebuilt program that is simple, fun, and interesting... and use it as sort of a library to introduce to students.

For example... let's say there's some simple fruit ninja clone or something. You start out with a whole, mostly functioning program and have them fill in a very simple part. Like make it so that when you touch the screen, it spawns some fruit.

Then have them change it so that when they touch the screen, it has like a 25% chance of spawning a bomb.

We're talking simple stuff, too... like the changes would literally be like this:

/*
  Student is given this:
*/
void screenTouched()
{
    // student inserts their code here
}


/*
  And their solution might be something like this:
*/
void screenTouched()
{
    double val = getRandomRealNumber();
    if( val < 0.25 )
        spawnBomb();
    else
        spawnFruit();
}

So it's the same basics: variables, function calls, if statements, etc. Only instead of it being in a stupid console program nobody cares about... it's in an awesome game and they can actually see how their code changes are affecting it.


Eventually you take away the modules and tell them "okay... now write the code for the 'spawnFruit' function"

And so on and so on. You eventually work down until they're doing the basic drawing and all that.

Not only does this keep them interested because their code is more tangible, but it also teaches them about modular design, program structure, etc, etc, etc. And it's something everyone can jump into right away.

[LB]

Wow, that's basically how I learned C++ - remember this thread?
http://www.cplusplus.com/forum/lounge/125916/

I've also seen things like making games in Scheme that teach functional programming like that - you just fill in a small part of a larger whole.

[JLBorges]

At some point, the messier and lower-level features of C++ will have to be examined. One way of teaching/learning about pointers, casting, allocation, etc. is to examine the implementation of the classes used to learn the basics. For example, the implementation of string, vector, and list classes are excellent contexts for discussions of language facilities from the C subset of C++ that are best left out of the first part of a course.

http://www.stroustrup.com/new_learning.pdf

[htirwin]

The linked list is not an advanced data structure. It's the first data structure besides arrays that you learn in a data structures course. If you took a data structures course and passed, and afterwards could not make your own linked list, then the professor should be fired.

It would be like taking an algebra course and not learning how to multiply polynomials.

Linked lists introduce linked vs contiguous data structures. Besides learning how they are implemented, you also learn what the difference is and when they are desirable to use. That provides a foundation for learning about trees and graphs.

Another reason you are required to learn data structures is that their underlying algorithms are the most critical and convenient basis for learning time and space complexity.

In my data structures course, we didn't have to implement linked lists, but we had to implement whichever data structures we needed to solve computationally difficult problems. I never implemented linked lists, but I had to implemented various types of trees and graphs.

Sometimes linked lists are taught in the perquisite for data structures so that students are prepared for the much more difficult things they will need to implement in a data structures course.

And for those of you who don't know, a Data Structures course is not about writing C structs or classes. It's about learning the fundamental data structures such as linked lists, queues, min/max heaps, trees ( AVL, Red Black, M-way tree, B-Tree, etc), graphs, hashing (tables, filters, cryptographic, etc), representation of sets etc. Then you learn sorting, searching, and other algorithms that are associated with these data structures.

This course provides the necessary background in order to understand and succeed in courses you have to take afterwards.

Maybe the issue is that 4 years is too small a time frame to cram in everything they expect you to learn. It seams the case that some people are into programming before they take data structures and write programs on their own. Others are just interested in checking off boxes and getting grades. They are able to make it through the introduction class, and maybe all the way through data structures while still being a novice and getting help on everything.

[ResidentBiscuit]

For example... let's say there's some simple fruit ninja clone or something. You start out with a whole, mostly functioning program and have them fill in a very simple part. Like make it so that when you touch the screen, it spawns some fruit.

This is exactly how I got into programming. Junior year of high school I took a video game development class. The class used a language/framework called Dark BASIC, and basically it came with a pre-built 3D world and the goal of the class was to add onto this world and create a game out of it. We didn't really go over any programming concepts explicitly. We were given a partner, and told to look at the code, read the documentation, and figure it out and damn it was awesome.

[LB]

@ResidentBiscuit: Wow, that's an awesome experience to have, especially as early as high school! That kind of class needs to be more prevalent.

[Cheraphy]

Oh wow. Dark BASIC. That was my very first language.

[htirwin]

I think that ideally students would be more advanced by the time they take data structures, and ideally they would have taken prior courses at least some of which were fun and engaging like Disch described.

The problem I think is that it takes some effort outside of just completing your assignments and checking boxes to get to that level because one semester or a few quarters isn't going to really get most people to that point, and most people don't put in that extra effort.

LB is going into Data Structures with a level of skill far beyond what most of the students in that class will have and probably, in practical C++ at least, beyond what most college graduates will have.

[ResidentBiscuit]

Yeah, LB is definitely more advanced in software development than the average student at his level (from my experience). By a long shot. I considered myself decently advanced relatively until I worked with LB! Ha.

But yeah, the Dark BASIC class was awesome. At the time, I was annoyed that the instructor gave us zero instructions besides "Make a game, classroom appropriate". But thinking back on it, it was hugely beneficial. I'm sure if it was some strict lecture class, I never would have gotten the interest in programming, and idea of learning on my own, which nobody will argue is a huge skill to have in this field.

[LB]

I always had trouble with vague assignments in school, but I realize now that that was because most assignments in school had strict, clearly-defined restrictions and requirements. Most of life, however, is vague problems where you have to find out the restrictions and requirements yourself, or decide them yourself. So, really, the vague assignments were trying to teach me how to deal with vague problems.

It's still really hard for me, though - I've always had a hard time making my own decisions because I don't know the trade-offs very well. In programming, however, I'm more familiar with the trade-offs, but I still struggle a bit when deciding how to go about solving a problem. I suppose that's why I'm not a business major. (I wouldn't want to be: http://marshmallowchallenge.com/TED_Talk.html )