Data Structures... so how do I understand them?

Question

So I am a Computer Science student and in about a week or so... I will be retaking a Data Structures course, using C++ for applying the theory. Yes, I did say "retaking". I took the course last Fall and I feel like there is more that I need to learn. Being a student, I feel that I MUST know the basics because it will be much easier to understand new concepts in future classes by already knowing the basic concepts... not having to relearn every time.

The first time around, I had no experience in C++ and the course expected us to be coding by the end of the first week. I struggled getting through several of the first programming assignments (MPs). Needless to say, I got used to it and had little trouble with the syntax the remainder of the semester. But then the harder Data Structures came around and the theory (Big O), became the difficult part.

All in all it was a great experience, but I feel my problem was that I didn't develop good study habits. I did the MPs and showed up to lecture, but it seems like my heart wasn't there with me. I want to change this the second time around because looking back at the class, I did have a good time and I enjoyed the material. But I found myself spending too much time thinking about/setting up the data structure(s) when I needed to be spending the time thinking about how to put the data structure to use effectively.

Learning theory is difficult (mostly because it isn't so exciting) so how should I apply myself to truly understand the Data Structures covered class? I've always been a visual learner, an interactive learner... I don't want to spend time just doing my MPs. Rather, I want to spend my time in such a way that I truly learn/understand the concepts and then directly apply the knowledge.

I'm looking for any suggestions... perhaps advice on study habits that have worked for you in the past learning such concepts... or suggestions on good note-taking techniques... anything that you'd like to share :) ... and most importantly, how to prepare before the semester starts.

Please feel free to provide feedback even if an answer has been selected. I am looking for your advice... this is why I posted :) Thanks!

---

NOTE: Data Structures and Topics covered in the course: Lists, Stacks, Queues, Trees (different kinds), Hash Tables, Graphs, Searching/Sorting/Traversal techniques.

---

UPDATE: Here's a list of links and references compiled from the answers so far.

• Algorithms in C++ by Robert Sedgewick
• Introduction to Algorithms by Cormen
• The NIST Dictionary of Algorithms and Data Structures
• Sorting algorithms
• Tree traversals
• Graph traversals
• http://www.codeproject.com/KB/cpp/linked_list.aspx
• http://www.codeproject.com/KB/architecture/treedata_class.aspx

UPDATE 2: Here's a list of some more sources that I found:

• http://people.ksp.sk/~kuko/bak/big/
• http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html
• http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html
• http://www.cs.duke.edu/csed/jawaa2/examples/BFS.html

Answer 1

The only way to meaningfully learn data structures and algorithms is to see them applied to real-world problems and to use them to solve real-world problems. Coding them up into working applications -- even if they contrived -- will reinforce the theoretical knowledge such that you will stand a better chance of retaining the ideas and integrating them into your personal problem-solving approach.

Answer 2

Here's what helped me the most... Since you're a visual person, Google some visualized sorting algorithms, tree traversals, hashing, and etc to get a general idea of what's going on. After that, try making a simple program using different structures and experiment with different permutations of them--maybe for an example, you can make a linked list to start, then make it a circular linked list, then make it a doubly linked list, then make it a doubly circular linked list, and so on...

You just have to experiment with the structures, and as you do that, you'll start to see what data structures are appropriate for the applications you'll be developing.

Here are some nice references for you.. Sorting algorithms: http://www.sorting-algorithms.com/ Tree traversals: http://nova.umuc.edu/~jarc/idsv/lesson1.html Graph traversals: http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html

---

As for efficiency (Big O analysis), it will come to you more or less naturally once you understand what is happening at the algorithmic level of each operation of the data structure.

One thing my university stresses is the development of our own implementation of data structures (which is bottom-up learning) without diving into the pre-established C++ templates (top-down learning). By making it from scratch, you really come to understand the overhead involved with inserting, removing, searching (traversing), and accessing data from a certain structure, and that will help your intuition when designing a system in the future.

Answer 3

Practice, practice, practice.

The first piece of advice that I have for you is to become as proficient as possible at C++.

Data Structures and Programming are two very different topics. If you find yourself struggling with programming, it is unlikely that you will be able to comprehend the data structures.

How do you become proficient in C++? Practice, practice, practice. Program everything. Learn everything you can about it. Write dozens of small programs. Anything you can do to become comfortable with C++.

