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 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 since you need to declare your array types when you initialize it.
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
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") print_node = self.first_node # Iterate through chain while print_node.next_node != None: print(print_node.data) print_node = print_node.next_node print(print_node.data) test_list = toy_list() try: test_list.print() # This will raise since there is no data added 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.
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] # Reference list number_1 = list # Lists are 0 indexed number_4 = list[-1] # Negative indexing # Looping through lists for number in number_list: print(number) >>1 >>2 >>3 >>4 # Adding data to the end number_list.append(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] # Popping items from a list popped = number_list.pop() print(popped) >> 5 print(number_list) >> [2,3]