Insertion
Admittedly, linked lists have yet to impress us from a performance standpoint. They’re no better than arrays at search, and much worse at reading. But not to worry—linked lists will have their moment. In fact, that moment is now.
Insertion is one operation in which linked lists 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 first 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 we have the following linked list:
If we want to ...
Get A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