If you become proficient at C++, then I assure you that data structures will become easier. (Notice that I didn't say easy, I said easier :) )

Answer 4

If you can visualize the implementation of data structures in real life, or to solve real life problems, then you may find it easier to understand.

Here are a few

1. FIFO Linked List - This is the drive through at McDonalds
2. LIFO Linked List - A stack of dinner plates
   • Searching and Sorting - A rolodex (if you're old that you've actually seen one of these things)

Answer 5

The key to learning data structures is to start with something small, and then build on that. Let's start with a simple C struct:

struct Person {
  char name[100];
  int age;
};

This data structure represents a person. You need to make sure you understand simple structure concepts such as these, and then you can move to bigger things.

When you start talking about data structures like stacks and queues, for example, first try to understand conceptually what the data structure is doing. For example, with a stack, we are using the LIFO principle, that is, Last In First Out. With a queue, we are using the FIFO principle (first in first out).

And then there's the one that trips a lot of people up, the linked list. You need to understand pointers well for this one, so before trying to tackle linked lists, start with something simple:

int* x;
int y = 10;
x = &y;

You should be able to look at that code and immediately know what it's doing. If you can't, then you're not ready to move to more advanced data structures like linked lists.

The main point I'm trying to make is you need to get the basics down cold, then build on those. It's also important to keep up with the class very diligently, ask your teacher or tutor if you are having troubles, and make sure you are on track each week and don't fall behind.

Computer Science classes are much like Math classes, each week usually builds on everything you've learned from the previous N weeks. So if you aren't understanding a key concept, like pointers for example, then you are going to have major struggles the remainder of the semester.

Answer 6

Here is a nice article to get you started: http://www.codeproject.com/KB/cpp/linked_list.aspx .Start with a simple linked list. It's very easy and you will understand it much easier than the other data structures. The Stack and Queue are maybe conceptually even easier but they are based on the simple linked list. Then you can move to double linked lists and trees. Looking forward to see your coding questions, Good Luck! :)

Answer 7

I would recommend getting a good book on algorithms ('Introduction to Algorithms' by Cormen et al. would be my recommendation). Through the book you will both develop and put to use different data structures and you will most probably realize what each structure is good for. Data structures are only useful as means to achieve a different goal: solving a particular problem.

Depending on how much time you have or want to spend on it, you can try to get problems from different programming contests like the ACM ICPC. Most of the problems will require you exercise this knowledge. Note that both algorithms and data structures are language agnostic, so if you have good knowledge of any other language just use it.

Answer 8

If you're a visual learner then ask your instructor for more diagrams. You might ask other students if you can study with them. Perhaps one of them can explain things to you in a way you can grasp more easily

Answer 9

In my opinion, these things are better off learned on-the-job, or through experience than in a theory course. Most times, while I was in school, working hard to stay ahead of the curve was the important part, which I think is similar to the experience that you have gone through. While it's commendable that you want to understand it thoroughly, as long as you know where to find good reference material when you need it, then the course has achieved its objective.

Most classes will build on the knowledge that you've gained in past classes. You'll run into these details again in your studies and your professors should be able to help you apply what you've learned in the past to your current classwork. As an interactive learner, office hours, internships and mentor opportunities seem like better ways to get the information you want.

Good luck!

Answer 10

I like dcp's answer.

The best way to wrap your head around data structures is to write mini examples. Even if you copy them from your book, if you can get them to work and compile, and you typed them in with your own fingers, you will learn a lot.

As you read your book, and after each lecture, write the shortest programs you can that create and work with (display, use, etc.) the data structure you just learned about.

Then when you have to do your actual assignments you'll learn even more as you try and take your mini examples and plug them into the solving of the assignment problems.

I think writing the shortest / smallest possible piece of working code for individual data structures is very useful. Also, don't be afraid to copy code (for your own edification, not for your turned in assigments).... If you copy by typing and not copy pasting, you do end up learning a lot, since it forces you to look at each character in the code.

---

If entire data structures seem like "too much" to wrap your head around, then start by writing mini examples of the components of the Data structures. So store a book title with a pointer. Then store many book titles with pointers to pointers. Read a book title with square bracket notation and pointer arithmetic. Use recursion in simple functions where it is clear what is going on..... For example recursion to show the factorial of a number is simpler to wrap you head around than recursion to show a binary tree (in my opinion).....

You'll see what your problem areas are, and try and isolate them to as small and specific of a thing as you can, and then write as short a program that you can that deals with that problem area..... and then build up.

Your lectures are about entire data structures... giant Cummulus cloud banks of theory.... so, essentially they are top down. Isolating little problems of syntax and usage in mini problems is bottom up. So your teacher helps you attack from the top, you attack from the bottom by practicing, and pretty soon there's nothing in the middle!

Answer 11

A good resource is The NIST Dictionary of Algorithms and Data Structures. You aren't going to sit down and memorize all this information, and you shouldn't use it to avoid coding up your own structures, that would completely void the value of the class, but this site serves as a great reference because it links the data structures with the algorithms that utilize them and also shows some variants, which provides insight into how you can modify the structures for other uses.

Hope that helps. Good luck.

---

Answer 12

You have received some interesting links and ideas already. I hope I can provide a little different point of view:

I learned to visualize and "like" data structures by being taught that computer memory is like a really long list. The structures then have different layout in the memory. By visualizing the structures in the memory, it became obvious to me (and interesting) how they work. Knowing the data layout in memory is incredibly important for a programmer as today's continuously growing machines are often halted by memory-access. A good memory-layout easen the burden for the CPU to fetch the data from the memory so that the CPU doesn't have to wait for data to arrive.

Data structures is the layout of the data in a memory. Consider memory as a long list, just like a shopping list but without the entries.

0...
1...
2...
3...
4...
5...
6...

When you put structures into the memory, they essentially fill up these slots in memory.

A list is very simple, it just fills the memory-list from the top and down:

0 Element 0
1 Element 1
2 Element 2
3 Element 3

Although sometimes you want to change element 2 to something else, maybe zero. That's the way lists work. You can access the data in the structure by knowing their index (in this case, 0 .. 3).

Stacks are different. You can only access the "top" of a stack by "pushing" an element to the top of it, or "poping" an element from the top of it. Pushing means adding another element and the old top becomes invisible. Poping means removing the top element and the one below it becomes visible.

0   [ Hidden data ]
.   [ Hidden data ]
.   [ Hidden data ]
.   [ Hidden data ]
n   [ Hidden data ]
n+1 Element 4

Linked lists are different. A linked list contains a pointer (index in the memory-list) to the data, and one pointer to the next element:

0 Data: Memory index 0x00000100
1 Next: Memory index 6
2 
3 
4 
5 
6 Data: Memory index 104
7 Next: Memory index 8
...
100 Data pointed to from first member
101
102
103
104 Data pointed to from second member

Queue's is like a more powerful stack, you have access to both the bottom and the top. You can only push items to the top and you can only pop items from the bottom.

0 (bottom) Element (ready to be popped)
1 [ Hidden data ]
2 [ Hidden data ]
3 [ Hidden data ]
.
.
.
n (top) (empty, ready to be pushed / be given data)

By visualizing the layout of each data-structure, they became a lot more obvious to me in how they require memory and how they really work ( also in the memory). I hope that my examples have given you some brief starting knowledge for you to base your future studies on. As a final example on data structures, I will give you an unbalanced binary tree that have had the following order of element insertion: 3, 2, 1, 10, 9, 8, 6, 5, 4, 7

The tree starts at memory address 100, since memory address 0 is invalid and I'll use that as a "no pointer".

100 Value: "3"
101 Left ptr: 103
102 Right ptr: 109

103 Value: "2"
104 Left ptr: 106
105 Right ptr: 0

106 Value: "1"
107 Left ptr: 0
108 Right ptr: 0

109 Value: "10"
110 Left ptr: 112
111 Right ptr: 0

112 Value: "9"
113 Left ptr: 115
114 Right ptr: 0

115 Value: "8"
116 Left ptr: 118
117 Right ptr: 0

118 Value: "6"
119 Left ptr: 121
120 Right ptr: 127

121 Value: "5"
122 Left ptr: 124
123 Right ptr: 0

124 Value: "4"
125 Left ptr: 0
126 Right ptr: 0

127 Value: "7"
128 Left ptr: 0
129 Right ptr: 0

Hope that helps!

Answer 13

I can remember my first data structures course. I remember being a bit overwhelmed at first.

I was more of a visual learner. To better grasp the material it really helped to see pictures. I used to draw out the steps of inserting, deleting and iterating through data structures such as a linked list or queue. It took up a lot of paper before I was done, but it was so worth it.

Once I got down drawing the process of insertions and what nots, the transition to actually programming the data structure was much easier.

Being able to visualize what was going on in memory really helped. And, as others mentioned before me: practice, practice, practice!

That there is a big part of success.

Good luck!

Answer 14

Not sure this is any help, really, but it may be somewhat encouraging.

I was in the same boat when I took Data Structures 4 years ago. I went through the class with enough knowledge to get by and get the B, at least, in the class even though I didn't understand a lot of it.

I did not understand templates, linked lists, 'this' pointers, and really didn't understand pointers in general that well either, which greatly hindered my ability. I miraculously did what was required on the homework and tests (although test scores were still low for everyone and my teacher wound up curving them) and finished with a B.

After that I went on to take other classes for a few years. I found that in these classes different concepts were taught separately that helped me understand them better. Algorithms taught more about sorting and Big O, Assembly taught more about what was going on 'under the hood' of the computer which helped me understand pointers, etc.

I realized the second to last semester of my fifth year that I pretty much knew all the concepts from Data Structures and I hadn't even spent any extra effort to learn them, at least not from the standpoint of going back and trying specifically to understand Data Structures, if that makes any sense.

Without any real effort I wound up writing a templated, linked-list stack and queue for a couple of homework assignments in Operating Systems and I understood them. It blew me away. I'm positive it will be the same for you. Give it time and focus on other classes and it will all click. It seemed to take forever for it all to click for me, but it did.

Hope that helps.

Answer 15

Honestly, I'm a self-taught C++ programmer originally (with my primary reference being the Source game engine's public-domain code from Half-Life 2), and I learned much of what got me through Data Structures by drawing up diagrams and reading comments and code.

