sec-data-structure.ptx

<?xml version="1.0" encoding="UTF-8"?>

<!--*****************************************
This is part of Basic Programming
Copyright (C) 2024
Phạm Công Vinh
See the file COPYING for copying conditions.
******************************************-->

<section xml:id="sec-data-structure" xmlns:xi="http://www.w3.org/2001/XInclude">
  <title>Data Structures</title>

  <objectives>
    <ul>
      <li>Learn about data structures.</li>
      <li>See two examples<mdash /><term>lists</term> and <term>dictionaries</term>.</li>
    </ul>
  </objectives>

  <introduction>

    <p>
      <idx><h>Code examples</h><h>without list</h></idx>
      Up until now, variables have been storing one singular value. Suppose we have a program that stores 100 perfect square numbers. It might look like this:
    </p>

    <program language="python">
      <input>
        ps1 = 0
        ps2 = 1
        ps3 = 4
        ps4 = 9
        # ...
        ps100 = 9801
      </input>
    </program>

    <p>
      This is highly impractical. So, to reduce the number of variables, we can make use of a new object<mdash></mdash><term>a data structure</term>.
    </p>

    <definition xml:id="def-data-structure">
      <idx><h>Definitions</h><h>of data structures</h></idx>
      <statement>
        <p>
          <term>A data structure</term> is a special data that acts as a storage for multiple other pieces of data.
        </p>
        <p>
          Each piece of <q>sub-data</q> stored by a data structure is called an <term>element</term>.
        </p>
        <p>
          Data structures are <em>built on top of</em> data types, meaning concepts in <xref ref="sec-data-type"/> can be applied to them.
        </p>
      </statement>
    </definition>
    
    <p>
      <idx><h>Code examples</h><h>with list</h></idx>
      Then, we can re-implement our program as follows:
    </p>
    
    <program language="python">
      <input>
        ps = [0, 1, 4, 9, ..., 9801]
      </input>
    </program>

    <p>
      Even though this is still impractical (we're typing 100 numbers), it's significantly better than before. Instead of creating 100 different variables, we create just one that holds 100 values. (This is a <term>list</term>, which is discussed below.)
    </p>

    <p>
      Every programming language has its own set of built-in data structures, all of which are different in some way and have their pros and cons.
    </p>

    <p>
      For now, we will take a look at two of the most used data structures<mdash /><term>lists (arrays)</term> and <term>dictionaries</term>.
    </p>

    <note>
      <idx><h>Notes</h><h>on learning data structures</h></idx>
      <p>
        The following sub-sections will only <em>briefly introduce</em> these two objects. <!-- If you are interested in their syntax or how to work with them, please refer to <xref ref="appendix-whats-next" text="title"/>. -->
      </p>
    </note>
  </introduction>

  <subsection xml:id="subsec-list">
    <title>Lists (Arrays)</title>

    <definition xml:id="def-list">
      <idx><h>Definitions</h><h>of lists</h></idx>
      <statement>
        <p>
          A <term>list</term> can store multiple values at once.
        </p>
        <p>
          Elements of a Pythonic list can be of <em>different</em> data types.
        </p>
      </statement>
    </definition>

    <aside>
      <title>Topic(s) you might be interested in</title>
      <p>
        <ul>
          <li>
            <p>
              <idx><h>Links</h><h>Python lists vs arrays</h></idx>
              <url href="https://www.google.com/search?q=Python+lists+vs+arrays" visual="google.com/search?q=Python+lists+vs+arrays">"Python lists vs arrays"</url>
            </p>
          </li>
        </ul>
      </p> 
    </aside>

    <note>
      <idx><h>Notes</h><h>on lists vs arrays</h></idx>
      <p>
        In some other programming languages, there's a data structure called <term>array</term>, which works the same as a list in Python.
      </p>

      <p>
        Python also has arrays, though with a different implementation from some others'. This goes to show that in different languages, data structures can have the same name but different implementations, and vice versa.
      </p>

      <p>
        Generally, the term <q>array</q> is more well-known than <q>list</q>.
      </p>
    </note>

    <p>
      For example:
    </p>

    <aside>
      <title>Try It Out</title>
      
      <p>
        Try adding more elements to the lists.
      </p> 
    </aside>

    <sage language="python">
      <input>
        li1 = [1, 2, 3]
        li2 = [1, 2.5, 3]
        li3 = [1, "test", 3]

        print(li1, type(li1))
        print(li2, type(li2))
        print(li3, type(li3))
      </input>
    </sage>
    <problem>
      <pre>
        [1 2 3] &lt;class 'list'&gt;
        [1 2.5 3] &lt;class 'list'&gt;
        [1 'test' 3] &lt;class 'list'&gt;
      </pre>
    </problem>
    <investigation>
      <idx><h>Code examples</h><h>using lists</h></idx>
      <p></p>
      <p>
        We declare 3 lists, each of which has 3 elements.
      </p>
      <p>
        The elements of <c>l1</c> are all integers.
      </p>
      <p>
        The list <c>l2</c> stores two integers and a float.
      </p>
      <p>
        The list <c>l3</c> has two integers and a string.
      </p>
      <p>
        The command <c>type()</c> lets us know their data type is <c>list</c>.
      </p>
    </investigation>

    <note>
      <idx><h>Notes</h><h>on using lists</h></idx>
      <p>
        As you can already see, lists have yet another distinct syntax. But we won't go into their syntax and usage yet. Refer to <xref ref="sec-using-list" text="type-local"/> for further discussion about lists.
      </p>
    </note>
    
  </subsection>

  <subsection xml:id="subsec-dictionary">
    <title>Dictionaries</title>

    <definition xml:id="def-dictionary">
      <idx><h>Definitions</h><h>of dictionaries</h></idx>
      <statement>
        <p>
          A <term>dictionary</term> can store multiple pairs of <term>key:value</term>.
        </p>
        <p>
          It's often used to store descriptive information.
        </p>
      </statement>
    </definition>

    <p>For example:</p>

    <aside>
      <title>Try It Out</title>
      
      <p>
        Try adding more information about Steve.
      </p> 
    </aside>

    <sage language="python">
      <input>
        info_of_student = {
          "name": "Steve",
          "gender": "male",
          "dob": 1980, 
          "hobbies": ["apples", "swimming", "programming"],
          5: "random",
        }

        print(info_of_student)
        print(type(info_of_student))
      </input>
    </sage>
    <problem>
      <pre>
        {'name': 'Steve', 'gender': 'male', 'dob': 1980, 'hobbies': ['apples', 'swimming', 'programming'], 5: 'random'}
        &lt;class 'dict'&gt;
      </pre>
    </problem>
    <investigation>
      <idx><h>Code examples</h><h>using a dictionary</h></idx>
      <p></p>
      <p>
        We declare a dictionary with 5 elements which are pairs of key:value.
      </p>
      <p>
        As you can see, the keys and values can have different data types.
      </p>
      <p>
        The command <c>type()</c> lets us know its data type is <c>dict</c>.
      </p>
    </investigation>
    
    <note>
      <idx><h>Notes</h><h>on using dictionaries</h></idx>
      <p>
        Dictionaries have yet another distinct syntax. Again, we won't go into their syntax and usage yet. Refer to <xref ref="sec-using-dictionary" text="type-local"/> for further discussion about dictionaries.
      </p>
    </note>
    
  </subsection>

  <conclusion>
    <p>
      <cd>
      </cd>
    </p>

    <exploration>
      <title>Basic Programming <mdash /> Part 7: Data Structures</title>
      <idx><h>Videos</h><h>part 07</h></idx>
    
      <p>
        Coming soon.
      </p>
      
      <video youtubeplaylist="PLBLdRr-v59vwnKvmvLtcgmAnsb2K1Ta_M" />
      
    </exploration>

  </conclusion>

</section>