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.

Under the hood of a linked list

Arrays and linked lists: A comparison

Singly linked lists

Orders management

Implementing singly linked lists

Insert

Search

Delete

Delete from the front of the list

Sorted linked lists

Insert in the middle

Can we improve search?

Doubly linked lists

Twice as many links, twice as much fun?

The importance of retracing your steps

Insert

Search and traversal

Delete

Concatenating two lists

Circular linked lists