Linked List
Last updated
Last updated
A linked list is a data structure that stores a collection of objects in a sequential manner. Each item in list is stored in a node. Each node consists of a single piece of data (it is permissible for the data to be an aggregate type) along with at least one pointer to another node, typically the next node within the list. The linked list object itself must contain a pointer to a node within the list that will allow access to every other node by following the pointers in the node. Usually this is a pointer to the first node in the linked list.
If you wanted to store an array of 5 numbers in an array this is what the array would look like:
A simple linked list that stores the same 5 numbers in the same sequence would look like this
The above is a singly linked list. It is called this because there is a single pointer out of each node to another node.
Note that while the above diagram only has a single pointer out of the linked list object itself, it is not part of the definition of a singly linked list. The single link only refers to the link from one node to another
To look at how to implement a linked list, the operations a linked list can do should be considered. A linked list can typically support some subset of the following operations.
push_front - add an item to the front of the linked list
push_back - add an item to the back of the linked list
pop_front - remove the frontmost item from the linked list
pop_back - remove the backmost item from the linked list
insert - given a point within the list insert an item just before that point
erase - remove a node at a specific point within the list
erase(a,b) - erases all nodes between a and b
traversals - some operation that applies to every node in the list
To support the above operations, a linked list typically will store more information than the basic list. We will detail these in the implementation section
