Linked List Data Structure
A linked list is a data structure that is made up of a group of nodes that are connected to eachter.
A node often contains:
- Some data.
- A pointer to the next node in the linked list.
The head of the linked list is a pointer to the first node in the list.
While the tail of a linked list is a pointer to the last node
Here's an example of a linked list of numbers:
In Python, the above linked list can be implemented below:
We are left with
tailto access data in the linked list.
Linked List Big O Overview
Note to get to another node, for example the third node, we must iterate through each node's
nextpointer until we reach the third one.
Linked List Pros
- Append to the end of the list in constant time
new_node = Node(data)tail.next = new_nodetail = new_node
- Similarly, prepend in constant time
new_node = Node(data)new_node.next = headhead = new_node
- A linked list doesn't need a preset size since new nodes can be added any time.
Linked List Cons
The main con with a linked list is that accessing any other node costs
Another con is that since nodes in the list aren't necessarily in contiguous location in memory, which makes it not cache-friendly.