Think together · Start with a story
A girl puts treasure clues in several boxes. Each box also tells her where to find the next one.
Break down the process
- Node AData and a link to B
- Node BData and a link to C
- Node CMarks the end
Linked-list nodes store data and connection information.
Nodes do not have to sit next to each other in memory. Follow the links to move from one node to the next.
01Arrays are contiguous—but how else can data be organized?
Arrays store elements next to each other in memory. Another approach is to let each element keep information about how to reach the next one.
02What is a node?
A node is one unit in a linked list. It stores its data and one or more links to other nodes.
03What does a singly linked list look like?
The last node has no next node, so its link is empty.
04Do linked-list nodes have to be next to each other?
No.
Unlike an ordinary array, linked-list nodes can be at different memory locations, as long as the link information can find the next node.
05How do you find the third node?
In a singly linked list, you usually start from the head:
You cannot jump to the target by writing “starting address + index offset” as you can with an array.
06Why are linked lists suited to changing connections?
Once you have found the relevant nodes, inserting or removing one often requires changing only a few links.
But remember: finding the insertion position may still require traversal.
07Are linked lists always better than arrays?
Array
Easy random access, contiguous storage, and often better cache behavior.
Linked list
Flexible connections, but each node needs extra link information and traversal locality is often worse.
What you have learned
- A linked list consists of nodes and connections between them.
- A singly linked-list node usually points to the next node.
- Linked-list nodes do not need to be stored contiguously.
- Accessing an element by position usually requires traversing from the front.
- Changing a link and finding a position have different costs.
Next: What Is a Tree?
Your turn to try
If you only know the first node, can you usually jump straight to the 100th node as you can with an array index?
Ready? Open to see the explanation
No. An ordinary linked list usually requires following the connections one by one to get there.