Difference between List and Dictionary in Python

Lists and Dictionaries in Python are inbuilt data structures that are used to store data. Lists are linear in nature whereas dictionaries stored the data in key-value pairs. In this article, we will see the difference between the two and find out the time complexities and space complexities which arises when we try to store data and try to perform certain operations on them.

Lists in Python

In Python, a list is a built-in dynamic sized array (automatically grows and shrinks). We can store all types of items (including another list) in a list. A list may contain mixed type of items, this is possible because a list mainly stores references at contiguous locations and actual items maybe stored at different locations.

Example: In this example, we will see how to create a simple one-dimensional list as well as a two-dimensional list in Python and access its values using the list index.

# Python program to demonstrate Lists # Creating a 1D List a = ["Geeks", "For", "Geeks"] # List of Strings print(a) # Accessing particular elements print(a[0]) print(a[0][1]) print(a[1]) # Creating a 2D List  a = [['Geeks', 'For'], ['Geeks']] print(a) # Accessing particular elements print(a[0]) print(a[0][1]) print(a[1]) 

List containing multiple values: ['Geeks', 'For', 'Geeks'] Geeks e For Multi-Dimensional List: [['Geeks', 'For'], ['Geeks']] ['Geeks', 'For'] For ['Geeks'] 

Dictionary in Python

A Python dictionary is a data structure that stores the value in key: value pairs. Values in a dictionary can be of any data type and can be duplicated, whereas keys can’t be repeated and must be immutable.

Example: In this example, we will see how to create a simple dictionary with similar key types as well as a dictionary with mixed key types.

# Creating a Dictionary with Integer Keys  Dict = {1: 'Geeks', 2: 'For', 3: 'Geeks'} print("Dictionary with the use of Integer Keys: ", Dict) # Accessing particular elements print(Dict[1]) print(Dict[2]) # Creating a Dictionary with Mixed keys  Dict = {'Name': 'Geeks', 1: [1, 2, 3, 4]} print("\nDictionary with the use of Mixed Keys: ", Dict) # Accessing particular elements print(Dict['Name']) print(Dict[1]) 

Dictionary with the use of Integer Keys: {1: 'Geeks', 2: 'For', 3: 'Geeks'} Geeks For Dictionary with the use of Mixed Keys: {'Name': 'Geeks', 1: [1, 2, 3, 4]} Geeks [1, 2, 3, 4] 

Difference between a List and a Dictionary

The following table shows some differences between a list and a dictionary in Python:

Space-Time Complexities of List and Dictionary

Understanding the space and time complexities of Lists and Dictionaries in Python is essential for choosing the right data structure for a given task. The efficiency of operations like searching, inserting, and deleting elements varies based on how these data structures are implemented.

Time Complexity Comparison

The table below shows the time complexities of different operations for Lists and Dictionaries:

Example 1: Comparing the time required to create a List and Dictionary having 1 million elements.

import time # Creating a List t1 = time.time() my_list = [] for i in range(1000000): my_list.append(int(i//(2**(1/2)))) t2 = time.time() print("Time taken to create List:", t2-t1, "seconds") # Creating a Dictionary t1 = time.time() my_dict = {} for i in range(1000000): my_dict[int(i//(2**(1/2)))] = i t2 = time.time() print("Time taken to create Dictionary:", t2-t1, "seconds") 

Time taken to create List: 0.28288698196411133 seconds Time taken to create Dictionary: 0.3956336975097656 seconds 

Example 2: Comparing the time required to find an element in a List and Dictionary having 1 million elements.

import time my_list = [int(i // (2**(1/2))) for i in range(1000000)] my_dict = {int(i // (2**(1/2))): i for i in range(1000000)} # Searching in List t1 = time.time() found = 707106 in my_list t2 = time.time() print("Time taken to find an element in List:", t2-t1, "seconds") # Searching in Dictionary t1 = time.time() found = 707106 in my_dict t2 = time.time() print("Time taken to find an element in Dictionary:", t2-t1, "seconds") 

Time taken to find an element in List: 0.01314544677734375 seconds Time taken to find an element in Dictionary: 1.9073486328125e-06 seconds 

Example 3: Comparing the time required to delete an element from a List and Dictionary having 1 million elements.

import time my_list = [int(i // (2**(1/2))) for i in range(1000000)] my_dict = {int(i // (2**(1/2))): i for i in range(1000000)} # Accessing an element t1 = time.time() element = my_list[500000] t2 = time.time() print("Time taken to access an element in List:", t2-t1, "seconds") # Deleting an element by value t1 = time.time() my_list.remove(element) t2 = time.time() print("Time taken to delete an element from List:", t2-t1, "seconds") # Accessing an element in Dictionary t1 = time.time() element = my_dict[707106] t2 = time.time() print("Time taken to access an element in Dictionary:", t2-t1, "seconds") # Deleting an element by key t1 = time.time() del my_dict[707106] t2 = time.time() print("Time taken to delete an element from Dictionary:", t2-t1, "seconds") 

Time taken to access an element in List: 3.0994415283203125e-06 seconds Time taken to delete an element from List: 0.006572246551513672 seconds Time taken to access an element in Dictionary: 1.9073486...

Example 4: Comparing the space occupied by List and Dictionary having 100 million elements.

import sys List = [] for i in range(1000000): List.append(int(i//(2**(1/2)))) print("Space occupied by List:", sys.getsizeof(List), "bytes") Dict = {} for i in range(1000000): Dict[int(i//(2**(1/2)))] = i print("Space occupiedd by Dictionary:", sys.getsizeof(Dict), "bytes") exit() 

Space occupied by List: 8448728 bytes Space occupiedd by Dictionary: 41943128 bytes 

Key Observations from the above examples

• Dictionaries provide faster lookups compared to lists when searching by key, as they have an average complexity of O(1), while lists require O(n) in the worst case.
• Lists are faster for index-based access, as retrieving an element by index takes O(1), whereas dictionary lookups require computing a hash.
• Dictionaries require more memory, as they store keys along with values, unlike lists.
• For large-scale searches and deletions, dictionaries outperform lists.
• For sequential access and storage efficiency, lists are preferable.