To learn how to use the linked lists provided in the standard library
To be able to use iterators to traverse linked lists
To understand the implementation of linked lists
To distinguish between abstract and concrete data types
To know the efficiency of fundamental operations of lists and arrays
To become familiar with the stack and queue data types
Up to this point, we have used arrays as a one-size-fits-all mechanism for collecting objects. However, computer scientists have developed many different data structures that have varying performance tradeoffs. In this chapter, you will learn about the linked list, a data structure that allows you to add and remove elements efficiently, without moving any existing elements. You will also learn about the distinction between concrete and abstract data types. An abstract type spells out the fundamental operations that should be supported efficiently, but it leaves the implementation unspecified. The stack and queue types, introduced at the end of this chapter, are examples of abstract types.
A linked list is a data structure used for collecting a sequence of objects that allows efficient addition and removal of elements in the middle of the sequence.
To understand the need for such a data structure, imagine a program that maintains a sequence of employee objects, sorted by the last names of the employees. When a new employee is hired, an object needs to be inserted into ...