✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-042

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.

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

Nodes

  • 10

  • 20

  • 30

  • 40

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

Access By Index

O(n)

Search

O(n)

Insert At Head

O(1)

Insert After Known Node

O(1)

Insert At Tail Without Tail Reference

O(n)

Insert At Tail With Tail Reference

O(1)

Delete At Head

O(1)

Delete By Value

O(n)

Traversal

O(n)

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

QuestionAnswer

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