Basic Data Structures in Python

WARNING

elem is the abbreviation of the word “element”, representing an indeterminate type in programming definitions, i.e., an abstract data type.

List

Definition

A container formed by a sequence of elements arranged in order.

• Elements can be of any type.
• Elements are arranged in a determined order, exhibiting sequentiality.

Creating a List

Method 1: Create an empty list instance and then add elements

• list()
• .append() method

>>> wife = list()  # Instantiation  
>>> wife.append("Nishimiya Shoko")  
>>> wife.append("Sakurajima Mai")  
>>> wife.append("Elysia")  
>>> wife  
['Nishimiya Shoko', 'Sakurajima Mai', 'Elysia']  

Method 2: Directly define and populate the list

>>> phones = ["Apple", "Huawei", "Xiaomi"]  
>>> phones  
['Apple', 'Huawei', 'Xiaomi']  

Accessing Elements

1. Using Indexing
   Access the (i+1)th element with [i].

2. index() Method
   name.index(x)
   Searches for the first element with value x in list name and returns its index.

3. count() Method
   name.count(x)
   Counts how many elements in list name have the value x and returns the count.

4. len() Method
   len(name)
   Returns the total number of elements in list name.

Adding Elements

1. append() Method
   name.append(x)
   Adds element x to the end of name.

2. insert() Method
   name.insert(i, x)
   Inserts object x at index i in name, shifting subsequent elements backward.

3. extend() Method
   name.extend(name2)
   Appends list name2 to the end of list name.

Modifying Elements

1. Direct Assignment via Index
   Assign a new value to an element using its index.

Deleting Elements

1. pop() Method
   name.pop()
   Removes the last element by default.
   name.pop(i)
   Removes the element at index i, shifting subsequent elements forward.

2. remove() Method
   name.remove(x)
   Removes the first element with value x, shifting subsequent elements forward.

3. clear() Method
   name.clear()
   Deletes all elements (empties the list).

4. del Statement
   del name[a:b]
   Deletes elements with indices in [a, b) (includes a, excludes b).
   del name[:] clears the list.
   del name[i] deletes the element at index i.

Reversing a List

1. reverse() Method
   name.reverse()
   Reverses the list in place (last element becomes first, etc.).

2. Slicing Method

   >>> nums = [1, 2, 3, 4, 5]  
   >>> new_nums = nums[::-1]  
   >>> new_nums  
   [5, 4, 3, 2, 1]  
   

   The original list nums remains unchanged; a new reversed list new_nums is created.

Sorting a List

1. sort() Method
   name.sort()
name.sort(cmp=None, key=None, reverse=False)
   • Modifies the original list in place (no return value).
   • cmp is an optional parameter (deprecated in Python 3).
   • key specifies a function to extract a comparison key from each element.
     • Omitted if elements are single-parameter (e.g., numbers or single characters).

   def takeSecond(elem):  
       return elem[1]  
   random = [(2, 2), (3, 4), (4, 1), (1, 3)]  
   random.sort(key=takeSecond)  # Sorts by the second element of each tuple.  
   print(random)  
   # Output: [(4, 1), (2, 2), (1, 3), (3, 4)]  
   

   • reverse: False for ascending (default), True for descending.

Tuple

Definition

A tuple is an immutable sequence of elements, similar to a list but unchangeable.

Creating a Tuple

1. Use parentheses () to enclose elements (lists use []).
2. Sometimes tuples can be created without () (not recommended).
3. Tuple Comprehension:

   atuple = (i+1 for i in range(31, 42))  
   

4. For single-element tuples, add a trailing comma , to avoid confusion with non-tuple objects.
5. Empty Tuple:

   a = tuple()  
   b = ()  
   

Tuples Are Immutable

Tuples do not support addition, deletion, or modification of elements.

Converting Between Tuples and Lists

• Tuple → List:

  atuple = (1, 'love', 3.334, 'Y')  
  alist = list(atuple)  # Converts to list  
  

• List → Tuple:

  alist = ['I', 2, 3.1415, 'polaris']  
  atuple = tuple(alist)  # Converts to tuple  
  

Dictionary (dict)

Definition

• A collection of key-value pairs.
• Keys must be hashable (e.g., strings, numbers).
  • Hash: A process that maps data of arbitrary size to fixed-size values.
• Values can be any object.

Creating a Dictionary

