A Common-Sense Guide to Data Structures and Algorithms

Insertion

Insertion is one operation in which linked lists can have a distinct advantage over arrays in certain situations. Recall that the worst-case scenario for insertion into an array is when the program inserts data into index 0, because it then has to shift the rest of the data one cell to the right, which ends up yielding an efficiency of O(N). With linked lists, however, insertion at the beginning of the list takes just one step—which is O(1). Let’s see why.

Say that we had the following linked list:

If we wanted to add "yellow" to the beginning of the list, all we would have to do is create a new node and have it link to the node containing ...