6 Linked lists: A flexible dynamic collection
In this chapter
- what linked lists can do better than arrays
- singly linked lists are the simplest version of linked lists
- doubly linked lists make it easier to read the list in both directions
- circular linked lists are good at handling periodic or cyclic data
In chapter 5, we discussed how static arrays have a weak spot when it comes to flexibility. Dynamic arrays may give us an illusion of flexibility, but, unfortunately, they are not a different (and flexible) data structure. They are just a strategy to resize static arrays as efficiently as possible. As discussed, the ability to resize arrays comes at a cost—slower insertion and deletion.
This chapter discusses yet another way of having a data structure that can be resized whenever needed, namely, linked lists. We will look at both singly linked lists (the simplest version) and doubly linked lists, which trade memory for better performance on some operations. As with dynamic arrays, we will find that there is again a price to pay for this flexibility, only this time, it’s a different price.
Linked lists vs. arrays
It makes sense to start our discussion by making a comparison between linked lists and arrays. After all, we already have a data structure that can hold data and on which we can perform insert, delete, and search operations. Furthermore, we can traverse an array, that is, we can read its elements sequentially and perform some operation on each of the elements.