Python3 Data Structures

In this chapter, we mainly combine the knowledge points learned earlier to introduce Python data structures.

Lists

In Python, lists are mutable, which is the most important feature that distinguishes them from strings and tuples. In one sentence: lists can be modified, while strings and tuples cannot.

The following are the methods of lists in Python:

The following example demonstrates most of the methods of lists:

Note: Methods like insert, remove, or sort that modify lists do not return a value.

Using Lists as Stacks

In Python, you can use a list to implement stack functionality. A stack is a last-in-first-out (LIFO, Last-In-First-Out) data structure, meaning the last element added is the first one removed. Lists provide some methods that make them very suitable for stack operations, especiallyappend()andpop()methods.

Use the append() method to add an element to the top of the stack, and use the pop() method without an index to release an element from the top of the stack.

Stack Operations

• Push: Add an element to the top of the stack.
• Pop: Remove and return the top element of the stack.
• Peek/Top: Return the top element of the stack without removing it.
• IsEmpty: Check whether the stack is empty.
• Size: Get the number of elements in the stack.

The following is a detailed explanation of how to implement these operations using lists in Python:

1. Create an empty stack

2. Push operation

Use the append() method to add an element to the top of the stack:

3. Pop operation

Use the pop() method to remove and return the top element of the stack:

4. View the top element of the stack (Peek/Top)

Directly access the last element of the list (without removing it):

5. Check if it is empty (IsEmpty)

Check whether the list is empty:

6. Get the size of the stack (Size)

Use the len() function to get the number of elements in the stack:

Example

The following is a complete example showing how to use the above operations to implement a simple stack:

In the above code, we defined a Stack class that encapsulates a list as the underlying data structure and implements the basic operations of a stack.

The output is as follows:

栈顶元素: 3
栈大小: 3
弹出元素: 3
栈是否为空: False
栈大小: 2

Using Lists as Queues

In Python, a list can be used as a queue, but due to the characteristics of lists, directly using a list to implement a queue is not the optimal choice.

A queue is a first-in-first-out (FIFO, First-In-First-Out) data structure, meaning the earliest added element is removed first.

When using a list, if you frequently insert or delete elements at the beginning of the list, performance will be affected because the time complexity of these operations is O(n). To solve this problem, Python provides collections.deque, which is a double-ended queue that can efficiently add and remove elements at both ends.

Implementing a Queue with collections.deque

collections.deque is part of the Python standard library and is very suitable for implementing queues.

The following is an example of implementing a queue with deque:

Implementing a Queue with Lists

Although deque is more efficient, if you insist on using a list to implement a queue, you can still do so. The following is an example of how to use a list to implement a queue:

1. Create a queue

2. Add elements to the tail of the queue

Use the append() method to add elements to the end of the queue:

3. Remove elements from the front of the queue

Use the pop(0) method to remove elements from the front of the queue:

4. View the front element of the queue (without removing it)

Directly access the first element of the list:

5. Check whether the queue is empty

Check whether the list is empty:

6. Get the queue size

Use the len() function to get the size of the queue:

Example (Implementing a queue with lists)

Although you can use a list to implement a queue, using collections.deque is more efficient and concise. It provides O(1) time complexity for add and remove operations, making it very suitable for a queue data structure.

List Comprehensions

List comprehensions provide a concise way to create lists from sequences. Usually an application applies some operations to each element of a sequence, using the results as elements of a new list, or creates subsequences based on determined conditions.

A list comprehension consists of an expression followed by a for clause, then zero or more for or if clauses. The result is a list generated from the expression in the context of the following for and if clauses. If you want the expression to produce a tuple, you must use parentheses.

Here we multiply each value in the list by three to obtain a new list:

Now let's play with a few tricks:

Here we call a method on each element of the sequence one by one:

We can use an if clause as a filter:

The following are some demonstrations of loops and other techniques:

List comprehensions can use complex expressions or nested functions:

Nested List Comprehensions

Python lists can also be nested.

The following example shows a 3X4 matrix list:

The following example converts the 3X4 matrix list into a 4X3 list:

The above example can also be implemented using the following method:

Another implementation method:

The del statement

The del statement can be used to remove an element from a list by index rather than by value. This is different from using pop(), which returns a value. The del statement can be used to remove a slice from a list, or to clear the entire list (the method we introduced earlier is to assign an empty list to that slice). For example:

You can also use del to delete variables:

>>> del a

Tuples and Sequences

A tuple consists of a number of values separated by commas, for example:

As you can see, tuples are always enclosed in parentheses in output so that nested structures are expressed correctly. They may be entered with or without parentheses, though parentheses are usually necessary if the tuple is part of a larger expression.

Sets

A set is an unordered collection of unique elements. Basic features include relation testing and eliminating duplicate elements.

Sets can be created with curly braces ({}). Note: To create an empty set, you must use set() instead of {}; the latter creates an empty dictionary, a data structure we will introduce in the next section.

The following is a simple demonstration:

Sets also support comprehensions:

Dictionaries

Another very useful built-in data type in Python is the dictionary.

Sequences are indexed by consecutive integers; by contrast, dictionaries are indexed by keys, which can be any immutable type, usually strings or numbers.

The best way to understand a dictionary is to view it as an unordered collection of key=>value pairs. Within the same dictionary, the keys must be distinct from one another.

A pair of curly braces creates an empty dictionary: {}.

This is a simple example of using a dictionary:

The dict() constructor builds dictionaries directly from a list of key-value pairs. If there is a fixed pattern, list comprehensions can specify particular key-value pairs:

In addition, dictionary comprehensions can be used to create dictionaries with arbitrary key and value expressions:

If the keys are simple strings, it is sometimes more convenient to specify key-value pairs using keyword arguments:

Looping Techniques

When looping through a dictionary, the keys and corresponding values can be retrieved at the same time using the items() method:

When looping through a sequence, the index position and corresponding value can be obtained at the same time using the enumerate() function:

To loop over two or more sequences at the same time, use zip() to combine them:

To loop over a sequence in reverse, first specify the sequence and then call the reversed() function:

To loop over a sequence in order, use the sorted() function, which returns a sorted sequence without modifying the original:

Reference Documentation

• Python3 List
• Python3 Tuple
• Python3 Dictionary