Applied Programming/Lists and Tuples

Data Structure

What is it?

A way in which data are stored for efficient search and retrieval. Different data structures are suited for different problems. Some data structures are useful for simple general problems, such as retrieving data that has been stored with a specific identifier. For example, an online dictionary can be structured so that it can retrieve the definition of a word. On the other hand, specialized data structures have been devised to solve complex specific search problems.

Looking at basic examples is an effective way to understand data structures. For example, a very basic example of a data structure is an array, in which multiple data bits are coordinated into a group sharing a common label. This helps programs call these data bits or perform other work on the data set as a whole. Another example of a data structure is a stack, which places data units in relative hierarchies, allowing code functions to work on the data in coordinated ways, such as pushing a new data unit into a stack, or popping a data unit from the top of a stack.

In a general sense, the data structure concept dovetails with that of virtual objects and virtual reality. As data is more elaborately arranged by developers and others, the data becomes more functional, allowing the emergence of a virtual reality. This is a core concept of many technological advances from the last few decades.

Array Data Structure

What is it?

In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula. The simplest type of data structure is a linear array, also called one-dimensional array. Arrays are among the oldest and most important data structures, and are used by almost every program. They are also used to implement many other data structures, such as lists and strings. Arrays are useful mostly because the element indices can be computed at run time. Among other things, this feature allows a single iterative statement to process arbitrarily many elements of an array. For that reason, the elements of an array data structure are required to have the same size and should use the same data representation.

Indexing

Zero-based

Index starts with 0. Array length is equal to the number of elements the array can store. Zero-based arrays are zero-based because of math-related reasons. Not for hardware-related reasons.

One-based

Index starts with 1.

N-based

The base index of an array can be freely chosen. Usually programming languages allowing n-based indexing also allow negative index values and other scalar data types like enumerations, or characters may be used as an array index.

Dimensions

One-dimensional

A one-dimensional array (or single dimension array) is a type of linear array. Accessing its elements involves a single subscript which can either represent a row or column index.

days_week = ['Mon', 'Tues', 'Wed', 'Thurs', 'Fri', 'Sat', 'Sun']
print(days_week[1])

Output:

Tues

Two-dimensional

Two dimensional array is an array within an array. It is an array of arrays. In this type of array the position of an data element is referred by two indices instead of one. So it represents a table with rows and columns of data.

 random_array = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12, 15, 8, 6]]
 print(random_array[0])
 print(random_array[1][2])

Output:

[11, 12, 5, 2]
10

Tuples

A tuple is a data structure that is an immutable, or unchangeable, ordered sequence of elements. Because tuples are immutable, their values cannot be modified.

Cannot modify

 t = ('a', 'b', 'c', 'd', 'e')
 t[0] = 'A'
 print(t)

Output:

TypeError: 'tuple' object does not support item assignment

As a general rule, tuples use less memory than a list or array.

Tuples allows for slicing and indexing like lists, but do not have methods for deleting or changing any elements.

Indexing

 t = ('a', 'b', 'c', 'd', 'e')
 print(t[1])
 print(t[-1])

Output:

b
e

Slicing

 t = ('a', 'b', 'c', 'd', 'e')
 print(t[1:])
 print(t[:2])
 print(t[1:3])
 print(t[::2]

Output:

('b', 'c', 'd', 'e')
('a', 'b')
('b', 'c')
('a', 'c', 'e')

Activities

1) Create a program that compares two lists and returns "True" if those lists have at least one common element.

2) Create a program that compares two lists and identifies common elements. Display the index of these common elements for each list.

3) Create a program that reads a list and removes any consecutive and repeating elements. For example, ["A", "B", "C", "C", "D", "E", "E", "G", "E", "F"] would result in ["A", "B", "C", "D", "E", "G", "E", "F"].

4) Create a program that combines two lists into a single list by alternating elements from each list. For example ["A", "B", "C"] + ["1", "2", "3"] would result in ["A", "1", "B", "2", "C", "3"].

Key Terms

Array (list) - A data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.

Data structure - A collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Field - A particular piece of data encapsulated within a class or object.

Hash table -A type of data structure that stores key-value pairs. The key is sent to a hash function that performs arithmetic operations on it. The result (commonly called the hash value or hash) is the index of the key-value pair in the hash table.

Heap - A specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.

Index (key) - A numerical representation of an item's position in a sequence.

Linked list - A collection of elements called nodes, where each node has a value and points to the next node in the list (and sometimes the previous).

Member - A single datum of a record; for example, the 'Name' field of a 'Person' record.

Record (struct) - A structure used to collect multiple variables, often of different types stored as fields.

Tagged union - A union that contains one additional field indicating the current type for enhanced type safety.

Tuple - Similar to an array or list with the exception that they are immutable and enclosed in parentheses.

Union - A data structure where a number of primitive types may be stored in concert, similar to a struct or a record.