Applied Programming/Lists and Tuples

This lesson introduces lists and tuples.

Objectives and Skills

Objectives and skills for this lesson include:

Readings

1. Wikipedia: Data structure
2. Wikipedia: Array data structure
3. Wikipedia: List (computer science)
4. Wikipedia: Record (computer science)
5. Python for Everyone: Tuples

Multimedia

1. YouTube: Python Tutorial for Beginners: Lists, Tuples, and Sets
2. YouTube: Multi-Dimensional Lists
3. YouTube: Introduction to Arrays
4. YouTube: Python - Looping Through Two Dimensional Lists
5. YouTube: Introduction to Linked List
6. YouTube: Data Structures: Linked Lists
7. YouTube: Difference Between List, Tuple, Set, and Dictionary in Python
8. YouTube: Tuples in Python: Create, Access, Concat, and More
9. YouTube: Python Tutorial: Sorting Lists, Tuples, and Objects

Examples

• Java
• JavaScript
• Python3

Activities

1. Download Northwind Customers. Write a program to read the file and create a customers list, where each element in the list is a customer list or tuple.
2. Provide an interface for the program above that allows the user to:
   • Display company name, contact name, and phone number for all customers sorted by company name.
   • Display contact name, company name, and phone number for all customers sorted by contact name.
   • Search for a given company name or part of a name and display matching records with fields labeled.
   • Search for a given contact name or part of a name and display matching records with fields labeled.
3. For each of the above, use separate functions for each type of processing. Reuse functions where possible, such as in sorting and searching. Avoid using global variables by passing parameters and returning results. Include appropriate data validation and parameter validation. Add program and function documentation, consistent with the documentation standards for your selected programming language.

Lesson Summary

• A data structure is a means to organize and store data for later retrieval and modification. It's typically implemented as a contiguous, homogeneous container of elements, either dynamic or fixed in size.
• Data structures include:
  • Arrays or associated arrays
  • Lists or linked lists
  • Records
  • Objects
• An array holds elements that can be randomly accessed through the use of an index—without the need for sequential traversal.
  • Typically, this index is zero-based, since the index is used to calculate an offset from the base address.
• A one-dimensional array is a type of linear array where access is limited to just one subscript which can either represent a row or column index.
• For a multidimensional array, the element with indices i, j would have address B + c · i + d · j, where the coefficients c and d are the row and column address increments, respectively.
• Arrays are used to implement mathematical vectors and matrices, as well as other kinds of rectangular tables. Many databases, small and large, consist of (or include) one-dimensional arrays whose elements are records.
  • Arrays can be used to implement other data structures, such as lists, heaps, hash tables, deques, queues, stacks, strings, and VLists.
• Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms.
• A list can often be constructed by writing the items in sequence, separated by commas, semicolons, and/or spaces, within a pair of delimiters such as parentheses, brackets, braces, or angle brackets. Lists are then able to expand and shrink. They are stored dynamically in memory.
• A list is an abstract data type—a mathematical model for implementing a concrete representation—that holds a finite number of items or elements.
  • Often, this is realized through the use of a linked list data structure, where each node contains not just data but also a link to the next (and sometimes previous) node.
  • Lists can hold data, but they can also contain any number of sublists, which are capable of having their own sublists further down the chain.
• A record is a data structure that collects together different variables, usually of different types.
• A record may sometimes have a key (or several). This key is a field or set of fields in the record that serves as the record's identifier. A unique key is often called the primary key, or simply the record key.
  • If you were storing employee records, you could use the unique company ID field to look-up employees without knowing any other information (remember that even names may conflict).
• Modern computer languages usually allow the programmer to define their own record type.
• When you define a record type, you specify the data type of each field and the associated identifier through which it can be accessed.
• Records may exist in any medium, but they are often written to persistent storage devices such as magnetic tapes or hard disks. Records are fundamental components of many data structures, especially linked data structures.
• Record operations include but are not limited to:
  • Declaration of a new record, including the relative position in the record, type, and name of each field.
  • Declaration and construction of a variable as belonging to a given record type.
  • Selection of a record field by using an explicit name.
  • Assignment of a record to another.
  • Comparison of two records for equality.
• You could even view the parameters of a function as record fields which receive values (the arguments).
• In Python, tuples are much like a list; the important distinction is that tuples are immutable, whereas lists are not.
  • The values stored in Python tuples can be of any type; elements are indexed by non-negative integers.
  • Tuples and lists are ordered collections of objects in that the order in which you define the elements is an intrinsic property to the data structures and does not change unless explicitly altered.
• Python provides various techniques for sorting data.
  • A sorted() built-in function sorts lists and tuples in ascending order. It returns a new sorted list.
  • A list.sort() built-in method modifies a list or tuple by sorting it in ascending order. It returns None.
  • sort() takes 2 parameters — a key, and a boolean value. The key can be a function that specifies how to sort. The boolean is set to true if you want the values reversed, and false if you do not want it reversed, the default is false.
  • Both list.sort() and sorted() allow reverse sorting by accepting a reverse parameter with a boolean value.
  • CSV is a built-in Python function that is used to parse strings based on a selected character, usually ",". This is extremely helpful for reading "Northwind Customers." For more info on how to use CSV: Reading CSV Files in Python

Key Terms

array

A container of elements stored in contiguous space, typically of the same data type.

class

A data structure that contains members, like a record, as well as various methods which operate on these members.

data structure

A collection of related values, often organized in lists, dictionaries, tuples, etc.

field

A variable which is one of multiple parts of a record.

hash table (hash map)

is a data structure which implements an associative array abstract data type, a structure that can map keys to values.

heap

Is 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.

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).

list

A list is a data structure that is a mutable, or changeable, ordered sequence of elements. Each element or value that is inside of a list is called an item. Lists are defined by having values between square brackets.

member

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

record

A structure used to collect multiple variables, often of different types stored as fields.

struct

Another word for a record.

tagged union

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

tuple

A sequence of immutable objects. Tuples cannot be changed unlike lists and tuples use parentheses, whereas lists use square brackets.

union

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

See Also

• Data structures
• Python Programming/Lists
• YouTube: How To Implement Linked Lists With Test Driven Development In JavaScript
• JavaScript - Parse CSV data into an array
• Implementing Bubble Sort in JavaScript

References

Applied Programming