In Python a list can be made at anytime simply by calling the list() constructor. This can be done without needing to import any fancy collections library either. But what exactly is a list in Python since you can’t use indexes on a node based list in other languages and you can’t append items to an array based list because when the array is full you need to make a bigger one and copy everything over. You also can’t hold arbitrary types of data in a typical array based list in Java since you need to declare your array types when you initialize the array.
According to the py-docs lists are variable-length arrays meaning it has clever logic built in to abstract resizing the array for you as you continue to append more data. Python also tries to predict how often you are appending data to pad the size a bit so it doesn’t need to resize as often since that requires temporarily more memory and running an o(n) operation for an insert that should otherwise be a o(1) operation on a node based list.
But if it was an array how does it hold dynamic types? Well this one is also simple and that is because Python treats everything as a dynamic object so behind the scenes an int, string, and MyClass are all derived from the same core python object. The list() is an array of those, magic isn’t it! However all of this magic isn’t cheap and is why working with Python lists results in code that runs slower than implementing list operations in an optimized language like C++.
Creating our own list data structure using a node class
To better understand how to use Python’s built-in list we should first understand how a basic list is created.
As mentioned in a previous article about data structures a list is a linear data structure built of linked nodes of data used to store a collection of data. Below is a quick implementation of a basic list for your reference.
class node: next_node = None def __init__(self, data): self.data = data class toy_list: # Track head node and active node first_node = None current_node = None def add(self, data): data_node = node(data) if self.first_node == None: # initialize the head of # the list self.first_node = data_node self.current_node = data_node else: # create links self.current_node. next_node = data_node self.current_node = data_node def print(self): if self.first_node == None: raise Exception("List contains no data to print") p_node = self.first_node # Iterate through chain while p_node.next_node != None: print(p_node.data) p_node = p_node.next_node print(p_node.data) test_list = toy_list() try: # This will raise since # there is no data added test_list.print() except Exception as e: print(str(e)) test_list.add("a") test_list.add("b") test_list.add("c") test_list.print() # Output # List contains no data to print # a # b # c
This list can hold things such as a series of numbers, items to buy while shopping, people in an address books, metrics about a component in a system, etc. But as you can see there isn’t an indexable way to retrieve items out of this list so how does Python achieve such magic?
Using Python’s Native List
Instead of creating your own list data structure like I did above; here is an example of using Python’s Native lists as well as working with some of its common built in methods.
# Empty list creation bracket_list =  object_list = list() # List creation with data number_list = [1,2,3,4] # Access data in a list print(number_list) >> 2 print(number_list[-1]) >> 4 # Reference list # Lists are 0 indexed number_1 = list[0 # Negative indexing number_4 = list[-1] # Iterating through lists for number in number_list: print(number) >>1 >>2 >>3 >>4 # Iterating by index for i in range(len(number_list)): print number_list[i] # Adding data to the end number_list.append(5) print(number_list) >> [1,2,3,4,5] # Slicing items after an index print(number_list[:2]) >> [1,2] # Slicing beginning of a list print(number_list[2:]) >> [3,4,5] # Replacing items number_list = 6 >> [6,2,3,4,5] # Deleting items del number_list >> [2,3,4,5] number_list.remove(4) >> [2,3,5] # Using a list as a stack by # popping items from a list popped = number_list.pop() print(popped) >> 5 print(number_list) >> [2,3]
As you can see from the above code the Python list really is a simple and effective data structure to work with. You can append items to the end of the list like a typical list and you can retrieve items out of a list similar to how you could an Array in Java.
But unlike an array you don’t need to initialize the size or the memory space when you create it which contributes to the flexible nature of Python’s list.