-
Notifications
You must be signed in to change notification settings - Fork 54
/
Copy pathDataStructures.html
343 lines (320 loc) · 27.8 KB
/
DataStructures.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
<!DOCTYPE html>
<html class="writer-html5" lang="en" >
<head>
<meta charset="utf-8" /><meta content="Topic: Data Structures, Difficulty: Medium, Category: Section" name="description" />
<meta content="Big-O, complexity, efficiency, algorithm, interview preparation, list, tuple, sequence" name="keywords" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Data Structures (Part I): Introduction — Python Like You Mean It</title>
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="../_static/css/theme.css" type="text/css" />
<link rel="stylesheet" href="../_static/my_theme.css" type="text/css" />
<!--[if lt IE 9]>
<script src="../_static/js/html5shiv.min.js"></script>
<![endif]-->
<script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
<script src="../_static/jquery.js"></script>
<script src="../_static/underscore.js"></script>
<script src="../_static/doctools.js"></script>
<script async="async" src="https://www.googletagmanager.com/gtag/js?id=UA-115029372-1"></script>
<script src="../_static/gtag.js"></script>
<script crossorigin="anonymous" integrity="sha256-Ae2Vz/4ePdIu6ZyI/5ZGsYnb+m0JlOmKPjt6XZ9JJkA=" src="https://cdnjs.cloudflare.com/ajax/libs/require.js/2.3.4/require.min.js"></script>
<script>window.MathJax = {"tex": {"inlineMath": [["$", "$"], ["\\(", "\\)"]], "processEscapes": true}, "options": {"ignoreHtmlClass": "tex2jax_ignore|mathjax_ignore|document", "processHtmlClass": "tex2jax_process|mathjax_process|math|output_area"}}</script>
<script defer="defer" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<script src="../_static/js/theme.js"></script>
<link rel="index" title="Index" href="../genindex.html" />
<link rel="search" title="Search" href="../search.html" />
<link rel="next" title="Data Structures (Part II): Dictionaries" href="DataStructures_II_Dictionaries.html" />
<link rel="prev" title="Scope" href="Scope.html" />
</head>
<body class="wy-body-for-nav">
<div class="wy-grid-for-nav">
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
<div class="wy-side-scroll">
<div class="wy-side-nav-search" >
<a href="../index.html" class="icon icon-home"> Python Like You Mean It
</a>
<div class="version">
1.4
</div>
<div role="search">
<form id="rtd-search-form" class="wy-form" action="../search.html" method="get">
<input type="text" name="q" placeholder="Search docs" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
</div><div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
<p class="caption" role="heading"><span class="caption-text">Table of Contents:</span></p>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="../intro.html">Python Like You Mean It</a></li>
<li class="toctree-l1"><a class="reference internal" href="../module_1.html">Module 1: Getting Started with Python</a></li>
<li class="toctree-l1 current"><a class="reference internal" href="../module_2.html">Module 2: The Essentials of Python</a><ul class="current">
<li class="toctree-l2"><a class="reference internal" href="Basic_Objects.html">Basic Object Types</a></li>
<li class="toctree-l2"><a class="reference internal" href="SequenceTypes.html">Sequence Types</a></li>
<li class="toctree-l2"><a class="reference internal" href="Variables_and_Assignment.html">Variables & Assignment</a></li>
<li class="toctree-l2"><a class="reference internal" href="Introduction.html">Introducing Control Flow</a></li>
<li class="toctree-l2"><a class="reference internal" href="ConditionalStatements.html">Conditional Statements</a></li>
<li class="toctree-l2"><a class="reference internal" href="ForLoops.html">For-Loops and While-Loops</a></li>
<li class="toctree-l2"><a class="reference internal" href="Iterables.html">Iterables</a></li>
<li class="toctree-l2"><a class="reference internal" href="Generators_and_Comprehensions.html">Generators & Comprehension Expressions</a></li>
<li class="toctree-l2"><a class="reference internal" href="Itertools.html">Python’s “Itertools”</a></li>
<li class="toctree-l2"><a class="reference internal" href="Functions.html">Basics of Functions</a></li>
<li class="toctree-l2"><a class="reference internal" href="Scope.html">Scope</a></li>
<li class="toctree-l2 current"><a class="current reference internal" href="#">Data Structures (Part I): Introduction</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#Describing-Algorithm-Complexity">Describing Algorithm Complexity</a></li>
<li class="toctree-l3"><a class="reference internal" href="#Sequential-Data-Structures:-Lists-and-Tuples">Sequential Data Structures: Lists and Tuples</a><ul>
<li class="toctree-l4"><a class="reference internal" href="#List/Tuple-Complexities">List/Tuple Complexities</a></li>
<li class="toctree-l4"><a class="reference internal" href="#List-Complexities">List Complexities</a></li>
</ul>
</li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="DataStructures_II_Dictionaries.html">Data Structures (Part II): Dictionaries</a></li>
<li class="toctree-l2"><a class="reference internal" href="DataStructures_III_Sets_and_More.html">Data Structures (Part III): Sets & the Collections Module</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="../module_2_problems.html">Module 2: Problems</a></li>
<li class="toctree-l1"><a class="reference internal" href="../module_3.html">Module 3: The Essentials of NumPy</a></li>
<li class="toctree-l1"><a class="reference internal" href="../module_3_problems.html">Module 3: Problems</a></li>
<li class="toctree-l1"><a class="reference internal" href="../module_4.html">Module 4: Object Oriented Programming</a></li>
<li class="toctree-l1"><a class="reference internal" href="../module_5.html">Module 5: Odds and Ends</a></li>
<li class="toctree-l1"><a class="reference internal" href="../changes.html">Changelog</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap"><nav class="wy-nav-top" aria-label="Mobile navigation menu" >
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
<a href="../index.html">Python Like You Mean It</a>
</nav>
<div class="wy-nav-content">
<div class="rst-content">
<div role="navigation" aria-label="Page navigation">
<ul class="wy-breadcrumbs">
<li><a href="../index.html" class="icon icon-home"></a> »</li>
<li><a href="../module_2.html">Module 2: The Essentials of Python</a> »</li>
<li>Data Structures (Part I): Introduction</li>
<li class="wy-breadcrumbs-aside">
<a href="../_sources/Module2_EssentialsOfPython/DataStructures.md.txt" rel="nofollow"> View page source</a>
</li>
</ul>
<hr/>
</div>
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<div itemprop="articleBody">
<style>
/* CSS overrides for sphinx_rtd_theme */
/* 24px margin */
.nbinput.nblast.container,
.nboutput.nblast.container {
margin-bottom: 19px; /* padding has already 5px */
}
/* ... except between code cells! */
.nblast.container + .nbinput.container {
margin-top: -19px;
}
.admonition > p:before {
margin-right: 4px; /* make room for the exclamation icon */
}
/* Fix math alignment, see https://github.com/rtfd/sphinx_rtd_theme/pull/686 */
.math {
text-align: unset;
}
</style>
<div class="section" id="Data-Structures-(Part-I):-Introduction">
<h1>Data Structures (Part I): Introduction<a class="headerlink" href="#Data-Structures-(Part-I):-Introduction" title="Permalink to this headline"></a></h1>
<p>Here we survey Python’s built-in data structures. You should already be familiar with its lists and tuples, two data structures that facilitate working with sequential data. Two other critical, built-in data structures to be introduced are:</p>
<ul class="simple">
<li><p>dictionary: a mapping from “keys” to “values”</p></li>
<li><p>sets: an unordered collection of items that can be used to perform set-algebraic operations (e.g. union and intersection)</p></li>
</ul>
<p>These data structures are not merely convenient constructs with some nice pre-written functionality; they also provide an interface to some optimized core utilities that have been written in C (or whatever language your Python interpreter is written in). For example, let’s write a function that checks if an item is contained within an iterable:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">is_in</span><span class="p">(</span><span class="n">seq</span><span class="p">,</span> <span class="n">target</span><span class="p">):</span>
<span class="sd">""" Returns True if `target` is contained in `seq`."""</span>
<span class="k">for</span> <span class="n">item</span> <span class="ow">in</span> <span class="n">seq</span><span class="p">:</span>
<span class="k">if</span> <span class="n">item</span> <span class="o">==</span> <span class="n">target</span><span class="p">:</span>
<span class="k">return</span> <span class="kc">True</span>
<span class="k">return</span> <span class="kc">False</span>
</pre></div>
</div>
<p>This function mirrors the C-algorithm that Python uses “under the hood” for checking for membership in a list (assuming you are using the CPython interpreter, which you almost definitely are). Because their function is implemented “at a lower level”, and need not be interpreted, we expect it to be faster than ours:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="n">x</span> <span class="o">=</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="s2">"moo"</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="kc">True</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="kc">None</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">8</span><span class="p">]</span>
<span class="gp">>>> </span><span class="n">is_in</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="c1"># takes 980 nanoseconds on my machine</span>
<span class="go">False</span>
<span class="gp">>>> </span><span class="o">-</span><span class="mi">1</span> <span class="ow">in</span> <span class="n">x</span> <span class="c1"># takes 320 nanoseconds on my machine</span>
<span class="go">False</span>
</pre></div>
</div>
<p>Here, Python’s built-in sequence-membership function is 3x faster than using our own function. Furthermore, it will be important to know the advantages provided by each of the data structures. For instance, testing for membership in a set is even faster than is checking for membership in a list:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># test for membership in a list</span>
<span class="o">>>></span> <span class="o">-</span><span class="mi">1</span> <span class="ow">in</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="s2">"moo"</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="kc">True</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="kc">None</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">8</span><span class="p">]</span> <span class="c1"># takes 295 nanoseconds on my machine</span>
<span class="kc">False</span>
<span class="c1"># test for membership in a set</span>
<span class="o">>>></span> <span class="o">-</span><span class="mi">1</span> <span class="ow">in</span> <span class="p">{</span><span class="mi">1</span><span class="p">,</span> <span class="s2">"moo"</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="kc">True</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="kc">None</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">8</span><span class="p">}</span> <span class="c1"># takes 65 nanoseconds on my machine</span>
<span class="kc">False</span>
</pre></div>
</div>
<p>We get a 4.5x speedup in our membership test just by using a set instead of a list, because the use of a set permits Python to use an entirely different algorithm for checking for membership. On our end, we merely replaced square brackets with curly braces! Hopefully this is sufficient motivation for learning about Python’s data structures and the algorithms that they utilize “under the hood”.</p>
<div class="admonition note">
<p class="admonition-title fa fa-exclamation-circle"><strong>Takeaway</strong>:</p>
<p>Python’s data structures come with a wealth of built-in functionality. Furthermore, understanding where each data structure “shines” is critical for writing efficient Python code. It is not necessary to memorize this information, but you should know that it exists and should be referenced frequently.</p>
</div>
<div class="section" id="Describing-Algorithm-Complexity">
<h2>Describing Algorithm Complexity<a class="headerlink" href="#Describing-Algorithm-Complexity" title="Permalink to this headline"></a></h2>
<p>In order to meaningfully compare the relative efficiency of algorithms, it is useful to summarize how algorithms “scale” with problem size. Two sorting algorithms may be comparable when sorting tens of items, and yet they may have wildly different performances when sorting thousands of items.</p>
<p>“Big-O” notation allows us to denote how an algorithm’s run time scales against problem size. Specifically, it signifies the “worst-case scenario” performance of an algorithm.</p>
<p>Let’s take, for instance, the <code class="docutils literal notranslate"><span class="pre">is_in</span></code> function that we wrote at the beginning of this section. In it, we iterate over a collection to check if it contains a specific item. The worst-case scenario for this algorithm is when the item is not a member of the collection at all - we have to iterate over the entire collection before we can conclude that it does not possess our item. So if we increase the collection to be <span class="math notranslate nohighlight">\(n\)</span> times larger in size, it should take <span class="math notranslate nohighlight">\(n\)</span> times as long to
iterate over it to determine that the item is not a member of the collection (again, dealing with the worst-case scenario). Because the worst-case scenario run time of <code class="docutils literal notranslate"><span class="pre">is_in</span></code> scales linearly with the size of the collection, <span class="math notranslate nohighlight">\(n\)</span>, we denote it’s run time complexity, using big-O notation, as <span class="math notranslate nohighlight">\(\mathcal{O}(n)\)</span>.</p>
<p>Now suppose we did a truly terrible job writing a membership algorithm, and performed a nested iteration over our collection:</p>
<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">is_in_slow</span><span class="p">(</span><span class="n">seq</span><span class="p">,</span> <span class="n">target</span><span class="p">):</span>
<span class="sd">""" Returns True if `target` is contained in `seq`."""</span>
<span class="k">for</span> <span class="n">item</span> <span class="ow">in</span> <span class="n">seq</span><span class="p">:</span>
<span class="c1"># for each item in seq, iterate over seq in its entirety!</span>
<span class="k">for</span> <span class="n">item2</span> <span class="ow">in</span> <span class="n">seq</span><span class="p">:</span>
<span class="k">if</span> <span class="n">item</span> <span class="o">==</span> <span class="n">target</span><span class="p">:</span>
<span class="k">return</span> <span class="kc">True</span>
<span class="k">return</span> <span class="kc">False</span>
</pre></div>
</div>
<p>For each item in <code class="docutils literal notranslate"><span class="pre">seq</span></code> we iterate over <code class="docutils literal notranslate"><span class="pre">seq</span></code> again, thus in the worst-case scenario we need to iterate over <span class="math notranslate nohighlight">\(n\)</span> items, <span class="math notranslate nohighlight">\(n\)</span> separate times - a total of <span class="math notranslate nohighlight">\(n^{2}\)</span> “steps” in our algorithm. Thus we would say that <code class="docutils literal notranslate"><span class="pre">is_in_slow</span></code> is a <span class="math notranslate nohighlight">\(\mathcal{O}(n^{2})\)</span> algorithm: whereas doubling size of <code class="docutils literal notranslate"><span class="pre">seq</span></code> would increase the run time of our <span class="math notranslate nohighlight">\(\mathcal{O}(n)\)</span> algorithm by a factor of 2 (linear scaling), it would increase the run time of this <span class="math notranslate nohighlight">\(\mathcal{O}(n^{2})\)</span> algorithm
by 4 (quadratic scaling).</p>
<p>Here is a more formal description of this notation:</p>
<div class="alert alert-block alert-info"><p><strong>“Big-O” Notation</strong>: Suppose that <span class="math notranslate nohighlight">\(n\)</span> denotes the “size” of the input to an algorithm, and that the mathematical expression <span class="math notranslate nohighlight">\(f(n)\)</span> describes how many computational steps the algorithm must take in its <em>worst-case scenario</em>, given that input. Then the algorithm’s run time complexity can be denoted using the <strong>“Big-O”</strong> notation: <span class="math notranslate nohighlight">\(\mathcal{O}(f(n))\)</span>.</p>
</div><p>A few important notes:</p>
<ul class="simple">
<li><p>We only care about the “highest-order” term in <span class="math notranslate nohighlight">\(f(n)\)</span>. That is, <span class="math notranslate nohighlight">\(\mathcal{O}(n + n^{2})\)</span> should just be written as <span class="math notranslate nohighlight">\(\mathcal{O}(n^{2})\)</span>.</p></li>
<li><p>We never care about constant factors in our scaling. That is, even if an algorithm iterates over a sequence twice, its big-O complexity should be written as <span class="math notranslate nohighlight">\(\mathcal{O}(n)\)</span>, rather than <span class="math notranslate nohighlight">\(\mathcal{O}(2n)\)</span>.</p></li>
<li><p>An algorithm whose run time <em>does not depend on the size of its input</em> is a <span class="math notranslate nohighlight">\(\mathcal{O}(1)\)</span> algorithm.</p>
<ul>
<li><p>Example: a function that returns the second element from a list.</p></li>
</ul>
</li>
<li><p>There are more nuanced methods for analyzing algorithm complexity than solely considering the worst-case scenario, which can be overly pessimistic. Know that “big-O” notation can be used to convey mean performance, <a class="reference external" href="https://en.wikipedia.org/wiki/Amortized_analysis">amortized</a> performance, and other types of analysis. Here, we will simply stick to the worst-case analysis.</p></li>
</ul>
<div class="admonition note">
<p class="admonition-title fa fa-exclamation-circle"><strong>Takeaway</strong>:</p>
<p>We will be using the “big-O” notation, <span class="math notranslate nohighlight">\(\mathcal{O}(f(n))\)</span>, to summarize the performance of the algorithms used by Python’s data structures.</p>
</div>
</div>
<div class="section" id="Sequential-Data-Structures:-Lists-and-Tuples">
<h2>Sequential Data Structures: Lists and Tuples<a class="headerlink" href="#Sequential-Data-Structures:-Lists-and-Tuples" title="Permalink to this headline"></a></h2>
<p>The “Sequence Types” section already introduced lists and tuples. Recall that both provide the same interface for accessing and summarizing the contents of a heterogeneous sequence of objects. However, a list can be mutated - updated, removed from, and added to - whereas a tuple cannot be mutated. Thus a list is <em>mutable</em>, whereas a tuple is <em>immutable</em>. Here you will find a summary of the algorithmic complexities of many of the built-in functions that work on sequential data structures.</p>
<p>For a complete rundown of the functions available to Python’s list, go <a class="reference external" href="https://docs.python.org/3/tutorial/datastructures.html#more-on-lists">here</a>.</p>
<div class="section" id="List/Tuple-Complexities">
<h3>List/Tuple Complexities<a class="headerlink" href="#List/Tuple-Complexities" title="Permalink to this headline"></a></h3>
<p>Let <code class="docutils literal notranslate"><span class="pre">seq</span></code> represent a <strong>list or tuple</strong> of length <span class="math notranslate nohighlight">\(n\)</span>; <span class="math notranslate nohighlight">\(i\)</span> and <span class="math notranslate nohighlight">\(j\)</span> are integers drawn randomly from the interval <span class="math notranslate nohighlight">\([0, n-1]\)</span>; <span class="math notranslate nohighlight">\(k\)</span> is the length of any subsequence involved in the operation. The following is a summary of the complexities associated with various common operations using lists and tuple (according to their implementations in CPython):</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 26%" />
<col style="width: 13%" />
<col style="width: 61%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Operation</p></th>
<th class="head"><p>Complexity</p></th>
<th class="head"><p>Explanation</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">len(seq)</span></code></p></td>
<td><p>O(1)</p></td>
<td><p>Return the number of items in the sequence</p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">seq[i]</span></code></p></td>
<td><p>O(1)</p></td>
<td><p>Retrieve any item from the sequence</p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">seq[i:j]</span></code></p></td>
<td><p>O(k)</p></td>
<td><p>Retrieve a length-k slice from the sequence</p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">for</span> <span class="pre">item</span> <span class="pre">in</span> <span class="pre">seq..</span></code></p></td>
<td><p>O(n)</p></td>
<td><p>Iterate over the sequence</p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">obj</span> <span class="pre">in</span> <span class="pre">seq</span></code></p></td>
<td><p>O(n)</p></td>
<td><p>Check if <code class="docutils literal notranslate"><span class="pre">obj</span></code> is a member of <code class="docutils literal notranslate"><span class="pre">seq</span></code></p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">seq.count(obj)</span></code></p></td>
<td><p>O(n)</p></td>
<td><p>Count the number of occurrences of <code class="docutils literal notranslate"><span class="pre">obj</span></code> in <code class="docutils literal notranslate"><span class="pre">seq</span></code></p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">seq.index(obj)</span></code></p></td>
<td><p>O(n)</p></td>
<td><p>Return position-index of <code class="docutils literal notranslate"><span class="pre">obj</span></code> in <code class="docutils literal notranslate"><span class="pre">seq</span></code></p></td>
</tr>
</tbody>
</table>
</div>
<div class="section" id="List-Complexities">
<h3>List Complexities<a class="headerlink" href="#List-Complexities" title="Permalink to this headline"></a></h3>
<p>Here we consider some mutating operations, like <code class="docutils literal notranslate"><span class="pre">append</span></code>, that are available to lists and not tuples. It is important to note that lists are implemented such that:</p>
<ul class="simple">
<li><p>operations that add-to or remove-from the <em>end</em> of the list are <span class="math notranslate nohighlight">\(\mathcal{O}(1)\)</span></p></li>
<li><p>operations that add-to or remove-from the <em>beginning</em> of the list are <span class="math notranslate nohighlight">\(\mathcal{O}(n)\)</span></p></li>
</ul>
<p>Let <code class="docutils literal notranslate"><span class="pre">my_list</span></code> represent a list of length <span class="math notranslate nohighlight">\(n\)</span>, and <code class="docutils literal notranslate"><span class="pre">i</span></code> is an integer drawn randomly from the interval <span class="math notranslate nohighlight">\([0, n-1]\)</span>. The following is a summary of the complexities associated with various operations using a list (according to its implementation in CPython):</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 28%" />
<col style="width: 13%" />
<col style="width: 59%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Operation</p></th>
<th class="head"><p>Complexity</p></th>
<th class="head"><p>Explanation</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">my_list[i]</span> <span class="pre">=</span> <span class="pre">obj</span></code></p></td>
<td><p>O(1)</p></td>
<td><p>Set the ith entry of the list with a new object.</p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">my_list.append(obj)</span></code></p></td>
<td><p>O(1)</p></td>
<td><p>Append a new object to the end of the list.</p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">my_list.pop()</span></code></p></td>
<td><p>O(1)</p></td>
<td><p>Remove the object from the <em>end</em> of the list.</p></td>
</tr>
<tr class="row-odd"><td><p><code class="docutils literal notranslate"><span class="pre">my_list.pop(0)</span></code></p></td>
<td><p>O(n)</p></td>
<td><p>Remove the object from the <em>beginning</em> of the list.</p></td>
</tr>
<tr class="row-even"><td><p><code class="docutils literal notranslate"><span class="pre">my_list.sort()</span></code></p></td>
<td><p>O(nlog(n))</p></td>
<td><p>Return a sorted version of the list.</p></td>
</tr>
</tbody>
</table>
</div>
</div>
</div>
</div>
</div>
<footer><div class="rst-footer-buttons" role="navigation" aria-label="Footer">
<a href="Scope.html" class="btn btn-neutral float-left" title="Scope" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left" aria-hidden="true"></span> Previous</a>
<a href="DataStructures_II_Dictionaries.html" class="btn btn-neutral float-right" title="Data Structures (Part II): Dictionaries" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right" aria-hidden="true"></span></a>
</div>
<hr/>
<div role="contentinfo">
<p>© Copyright 2021, Ryan Soklaski.</p>
</div>
Built with <a href="https://www.sphinx-doc.org/">Sphinx</a> using a
<a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a>
provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
</div>
</div>
</section>
</div>
<script>
jQuery(function () {
SphinxRtdTheme.Navigation.enable(true);
});
</script>
</body>
</html>