What is a list in Python?

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[0] # 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[0] = 6
>> [6,2,3,4,5]

# Deleting items
del number_list[0]
>> [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]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s