Linked Lists in C#
Introduction to Linked Lists
A Chain of Data
Imagine a scavenger hunt. You start with a clue that tells you where to find the next one. You follow it, find the second clue, which points you to the third, and so on, until you reach the final prize. A linked list works in a similar way. It's a fundamental data structure for storing a sequence of items, but with a twist.
Unlike an array, which keeps all its items in a single, contiguous block of memory (think houses side-by-side on a street), a linked list is made of individual elements called nodes. Each node can be stored anywhere in memory.
node
noun
An individual element in a linked list that contains two pieces of information: the actual data it's storing and a pointer, or reference, to the next node in the sequence.
Each node holds a piece of data and a pointer that acts as the "clue," telling you the memory address of the next node in the chain. The first node is called the head, and the last node points to null to signify the end of the list.
Linked Lists vs Arrays
So why use a linked list instead of a simple array? It comes down to flexibility. Arrays are rigid. When you create one, you have to decide its size upfront, and it needs a single, unbroken chunk of memory to live in. If that chunk isn't available, you're out of luck.
Linked lists are dynamic. They can grow or shrink as needed because each node is allocated independently. This makes them incredibly efficient for situations where you'll be adding or removing elements frequently. To insert an item into the middle of an array, you have to shift every element that comes after it. With a linked list, you just need to adjust a couple of pointers.
The main drawback is access. To get to the 50th element in an array, you can jump there directly using its index. In a linked list, you must traverse the list from the head, following 49 pointers to find the 50th node. This is known as sequential access, and it can be much slower.
| Feature | Array | Linked List |
|---|---|---|
| Memory Layout | Contiguous block | Can be scattered |
| Size | Fixed | Dynamic (can grow/shrink) |
| Insertion/Deletion | Slow (requires shifting) | Fast (requires pointer changes) |
| Element Access | Fast (random access via index) | Slow (sequential access from head) |
Choosing between an array and a linked list depends on what you need to do. If you have a fixed number of items and need to access them quickly by their position, an array is a great choice. If your list size will change a lot and you'll be doing many insertions and deletions, a linked list is often more efficient.
Let's check your understanding of these core concepts.
What are the two essential components of a node in a standard singly linked list?
What is the primary advantage of a linked list over an array when it comes to memory allocation?
This fundamental trade-off between access speed and modification flexibility is a core concept in computer science.