DataTerminology.comNEW
A linear data structure where elements contain references to the next node, allowing efficient insertions and deletions.
DESCRIPTION
A linked list is a sequence of nodes where each node holds data and a reference to the next (and sometimes previous) node. Unlike arrays, linked lists have non-contiguous memory layouts and support efficient insertions and deletions. Variants include singly and doubly linked lists, circular lists, and skip lists. Iteration is sequential, making random access O(n). Linked lists are fundamental in language runtimes, compilers, and embedded systems.
ALTERNATIVE DEFINITIONS
Wikipedia
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory, instead each element points to the next.
Highlights non-contiguous memory and pointer-based ordering.
GeeksforGeeks
A linked list is a linear data structure where each element is a separate object. Each element (node) of a list is comprising of two items - the data and a reference to the next node.
Emphasizes node structure and separation of data and references.
Oracle Java SE
LinkedList class implements the List interface, allows all elements including null, and provides methods for insertion, removal, and retrieval of elements.
Describes a concrete implementation in Java’s standard library.
RELATED TERMS
Node Pointer Doubly Linked List Singly Linked List Stack Queue Traversal Insertion Deletion
COMPETING TERMS
RELATIONS
- Broader: List
KNOWLEDGE AREAS
Software Engineering Programming Languages
TARGET AUDIENCE
Software Developer Full Stack Developer Software Architect Data Engineer
EXTERNAL SOURCES
- Wikipedia - Linked list
- Wikipedia - Canonical overview
- Oracle - LinkedList Java API reference
- GeeksforGeeks - Intro tutorial with examples
TOP QUESTIONS
When should a Linked List be used over an Array?
Use linked lists for frequent insertions/deletions and when contiguous memory is unavailable. Arrays are better for random access and cache locality.
Category: Opinion
What is the time complexity of Linked List operations?
Insertion/deletion at known positions is O(1); random access and search are O(n).
Category: Definition
What are common mistakes with Linked Lists?
Forgetting to update pointers, causing memory leaks or cycles; mishandling head/tail updates during deletion.
Category: Mistakes
What risks come with Linked Lists?
Poor cache locality and overhead of pointers hurt performance. They can fragment memory.
Category: Risks
How does a Doubly Linked List differ?
It adds a pointer to the previous node, enabling O(1) deletion with known node and bidirectional traversal.
Category: Definition
How is iteration implemented for Linked Lists?
Traverse from head to tail using next pointers, stopping on null or when returning to head for circular lists.
Category: Tutorial
What’s a real-world use of Linked Lists?
Implementing queues, adjacency lists in graphs, or undo stacks in editors.
Category: Example
Can Linked Lists be memory efficient?
With compact node layouts and pooled allocators they can be efficient, but arrays often win for dense data.
Category: Opinion
How do skip lists relate to Linked Lists?
Skip lists add hierarchical forward pointers to achieve expected O(log n) operations.
Category: Definition