Data Structures... so how do I understand them? [closed]

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

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!