Singly linked list in C++
Educative Answers TeamA singly linked list is a type of linked list that is unidirectional, i.e., it can be traversed in only one direction from the head to the last node (tail).
Each element in a linked list is called a node. A single node contains data and a pointer to the ​next node, which helps to maintain​ the structure of the list.
The head is a pointer that points to the first node of the list and, hence, helps us traverse the list. The last node (also referred to as the tail) points to NULL, which helps us in determining when the list ends.
Common singly linked​ list operations
1. Search for a node in the ist
You can determine and retrieve a specific node from the front, end, or anywhere in the list.
The worst-case​ Time Complexity for retrieving a node from anywhere in the list is O(n).
2. Add a node to the list
You can add a node at the front, end, or anywhere in the linked list.
The worst-case Time Complexities for performing these operations are:
- Add an item to the front of the list: O(1)
- Add an item to the end of the list: O(n)
- Add an item a​nywhere in the list: O(n)
