1.5 Dynamic Data Structures1.4.1 Partitioning the Array1 Algorithms and Data Structures in Java1.5.1 List Nodes

1.5 Dynamic Data Structures

Arrays have certain disadvantages as data structures. In an unordered array, searching is slow. In an ordered array, inserting a new element is slow (because all elements after the inserted element have to be shifted by one position to the right) and also deleting an element is slow (because we have to shift all elements after the deleted element one position to the left). Last but not least, the size of an array cannot be changed after creation.

In this section, we will look at a data structure that solves some of these problems: the  linked list. After arrays, linked list are the second most commonly used general-purpose data structure. They are mainly used in cases where elements are frequently inserted respectively deleted and/or it is

Lists are used for frequently inserting and deleting an unpredictable number of elements.
hard to predict the number of elements to be stored. They are not used for fast searching; for this purpose, there exist better data structures (search trees, hash tables) with which we will deal in a subsequent course.
© Wolfgang Schreiner; February 3, 2005

1.5 Dynamic Data Structures1.4.1 Partitioning the Array1 Algorithms and Data Structures in Java1.5.1 List Nodes