concept · INFO-CS-ADS-042Singly Linked Lists
A singly linked list is a linked data structure in which each node stores data and a reference to the next node. Traversal normally proceeds in one direction, from the head toward the final node.
Explanation
Overview
A singly linked list is a sequence of nodes where every node contains a data field and a next reference. The next reference identifies the following node, while the final node points to null in a non-circular implementation.
Purpose
Singly linked lists are useful for representing dynamically changing sequences when forward traversal is sufficient and efficient insertion or deletion at the beginning is desirable.
Time complexity
accessByIndex: O(n); search: O(n); insertAtHead: O(1); insertAfterKnownNode: O(1); insertAtTailWithoutTailReference: O(n); insertAtTailWithTailReference: O(1)
Space complexity
O(n) for n nodes, with one next reference stored in each node.
Example
nodes: 10; 20; representation: HEAD → 10 → 20 → 30 → 40 → NULL; explanation: The head references the node containing 10. Each node points to the next node until the final node points to null.
Advantages
Simple node structure.; Requires only one reference per node.; Supports dynamic growth and reduction.; Efficient insertion and deletion at the head.; Does not require contiguous memory.
Limitations
Traversal is possible only in the forward direction.; Accessing a node by index requires sequential traversal.; Deleting a node generally requires access to its predecessor.; Searching takes linear time.
Example or application
Representation
HEAD → 10 → 20 → 30 → 40 → NULL
Explanation
The head references the node containing 10. Each node points to the next node until the final node points to null.
Definition
A singly linked list is a sequence of nodes where every node contains a data field and a next reference. The next reference identifies the following node, while the final node points to null in a non-circular implementation.
Purpose
Singly linked lists are useful for representing dynamically changing sequences when forward traversal is sufficient and efficient insertion or deletion at the beginning is desirable.
Node Structure
Data
Stores the value or information associated with the node.
Next
Stores a reference to the next node.
Conceptual Representation
[Data | Next]
Main Components
Head: Reference to the first node.
Node: Individual element containing data and a next reference.
Tail: The final node, whose next reference is null.
Null: Marks the end of the list.
Connection Pattern
Each node points only to its immediate successor. There is no built-in reference to the previous node.
Traversal
Traversal starts at the head. A temporary reference visits the current node and moves to its next reference repeatedly until it reaches null.
Insertion Methods
At the beginning: Create a node, point it to the current head, and update the head.
At the end: Find the final node, connect its next reference to the new node, and leave the new node pointing to null.
After a specified node: Connect the new node to the specified node's successor, then connect the specified node to the new node.
Deletion Methods
From the beginning: Update the head to reference the second node.
From the end: Find the node before the final node and set its next reference to null.
By value: Locate the target node and update the previous node's next reference to bypass it.
Advantages
Simple node structure.
Requires only one reference per node.
Supports dynamic growth and reduction.
Efficient insertion and deletion at the head.
Does not require contiguous memory.
Limitations
Traversal is possible only in the forward direction.
Accessing a node by index requires sequential traversal.
Deleting a node generally requires access to its predecessor.
Searching takes linear time.
Time Complexity
Insert After Known Node
O(1)
Insert At Tail Without Tail Reference
O(n)
Insert At Tail With Tail Reference
O(1)
Space Complexity
O(n) for n nodes, with one next reference stored in each node.
Implementation Considerations
Check whether the list is empty before accessing the head.
Handle insertion into an empty list correctly.
Update the head whenever the first node changes.
Maintain the tail reference if the implementation uses one.
Avoid losing references to nodes that must remain in the list.
Common Applications
Implementing stacks
Implementing simple queues
Representing graph adjacency lists
Maintaining dynamically changing sequences
Handling chains of connected records
Learning Objectives
Identify the structure of a singly linked-list node.
Explain forward-only connections.
Understand how traversal reaches each node.
Describe insertion and deletion methods.
Analyze common operation complexities.
Key Takeaways
Each node stores data and one next reference.
The head identifies the first node.
The final node points to null in a non-circular list.
Forward traversal is the standard access method.
Insertion after a known node can be constant time.
Related Topics
Introduction to Linked Lists
Doubly Linked Lists
Circular Linked Lists
Linked List Node and Memory Structure
Insertion in Linked Lists
Deletion in Linked Lists
Practice Questions
| Question | Answer |
|---|
What is the main purpose of singly linked lists? | A singly linked list is a linked data structure in which each node stores data and a reference to the next node. Traversal normally proceeds in one direction, from the head toward the final node. |
What should be checked before applying singly linked lists? | For singly linked lists, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of singly linked lists be validated? | Trace a representative singly linked lists case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures