General Definitions in Data Structure

There are many different terms used in computer science. Some of these can have different meanings among the various textbooks and programming languages. To aide the reader and to avoid confusion, we define some of the common terms we will be using throughout the text.

A collection is a group of values with no implied organization or relationship between the individual values. Sometimes we may restrict the elements to a specific data type such as a collection of integers or floating-point values.

A container is any data structure or abstract data type that stores and organizes a collection. The individual values of the collection are known as elements of the container and a container with no elements is said to be empty. The organization or arrangement of the elements can vary from one container to the next as can the operations available for accessing the elements. Python provides a number of built-in containers, which include strings, tuples, lists, dictionaries, and sets.

A sequence is a container in which the elements are arranged in linear order from front to back, with each element accessible by position. Throughout the text, we assume that access to the individual elements based on their position within the linear order is provided using the subscript operator. Python provides two immutable sequences, strings and tuples, and one mutable sequence, the list. In the next chapter, we introduce the array structure, which is also a commonly used mutable sequence

A sorted sequence is one in which the position of the elements is based on a prescribed relationship between each element and its successor. For example, we can create a sorted sequence of integers in which the elements are arranged in ascending or increasing order from smallest to largest value.

In computer science, the term list is commonly used to refer to any collection with a linear ordering. The ordering is such that every element in the collection, except the first one, has a unique predecessor and every element, except the last one, has a unique successor.

By this definition, a sequence is a list, but a list is not necessarily a sequence since there is no requirement that a list provide access to the elements by position. Python, unfortunately, uses the same name for its built-in mutable sequence type, which in other languages would be called an array list or vector abstract data type.

To avoid confusion, we will use the term list to refer to the data type provided by Python and use the terms general list or list structure when referring to the more general list structure as defined earlier.

Leave a Comment