Maybe I'm just a prodigy or something, because it always seemed to come relatively easy to me, but I learned during a LOT of time spent reading, thinking, and analyzing what the particular uses of each structure could be, and why each structure exists as something separate from the other data structures in the first place.

Having written some serious code projects (ie. Connect Four and a side-scrolling space shooter, as well as 3D isometric plotters and 2D drawing programs) on the severely-limited TI-83 Plus calculator in high school (p.s. Using TI-Basic, not Assembly), I realized what sorts of operations were more efficient, and I realized how limited the built-in list system (a basic Vector) was for data storage in certain situations. I also figured out how Big-O worked when I tried timing a program's runtime with different-size lists of input.

Practice, think about things as you are doing them, and try to figure out how and why they work, and never be afraid to get down and dirty with testing. After all, what is science without experimentation?

Answer 16

Practically speaking, I find that data structures require a solid understanding of pointers and memory.

For instance, you should be able to grok why the below linked list doesn't work in under a minute.

But, to understand why it doesn't work, you have to understand how memory is laid out in C and C++, and to understand intuitively the concept of a pointer.

Some people like pictures and drawing out pictures. Other people like to watch the MIT OpenCourseware - I recommend giving it at least a try.

class node
{

  int data;
  node* next;

  node* addnode()
  {
    node newnode;
    this->next = &newnode;

    return &newnode;
  }
};