1. Empty Dictionary + Assignment:

   profile = dict(name='孤筝', age=19, hobby='明月栞那')  
   

   (Note: Keys as identifiers do not need quotes.)

2. Direct {} Syntax:

   profile = {'name': '孤筝', 'age': 19, 'hobby': '明月栞那'}  
   

   (Keys as strings require quotes.)

3. From Sequence of Pairs:

   alist = [('name', '孤筝'), ('age', 19), ('hobby', '明月栞那')]  
   profile = dict(alist)  
   

4. Dictionary Comprehension:

   adict = {i: i**2 for i in range(2, 6)}  
   # Output: {2: 4, 3: 9, 4: 16, 5: 25}  
   

Accessing Elements

1. dict[key]:
   Raises KeyError if the key is missing.

2. dict.get(key[, default]):
   Returns default (or None) if the key is missing.
   If the key is absent, it can optionally add the key with the default value.

Adding/Modifying Elements

• Add/Modify: dict[key] = value

Deleting Elements

1. dict.pop(key): Removes the key-value pair.
2. del dict[key]: Deletes the pair.

Other Key Methods

Checking Key Existence

1. in/not in
2. dict.has_key() (Python 2 only; removed in Python 3).

Setting Default Values

1. Conditional Check:

   if "gender" not in profile:  
       profile["gender"] = "male"  
   

2. setdefault():
   dict.setdefault(key, default=None)
   Sets default if the key is missing.

Set

Definition

An unordered collection of unique elements (like a mathematical set).
Question: If sets are unordered, how are elements ordered when printed/stored?

Creating a Set

1. Curly Braces {}: Duplicates are automatically removed.
2. set() Constructor:

   aset = {1314, '520'}  
   bset = set()  # Empty set  
   cset = set(['I', 'love', 'ishimiya'])  
   

Adding Elements

1. add():
   aset.add(elem)

   • No effect if elem already exists (no error).
   • elem must be immutable (e.g., numbers, strings).

2. update():
   aset.update(iterable)
   Adds elements from any iterable (e.g., list, tuple, dict keys).

Deleting Elements

1. remove(): Raises KeyError if the element is missing.
2. discard(): No error if the element is missing.
3. pop(): Randomly removes and returns an element.
4. clear(): Empties the set.

Set Operations

Union

aset.union(bset) or aset | bset

Difference

aset.difference(bset) or aset - bset

Intersection

1. intersection(): aset.intersection(bset) or aset & bset
2. intersection_update(): Updates aset in place.

Symmetric Difference (Non-Overlapping Elements)

1. symmetric_difference(): Returns new set.
2. symmetric_difference_update(): Updates aset in place.

Other Operations

1. Membership Check: elem in aset
2. Disjoint Check: aset.isdisjoint(bset) (True if no common elements).
3. Subset Check: bset.issubset(aset) (True if bset is a subset).

Iterator

Iterable Objects

Objects usable in for loops (e.g., lists, tuples).

Iterable Protocol

1. Implements __iter__(): Returns an iterator instance.
   • isinstance(obj, Iterable) returns True.
2. Fallback to __getitem__(): If __iter__() is missing, Python checks for __getitem__() to simulate iteration.
   • isinstance(obj, Iterable) returns False for this case.

Iterator Objects

• Created via iter(iterable).
• Elements are accessed using next(), raising StopIteration when exhausted.

alist = ['人', '生', '若', '只', '如', '初', '见']  
gen = iter(alist)  
for _ in alist:  
    print(next(gen))  # Outputs elements sequentially  

Iterable vs. Iterator

• Iterable: The container (e.g., list).
• Iterator: The object returned by iter(), enabling element-by-element traversal.

Generator

A function that produces values lazily (like an iterator), usable in for loops.

Creating Generators

List Comprehension → Generator

alist = [i for i in range(5)]  # List  
gen = (i for i in range(5))    # Generator  
print(next(gen))  # Output: 0  

yield Keyword

• Pauses function execution and returns a value.
• Resumes from the paused state on subsequent calls.

def generator():  
    top = 5  
    i = 0  
    while i < top:  
        print(f'Current value: {i}')  
        i += 1  
        yield i  
    raise StopIteration  

gen = generator()  
for _ in range(5):  
    print(next(gen))  

Key Difference: yield vs. return

• yield pauses execution; return terminates it.
• yield can resume; return cannot.