Ok, I have read about initialization lists. I have another question about line 11. Line eleven is the node constructor. It initializes data with the value t of type "T". I dont understand why "prev" and "next" are being initialized with pointers though. Isn't that saying that:
T data= T t
node* next=node* n//I don't understand the significance of setting
node* prev=node* p// next and prev to n and p.
I don't understand the significance of setting next and prev to n and p.
The regulars here may well correct me (which would be awesome, btw), but first to answer your question: the point of linked lists is to make swapping elements efficient -- in particular, to swap any two nodes, you'd just swap the next and prev pointers of the nodes and their neighbors, rather than swapping the contents and leaving the nodes in place. You can draw it on paper as a set of boxes with content-values and arrows pointing from each to its previous and next boxes, and swap nodes (or insert, or delete, or whatever else) by erasing old arrows and drawing new ones so that following the arrows results in the correct new order.
Really not related, other than the question about whether to use pointers, because of the need to know a consistent size to allocate and compute index offsets, a polymorphic STL vector<> of objects needs to store pointers rather than instances. A specific example is wanting to store a list of Shape instances, where a specific shape would be an instance of subclass Triangle, Circle, or ZanyShape. You can't specify std::vector<Shape> because the compiler won't know how to grow/index the vector for different kinds of shapes, so instead (since a pointer is always the same size):
Circle *c = new Circle(args);
the point of linked lists is to make swapping elements efficient
Any linked data structure has that benefit, but it's not the point of linked lists. I'd argue that the point of a linked list is the principle benefit, which would be efficient growth (ie. insertion and deletion) in the absence of random access.
This is the answer to idcristi's question. Since the list is generic, nothing stops you from storing a pointer type (it doesn't have to be polymorphic). Just like using pointers to speed up the passing of parameters, the same solution can be used to speed up the management of list data items.
Replacing T data with T *data actually makes the list less generic, and introduces some tricky pointer management problems.
 In fact, beyond the fundamental insertions and deletions, link surgery isn't as common in linked lists as you might think. Linked lists are generally reserved for simpler tasks where complex structure changes are unnecessary.
In fact, beyond the fundamental insertions and deletions, link surgery isn't as common in linked lists as you might think. Linked lists are generally reserved for simpler tasks where complex structure changes are unnecessary.
Good point. While a fairly common recurring "programming test" given during interviews is "write code to reverse a singly-linked list", link surgery (as you so aptly put it) tends to show up more in maintaining a heap or a sorted-and-balanced tree of heavy-weight objects. But it's easier (for me, anyway) to start thinking in just the one-dimensional linear world of a list before getting more involved. Thanks for the additional insights!
>>Any linked data structure has that benefit, but it's not the point of linked lists. I'd argue that the point of a linked list is the principle benefit, which would be efficient growth (ie. insertion and deletion) in the absence of random access
I would like to point out one thing, in theory insertion/deletion is constant in a usual linked list implementation, but however one should think about it practically. Since the memory is all over the place in linked list, its not cache friendly, thus causes( or can cause ) a lot more cache misses, which would increase the latency time. Thus when you think you need linked list, you might be able to get away with using an array, especially if the order doesn't matter. If the order doesn't matter then you can achieve constant insertion and deletion with arrays too!! And its cache friendly. But as usual, it all depends. Its just a thought I figure to share.
I am working creating a fully encapsulated, homogeneous singly linked data structure. The Listing class and SinglyLinkedList class that are part of the whole application compile fine, but the problem ...