This is an approximation of a (bugged) implementation of a linked list I wrote about 10 years ago when I was learning data structures.

And as a final note, practice and theory are the yin and yang of a quality programmer/developer/computer scientist. You can't be truly proficient without both.

Answer 17

When I taught programming, I always referred the Demystified books to my students.

I suggest you read:
- Data Structures Demystified
- OOP Demystified

These two books do a good job at breaking down data structures and OOP principle in simpler easy to read terms, with easy to follow examples. It's a good overview, but it does not go into the data structures supplied by the STL.

Answer 18

If you have problems with the O-notation, then 'Introduction to algorithms' by Cormen et.al. introduces these theoretic concepts in an easy to understand style. Well, this book is basically the bible for basic data structures. The proofs of runtime/space bounds are always presented in a very instructive fashion.

As always, if you study such book, do not just read it, but try to work on most of the exercises. Usually, doing this is very effective for learning the stuff.

Another general technique: try to join a local study group of 2-3 other students - usually, discussing the material with others (face to face) and while trying to explain the self-studied material to peers gives you a lot of hints, which things you need to cover more.

To master C++ for the exercises, 'The C++ Programming Language' by Stroustrup gives a good introduction and reference to the various language concepts. Since C++ is such a multi-paradigm language, beginners often are confused what of the concepts actually to use in practice to solve certain problems. To help with that 'Effective C++' by Scott Myers is a good start.

If your course makes heavy use of the STL, then there is 'Effective STL' as well. Scott Myers writing style is usually regarded as very 'fitting' for beginners.

Answer 19

One thing you always need to remember, is that data structures don't just exist. They were invented to fit a need, which therefore means they are good for some reasons, but not for others.
Find out what those reasons are, what the data structure is good for, try to figure out the Big O for the operations before you will be told them.
Always compare data structures. Even with the simplest of them - An array. Take that as a starting point, and compare every data structure you find to an array. Sometimes you`ll find little tricks which help you avoid using the big data structure altogether.
For me, what helped me understand a lot of data structures and algorithms was the applet here, and I hope it will help you too: Applet

Answer 20

To me the best book I've found (so far) for understanding data structures is Steven Skiena's The Algorithm Design Manual.
Aside from the first part covering algorithm analysis, algorithm & data structures the second part is absolutely invaluable in finding (or at least narrowing down) the proper data structure/algorithm for solving a problem.

Answer 21

Donald Knuth's "The art of computer programming", vol 1.