Is Python list an array or Linkedlist?

Randall 108 Published: 09/27/2024

Is Python list an array or Linkedlist?

I'd be happy to provide a detailed explanation in English!

In Python, the list data structure is often referred to as an "array" by beginners and non-experts. This leads to some confusion about the underlying implementation of a list versus an array or linked list in other languages.

To clarify, a Python list is neither exactly an array nor a linked list. It's a unique hybrid that combines benefits from both worlds. Here's why:

Similarities with arrays:

Memory layout: In memory, Python lists are contiguous blocks of memory, similar to arrays in languages like C or Java. This means that elements are stored sequentially, making random access and iteration efficient. Fixed size: Unlike linked lists, Python lists have a fixed size at the moment they're created, which is beneficial for applications where memory efficiency is crucial.

Similarities with linked lists:

Dynamic growth: Python lists can grow or shrink dynamically as elements are added or removed, similar to linked lists. This allows for efficient insertion and deletion operations. Variable-size elements: Unlike arrays, Python lists can contain elements of varying sizes, which is useful when working with heterogeneous data.

Key differences:

Internals: Under the hood, Python lists use a combination of array-like structures (like PyObject* pointers) to store their elements, rather than explicitly linked nodes as in traditional linked lists. Memory management: The memory management for Python lists is handled by the interpreter, whereas in languages like C or Java, the programmer needs to manually manage memory using pointers or garbage collection.

In terms of time and space complexity:

Insertion or deletion at any position: O(n) in time (where n is the current length of the list), since some elements need to be shifted. Accessing an element by index: O(1) in time, as the interpreter can directly calculate the memory address.

In summary, a Python list combines the benefits of arrays (memory efficiency and fast iteration) with those of linked lists (dynamic growth and efficient insertion/deletion). While it shares some characteristics with both data structures, its underlying implementation is distinct.

How to take input in linked list in Python

I'd be happy to help you with that!

In Python, you can create a linked list using a class to define the node structure and its methods. Here's an example of how you can implement this:

class Node:

def init(self, data=None):


self.data = data


self.next = None


class LinkedList:


def init(self):


self.head = None


def append(self, data):


if not self.head:


self.head = Node(data)


else:


current = self.head


while current.next:


current = current.next


current.next = Node(data)


def display(self):


elements = []


current_node = self.head


while current_node:


elements.append(current_node.data)


current_node = current_node.next


print(elements)

Testing the LinkedList class:

my_list = LinkedList()


data_list = [1, 2, 3, 4, 5]


for data in data_list:


my_list.append(data)


my_list.display()

In this code:

We create a Node class to represent each node in the linked list. The LinkedList class is created with an __init__ method that sets up the head of the linked list as None by default. The append method adds new nodes to the end of the linked list. If the list is empty, it creates a new node and sets it as the head. Otherwise, it traverses the list until it reaches the last node, then appends the new node. The display method prints out all the elements in the linked list by starting at the head of the list and following the next pointer until there are no more nodes.

To input data into this linked list, you would use the append method to add individual elements or a list of elements:

my_list = LinkedList()

data_input = input("Enter comma-separated values: ")


input_values = [int(x) for x in data_input.split(",")]


for value in input_values:


my_list.append(value)


my_list.display()

Here, we use the input function to get a string from the user. We then split this string into individual elements using the split method with the comma as the separator. The resulting list is converted to integers and appended to the linked list.

In summary, you can create input for your linked list by providing comma-separated values when prompted, or by passing in a list of values.

Related Articles