The history of linked lists is long, with many implementation variations. Early lists often concentrated on economical use of memory (eg, single links). Bidirectional lists became the standard as memory prices dropped, and as OOP because the standard, the C++ STD list and Java LinkedList classes have replaced hand-made lists and replaced the link implementation details with iterators.
Linked lists are favorite topics of textbooks, and really wonderful exercises for learning to work with pointers, but don't even think about using your own lists. Use the library lists instead.
When memory was scarce, small data structures were critically important. It's still important, but if using a little extra memory can be used to make algorithms easier, it's worth it. Some problems with singly-linked lists:
If the last element is linked to the first, the entire list forms a ring, there are no longer any special end cases. The "end" of the list is when you get back to the starting point. This eliminates the concept of front and back of the list, which may or may not be an advantage.
A solution to the above problems is to add an extra link in to the previous element in each node. The memory cost is generally considered worth the convenience it buys. A node might be declared as follows (non-OOP):
// Node for doubly linked list of floats.
struct Node {
Node* next; // Pointer to next element
Node* prev; // Pointer to previous element
float data;
};
The common operations of inserting and deleting become easy. There are still some problems that remain.
Doubly linked lists still have end point problems that can be solved but making them circular. Problems still remain.
The advantage of a dummy node is that there is a reference point to identify the front and back.
Secondly, there is something in the list even when the list is empty. The advantage of this may not be immediately obvious, but having a pointer to this dummy element represent the list allows list manipulations to take place without having to store back into this pointer.
Lists are represented by an object that contains little more than a pointer to the list elements. You might think of it as a pointer to a dummy node in a circular doubly linked list. The beauty of OOP is that the implementation can be completely hidden Movement around the list uses an iterator, which hides the implementation details of the node and pointers.