Linked Lists - A Concise and Practical Introduction to Programming Algorithms in Java - page 145

7
Linked Lists

7.1 Introduction

Linked lists allow us to structure input data sets into elementary units by
chopping the data-sets into its many individual elements that are stored in
corresponding cells . Cells are all chained together into a single thread of cells,
starting from the head to the tail. These chained cells can be manipulated
dynamically by either adding or removing elements. These operations can be
carried out e ciently (in constant time O (1)) by creating new cells or deleting
some cells of the list. Linked lists are therefore preferred to arrays whenever we
do not know a priori the input size. This is all the more interesting for sorting
and searching operations that consider dynamic data sets in practice.

7.2 Cells and lists

7.2.1 Illustrating the concepts of cells and lists

Consider an arbitrary set of objects for which we would like to

create a linked list data-structure. A cell is an elementary structure consisting
of two fields :

O = { O 1 , ..., O n }

- The first field is used for storing the considered object. Thus the first field
plays the role of container.