Hello all. I'm in the last couple of weeks of my Data Structures and Algorithms C++ class. I need help. I can't like...wrap my head around some of these more complex data structures like Binary Search Trees, LinkedLists and others. Like how do I implement them and use them in a problems. Any suggestions for reading, or better yet interactive lessons on these things would be appreciated.
I find it useful to think about linked lists and binary search trees as recursive data types. For example, a list is either: (a) the empty list; or (b) a non-empty list consisting of an element (the head of the list) and another list (the tail of the list). If you think about the recursive structure of a linked list, its applications are immediate: a linked list provides O(1) access to its head and tail and O(n) access to arbitrary elements, because a linked list is a linear arrangement of data. In other words, a linked list arranges data in such a way that accessing the most recently inserted element is trivial, but accessing arbitrary elements takes time proportional to the length of the list. When you think about applications of a linked list (as opposed to an array), the question you should ask is: do I need to to efficiently access arbitrary elements, or merely the most recently accessed element? If you are only performing linear operations on your data, a linked list might be appropriate; if you need randomized access, an array might be better. The same considerations apply to binary search trees, except that (unbalanced) binary search trees can access elements more efficiently when their inputs are randomized. In the worst case, binary search trees have the same complexity as linked lists.
This doesn't really help with the implementation, but I really think considering the "shape" of your data structure is helpful. The implementation follows pretty trivially by considering the shape of the data structure you want to implement (assuming you are working in a standard programming languages).
Last edited: