Skip to main content

Data Structures Primer

I've been a tutor for this past semester to students taking Introduction to Programming. Many who have come to my session are moving on to Data Structures next semester. They asked if they could have a primer as to what to expect.

I have some resources that I have found helpful both while taking the course and tutoring it in the past. It will take me a little bit to compile a good list of those, but for now, here is a bare-bones list of topics of topics you might expect to see for a data structures course:

Part 1:
- Running time of code segments (Big-O Notation)
- Abstract Data Type (ADT)
- Interfaces (when to use "implements", cannot instantiate them, what inheritance is)
- Superclass, subclass, method overriding/overloading
- Abstract classes

Part 2:
- Binary Search Trees
- Stacks (and its four methods — push, pop, peek, empty)
- Linked list (single, double, circular)
- Prefix and postfix notation (compare to infix)

Part 3:
- Min/Max Heap
- Hash Tables - Open and closed hashing. How to insert into a hash table given a probe sequence.
- Binary Trees (AVL and Red/BLack)
- AVL Trees - how to construct one, worst case AVL-tree
- Red Black Trees
- B-Trees, especially deletion from one
- Know recursive code and how to trace it

Bear in mind, this is an incomplete list. The topics may be presented in different order as well. The "parts" are how I remember it and might not be accurate.

I'm not sure if I'll be able to compile a complete list of resources, but here is probably the best one for visualizing data structures: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Another one is CodingBat.com/java. This is especially helpful for learning recursive code. I don't know if any of the other sections would be helpful, but they might be.

Best of luck! It will be tough, but you got it! Even if you know one or two topics from each part, you will have a leg up on learning this material.

Comments

Popular posts from this blog

Mark Richards on the Evolution of Software Architecture

For this week’s blog on Software Architecture, I listened to Episode 3 of the “Software Architecture Radio” Podcast, which featured Mark Richards, an independent software architect. He has 32 years in the industry, with more than twenty years as a software architect. 
They mostly talked about the evolution of software architecture. Although some of the things they talked about went a little over my head, I was able to pick up on the majority of what they were talking about. 
He divided up the evolution of architecture into five stages. He talked about evolution happening in vertical and horizontal slices, that is within each layer and one layer affecting those above and around it. The layers were (1) hardware, (2) software, (3) human interaction, (4) social interaction, and (5) the environment, such as the internet of things.
He said one thing in particular, need, drives change the fastest. As an aside, he also said that that’s the best way of teaching something in this field, by establi…

Apprenticeship Pattern “Read Constantly”

The apprenticeship pattern I decided to choose for this week’s blog was “Read Constantly.” It was somewhat self-explanatory, but I thought it had some good insights nonetheless.

It recommended reading books over blogs. I would imagine that this is the right course of action from researching blogs last semester. All the material was good and informative, but many times when the host was interviewing someone, it felt like a summary of what could be a very interesting book. There’s only so much that can be gained from a blog post or a podcast. The things that you learn from those can be valuable, but it is better to go deeper when possible. Even if you have a very wide base of knowledge, it will only get you so far when you only scratch the surface.

The quote at the very beginning, from Steve McConnell, says that if you read a good programming book every other month, you will distinguish yourself from your peers. This seems like a worthwhile task, and frankly it is very doable. He chalks…

Productivity for a Developer

For my final blog for “Software Design and Architecture” this semester, I decided to research time management for doing software projects. This is an issue that I ran into creating my final project, and I thought it would be worthwhile to learn from my experience while it was fresh in my mind.

I thought this would be particularly helpful because I would like to do a few projects for fun over the winter break. I don’t think that I’m alone in that without a looming deadline, what little time management skills I have tend to go out the window. I hope this will change this time. I doubt reading an article will transform me into an extremely productive person, but at least it might point me in the right direction. I can only hope.

The article that I found was from *codeproject.com* and was titled “Time Management Tips for Developers.” I thought it gave some good pieces of advice. Even if you are not a software developer, you could benefit from all the advice given. I will focus on three pi…