Difference Between List & Linked List in Python (Examples)

Hi! This tutorial will explain the differences between a list and a linked list in Python.

The table of content is structured as follows:

1) Python List

2) Attributes of Python Lists

3) Python Linked List

4) Attributes of Linked Lists

5) Differences Between Lists & Linked Lists

6) Video, Further Resources & Summary

Let’s dive into the discussion and Python code!

Python List

A Python list is a versatile and dynamic data structure that allows for the storage and manipulation of an ordered collection of elements.

Lists are mutable, meaning their contents can be modified after creation, and they support elements of different data types, including numbers, strings, and more.

With zero-based indexing, you can access elements by their position in the list, and Python provides a wide range of built-in methods for common operations like adding, removing, and searching for elements.

Below are examples of Python lists:

# list of integers
int_list = [5, 4, 3, 2, 1]
print(int_list)
 
# [5, 4, 3, 2, 1]
 
# list of strings
str_list = ["Germany", "Nigeria", "France", "Turkiye", "Mexico"]
print(str_list)
 
# ['Germany', 'Nigeria', 'France', 'Turkiye', 'Mexico']

We can also create a Python list using the built-in list() function:

# list of integers
int_list = list((5, 4, 3, 2, 1))
print(int_list)
 
# [5, 4, 3, 2, 1]
 
# list of strings
str_list = list(("Germany", "Nigeria", "France", "Turkiye", "Mexico"))
print(str_list)
 
# ['Germany', 'Nigeria', 'France', 'Turkiye', 'Mexico']

Attributes of Python Lists

Below are the attributes of Python lists:

Lists maintain the order of elements as they are inserted, allowing you to access elements by their position (index) in the list.
Lists are mutable, which means you can modify their contents by adding, removing, or changing elements after the list is created.
Lists can contain elements of different data types, including numbers, strings, other lists, objects, and more.
Lists can contain duplicate elements. You can have the same value appear multiple times in a list.
Lists can grow or shrink in size as you add or remove elements. You don’t need to specify a fixed size when creating a list.
List elements are accessed using a zero-based index. The first element is at index 0, the second at index 1, and so on.
Lists can be iterated over using loops or comprehension, making it easy to process all the elements in a list.
Lists support various operations, including append, extend, insert, remove, pop, index, and more.

Python Linked List

A Python linked list is a dynamic and efficient data structure composed of individual nodes, where each node stores both data and a reference to the next node in the sequence.

Linked lists are particularly well-suited for scenarios requiring frequent insertions and deletions, as these operations can be performed in constant time by adjusting the references.

Linked lists come in two main types: singly linked lists, where nodes have references to the next node, and doubly linked lists, where nodes have references to both the next and the previous nodes, enabling bidirectional traversal.

Below are examples of linked lists:

# linked list of integer values
class LinkedList:
  def __init__(self, val = 0 , next = None):
    self.val = val
    self.next = next
 
# instantiate the nodes
first_node = LinkedList(1)
second_node = LinkedList(2)
third_node = LinkedList(3)
fourth_node = LinkedList(4)
fifth_node = LinkedList(5)
 
# link nodes
first_node.next = second_node
second_node.next = third_node
third_node.next = fourth_node
fourth_node.next = fifth_node
 
# traverse and print list
current = first_node
while current is not None:
  print(current.val)
  current = current.next
 
# 1
# 2
# 3
# 4
# 5
 
# linked list of string values
class LinkedList:
  def __init__(self, val = 0 , next = None):
    self.val = val
    self.next = next
 
# instantiate the nodes
first_node = LinkedList("Mary")
second_node = LinkedList("had")
third_node = LinkedList("a")
fourth_node = LinkedList("little")
fifth_node = LinkedList("lamb")
 
# link nodes
first_node.next = second_node
second_node.next = third_node
third_node.next = fourth_node
fourth_node.next = fifth_node
 
# print out list
current = first_node
while current is not None:
  print(current.val)
  current = current.next
 
# Mary
# had
# a
# little
# lamb

Attributes of Linked Lists

Below are the attributes of linked lists:

A linked list consists of individual nodes, each containing data and a reference (pointer) to the next node in the sequence.
Linked lists can dynamically grow or shrink in size as nodes are added to or removed from the list. There is no need to specify a fixed size upfront.
Unlike arrays or Python lists, linked lists do not require contiguous memory allocation. Nodes can be scattered throughout memory, and the references connect them.
A linked list often has a reference to the head (the first node) and sometimes a reference to the tail (the last node). These references are used to access the beginning and end of the list efficiently.
Unlike arrays or Python lists, linked lists do not support direct random access to elements by index. To access a specific element, you must traverse the list from the head or tail.
Linked lists have a higher memory overhead compared to arrays or Python lists due to the need to store pointers or references for each node.
Common operations on linked lists include adding nodes to the beginning (prepend), adding nodes to the end (append), inserting nodes in the middle, removing nodes, and traversing the list.

Differences Between Lists & Linked Lists

Having examined both Python data structures, let us now see the dissimilarities between them:

Data Structure:
List: In Python, a list is an array-like data structure that stores elements in a contiguous block of memory. Lists are implemented as dynamic arrays, allowing for efficient random access and slicing of elements.

Linked List: A linked list is a data structure in which elements, called nodes, are connected together using pointers. Each node contains a data element and a reference (or pointer) to the next node in the sequence.
Memory Allocation:
List: Lists allocate a single block of memory to store all elements consecutively. This means that lists have a fixed memory overhead and can quickly allocate memory for new elements as needed.

Linked List: Linked lists allocate memory for each node separately. While this provides flexibility in terms of memory allocation, it also results in more memory overhead due to the storage of pointers.
Dynamic Sizing:
List: Lists in Python can dynamically resize themselves when elements are added or removed. This resizing is done automatically, and you don’t need to manage memory allocation explicitly.

Linked List: Linked lists can also grow or shrink dynamically, but you need to manage memory allocation for new nodes and deallocation for removed nodes manually.
Random Access:
List: Lists allow for efficient random access to elements in constant time (O(1)) because they use indexing.

Linked List: Linked lists do not support efficient random access; you need to traverse the list from the beginning (or end) to reach a specific element, which takes linear time (O(n)) in the worst case.
Insertion and Deletion:
List: Lists can efficiently insert or delete elements at the beginning or end in constant time (O(1)), but inserting or deleting elements in the middle requires shifting elements, which takes linear time (O(n)).

Linked List: Linked lists can efficiently insert or delete elements at any position (beginning, end, or middle) in constant time (O(1)) because they only require updating pointers.
Memory Usage:
List: Lists typically use less memory per element compared to linked lists due to the absence of pointers for each element.

Linked List: Linked lists consume more memory per element because of the overhead associated with storing pointers for each node.

Video, Further Resources & Summary

Do you need more explanations on the differences between lists and linked lists in Python? Then you should have a look at the following YouTube video of the Statistics Globe YouTube channel.

In the video, we explain the differences between lists and linked lists in Python in some more detail.

The YouTube video will be added soon.

Furthermore, you could have a look at some of the other interesting Python lists tutorials on Statistics Globe, starting with these:

This post has explained the differences between lists and linked lists in Python. I hope you found it helpful! In case you have further questions, you may leave a comment below.

This page was created in collaboration with Ifeanyi Idiaye. You might check out Ifeanyi’s personal author page to read more about his academic background and the other articles he has written for the Statistics Globe website.