Singly-linked lists: Insert

Insertion is one of the fundamental operations of a singly-linked list. There are several ways to insert a new element into a singly-linked list, depending on the position where the new element should be added.

Here are some common ways to insert an element into a singly-linked list:

Insert at the head of the list: To insert a new element at the head of the list, create a new node containing the new element and set its next pointer to the current head of the list. Then, set the head of the list to the new node.
Insert at the tail of the list: To insert a new element at the tail of the list, create a new node containing the new element and set its next pointer to nullptr. Then, traverse the list from the head to the tail and set the next pointer of the last node to the new node.
Insert at a specific position: To insert a new element at a specific position in the list, traverse the list from the head to the node immediately before the position where the new element should be added. Then, create a new node containing the new element and set its next pointer to the next node. Finally, set the next pointer of the previous node to the new node.

Here is an example implementation of a function to insert a new node at the head of a singly-linked list in C++:

template <typename T>
void insertAtHead(SinglyLinkedListNode<T>*& head, T value) {
    SinglyLinkedListNode<T>* newNode = new SinglyLinkedListNode<T>(value);
    newNode->next = head;
    head = newNode;
}

n this example, we define a function insertAtHead that takes a reference to the head of the list and the value of the new element to be added. The function creates a new node containing the new element and sets its next pointer to the current head of the list. Finally, the function sets the head of the list to the new node.

This function can be called like this:

SinglyLinkedListNode<int>* head = nullptr;
insertAtHead(head, 1);
insertAtHead(head, 2);
insertAtHead(head, 3);

This code creates a singly-linked list with three nodes containing the values 3, 2, and 1, in that order.