Chapter 27 Linked Lists
So far we have used arrays to store multiple items of the same data type. There are several situations you can imagine in which this is not ideal. Here are two such scenarios:
- One problem with this method is that you have to declare the array in question (in your code with a fixed size or at runtime using dynamic memory allocation) and whichever way you do so, by the time you first use the array its length is locked in. Then what are you options if your array is full and you wish to add in another record? The only choice would be to ask for space for a bigger array, copy all of the information over and then add the new record. This is not exactly efficient.
- Next, imagine that your array contains records that have been sorted by some criterion. Suppose you wanted to add a new record, and it would have to go somewhere in the middle of your array in order to maintain the sorting. You’d then have to move over all of the records that need to come after the new record in order to make room for the new record. Again, this is not a very efficient way to go about things.
This is where linked lists might present a better way to store your data. A linked list provides a linear ordering of records without them having to be physically arranged that way in memory. In other words, rather than using the records’ arrangement in memory to determine their ordering, each record keeps track of the location of the record that is to follow it in the linear ordering. This will all become clear shortly.
In this chapter, we will cover the following topics:
- Linked lists
- Passing linked lists to functions
- Simplifying and automating the creation of linked lists
- Using linked lists to store extremely large numbers
- Manipulating linked lists (i.e. search, sort, reverse)
