You have a list. There are a number of things you can do with that list structure. You should really understand how it works. You should understand when deletion occurs. You can try to create lists on the fly, off the heap. You got new lists and then you have to principally delete lists, or when the lists go out of scope, then the destructors are automatically invoked. If you want, you can put into the destructor some prints so that you can actually see when things are invoked. That's very useful if the whole concept is new to you. I recommend playing with that a lot. And then the other thing that would be very useful, recall that I asked that everybody here have a background in basic computer science and data structures. so, all of you with that background, should readily be able to convert that singly-linked list to a doubly linked list. Okay, so now in this next topic the standard template library (STL), which indeed has lists, actually the most, it actually now in C++ 11 it has both a singly linked list and a doubly linked list. But the principle data structure it has, and the thing I want you to study the most, is vector. Vector is the most used type. Vector again, from my perspective is where you get 90% of your value. So if you learn vector, you'll get 90% of the value in the container, and understanding container classes. I should say, sequential container classes. So normally in C, we did everything with these very raw, native arrays. Native arrays. They were very primitive. really, and remember C was systems implementation language. It wasn't to be used for a lot of data processing, so Ritchie did not put a lot of effort into making arrays convenient to use. So an array was really just a pointer, and then the pointer was provided with some allocated memory. The allocated memory could come off the heap through a calloc or a malloc Or the allocated memory could come through a specific stack-based declaration, where there was an integer constant amount of memory known on stack entry. So it was a very simple scheme. because he didn't require the system implementation language. But, that's far too limited and too error prone for doing very complicated data rich computation. So, one of the first and most successful kinds of containers is. An abstraction of an array, in which you not only have the ability to dynamically size the array, you have ways of making sure you don't get any kind of indexing errors. Because you also can know where the beginning and end of a vector is. And so, one recommendation to becoming a real C++ programmer is abandon your use of basic C arrays and turn all of that processing into vector. There's also a list, a list is another sequential array. Then when you go for a list as opposed to an s list, you get doubly-linked lists, and the doubly-linked lists look like the code we just looked at, except. You'll have a data element, you'll have a previous pointer and you'll have a next pointer and this lets navigation go bidirectionally. So this could be navigated bidirectionally. And that makes a lot of algorithms more convenient, because sometimes you want to stop and you want to back up, and you don't want to have to always be starting at the beginning of an array,( no eh, ) excuse me, the beginning of a list. So, the list is very good for operations like insertion and deletion. It's not so good when you have to get to an element that's somewhere deep in the list because that's an order-n O(n) computation. For a vector this is an order one O(1) {constant time} computation, which is very efficient to look up the nth element. (<vector> Dominate s <list> for lookup.) So, vectors tend to dominate in the general world of data processing because you have this ability to random access. But lists have very important uses where you need to not only expand but possibly shrink. And insert and you have a fair amount of insertion and deletion and then the balance is tipped. The efficiency balance is tipped from vector to list. And more complex computations, truthfully, will use both types of these container classes. So that's again available on STL and something you should get very used to understanding and using. Okay. if you're out there on a forum, you may want to discuss some of how we are working on homework 2. Remember, homework two is to do a Dijkstra's algorithm for shortest paths in which you generate your graphs at random and the graphs are not only generated at random, but they have a density. The density means the average number of edges over how many edges can be in a complete graph. So, in a complete graph of size n, you can have n minus one ordinary edges out of any node. And if you wanted a density of 10%, you would have 10% of that. So, if you had 101 nodes, 10% would be, you would have 10 edges on average for each node. And that would be a parameter into our graph generating algorithm that we're using to test the the Dijkstra algorithm.
