A linked list is a linear collection of data items where each item has some form of link connection to other items. A more low-level explanation is that linked lists are chunks of memory that are bound together by pointers.
The Lingo:
- The items within a linked list are called nodes
- Linked lists are usually implemented with a head and tail node
- A tail represents the last node of a linked list
- The head of a linked list refers to the first node
Pros and cons
Pros ✅
- Linked lists can have constant time for operations like insertion/deletion at the head or tail
- Dynamic at runtime
Cons 👎
- Accessing elements by index requires traversing the list
- Extra space for pointers
Linked Lists vs. Arrays
- Arrays have better memory locality and cache performance. This is because linked lists have a random pointer jumping characteristic whereas arrays have contiguous traits.
- Linked lists do have better time complexities when performing insertion or deletions at head and tail depending on its implementation.
Pros & cons
Pros ✅