Here’s a very simple implementation of the linked list data structure.
A pointer to the head element is enough to define a linked list. Each element consists of one pointer to the subsequent element in the list and one pointer to the element’s data:
A doubly linked list is like our previously implemented Linked List, but instead of only having pointers to the next element, it also has pointers to the _previous _element:
This property makes the doubly linked list very useful as a base for other data structures such as the stack: having a previous pointer means we can quickly (O(1)) remove objects from the list’s tail, which would be impossible with a linked list.
We won’t discuss implementation since it so similar to a linked list. If anything implementation is even simpler than a linked list because of the previous pointer access.
