A data structure combines data organization with methods of accessing and manipulating the data. For example, an ArrayList
is a data structure for storing a list of elements and provides methods to find, insert, and remove an element. At a very abstract level, we can describe a general “list” object. A list contains a number of elements arranged in sequence. We can find a target value in a list, add elements to the list, remove elements from the list and process each element of the list.
An abstract description of a data structure, with the emphasis on its properties, functionality, and use, rather than on a particular implementation, is referred to as an Abstract Data Type (ADT). An ADT defines methods for handling an abstract data organization without the details of implementation.
A "list" ADT, for example, may be described as follows:
Data organization:
- Contains a number of data elements arranged in a linear sequence
Methods:
- Create an empty List
- Append an element to List
- Remove the i-th element from List
- Obtain the value of the i-th element
- Traverse List (process or print out all elements in sequence, visiting each element once)
- An
ArrayList
object contains an array of object references plus many methods for managing that array. The most convenient feature of an ArrayList
is that you can keep adding elements to it no matter what size it was originally. The size of the ArrayList
will automatically increase and no information will be lost.