An Introduction to Data Structures

Linked Lists

Suppose you are maintaining a vector of sorted objects (such as employees)
- Many elements will need to be shifted back if an new object is inserted in the middle.
- Many elements will need to be shifted forward if an object is deleted from the middle.
Moving a large number of records can involve a substantial amount of computer time.
Rather than store a sequence of values in one long block of memory (like a vector or an array) a linked list stores each value in its own memory block, together with the locations of the neighboring blocks in the sequence.