- Single Linked List - Single linked lists are a data structure that implements items that form a list based on their
relationships. The term single linked list comes from the property that each item in the list only points to the next
item in the list. This is a single link that connects these two items. The link between these two items can only be
traveled in one direction.
The items that are contained in the list are held in objects called 'Nodes'. These nodes hold a link to the data that
is the item in the list. Below illustrates the relationship between Nodes, their data and each other.
The image represents the pointers of a single linked list. Each node has
a pointer to the next node in the list and and pointer to the data it holds.
Having each node in the list only have to maintain a pointer to its next node the list can be held in a single variable.
This node is called the head node. This is the beginning of the list. Every item in the list can be found using the head
node. Some single linked list implementations also include the use of a tail pointer. The cost of this varies for different
algorithms. Maintaining a tail pointer adds costs to other simpler algorithms however it does provide a very simple
means of implementing an add last algorithm.
Breaking List Relationships - Breaking a link between nodes cuts the list into two separate lists, however if
each side is not accounted for they will become broken. Representing this concept is easily done with blocks and
string. Below is an example of blocks 'A', 'B' 'C' and 'D' connected together by string. The first block is secured
to the head.
The images above symbolize the single linked list concept through the relationships between
blocks connected together with string to maintain the blocks from falling
The first image represents a fully linked list. The blocks are secured together by the link of the node before it. If a
link is removed ( second figure ) the list becomes broken. The link from block 'B' was set to null this represents
the block 'C' being removed from the string connected to block 'B'. This results in blocks 'C' and 'D' falling off of the
list. Note that theoretically block 'C' still contains its link to block 'D' however there is no way to reference block 'C'
unless a variable is holding a reference to block 'C' before the link from block 'B' to 'C' was destroyed. The last figure
represents an empty list. The head pointer is null and does not contain any blocks. The blocks are now unreferenced
- Current Projects -