What is insertion in C programming?

Answer 1

Insertion is an operation that inserts a new datum (an object or data element) into a data container. How this is achieved depends on data container's type.

The simplest container is an array. In order to insert a new element into an array there has to be space to accommodate the new element. Free space is always allocated at the end of the array as it is easier to keep track of which elements are in use when all the unused elements are at the end of the array. If there is no free space, the array must be reallocated to make space. Reallocation can be an expensive operation so we typically double the allocation on each reallocation. Since all the free space is at the end of the array, it is trivial to push new elements onto the end of the array in the first unused space. If we need to insert anywhere else in the array, we use a single-pass insertion sort algorithm to move the unsorted element (the new element) into its correct position within the sorted set (the used elements). This essentially moves every element that should come after the new element one position to the right, towards the end of the array, starting with the last element. Once all elements are moved we can insert the new element into the gap we created.

With a singly-linked list, the most efficient insertion is to insert at the head of the list. This is achieved by pointing its node at the head node and making the new node the new head of the list. If we need to insert elsewhere, we must traverse the nodes to locate the node that comes before the new node. We then point the new node at that previous node's next node and point the previous node at the new node.

With a doubly-linked list we can insert at either the head or the tail and can traverse in either direction to locate any other insertion point. Again, adjusting the affected node pointers completes the insertion.

Stacks always insert on the top of the stack (typically implemented as singly-linked list where all insertions occur at the head). Queues always insert at the end of the queue (typically implemented as a circular singly-linked list where we keep track of the tail which points back at the head node for extractions).