What is a List?

Lists are an abstract data structure that can be implemented using linked lists or arrays.

Linked lists inherently support list operations and can dynamically adjust their size, while arrays have a fixed length, making them less practical for use as lists. To address the limitations of arrays, lists can be implemented using dynamic arrays that can expand as needed during program execution. Dynamic arrays inherit the advantages of arrays while providing the flexibility to grow and shrink as the program requires. The choice between linked lists and dynamic arrays for implementing lists depends on the specific requirements and trade-offs of the application.

Common list operations

Initializing

# Without initial values
nums1: list[int] = []
# With initial values
nums: list[int] = [1, 3, 2, 5, 4]

Accessing elements

Access and update elements in O(1) time

# Access elements
num: int = nums[1]  # Access the element at index 1

# Update elements
nums[1] = 0    # Update the element at index 1 to 0

Inserting and Removing

Adding elements to the end of a list is an O(1) operation, the efficiency of inserting and removing elements elsewhere in the list remains the same as in arrays, with a time complexity of O(n)

nums.clear()

# Append elements at the end
nums.append(1)
nums.append(3)
nums.append(2)
nums.append(5)
nums.append(4)

nums.insert(3, 6)  # Insert number 6 at index 3

nums.pop(3)        # Remove the element at index 3

Iterating the list

# Iterate through the list by index
count = 0
for i in range(len(nums)):
    count += nums[i]

# Iterate directly through list elements
for num in nums:
    count += num

Concatenating

nums1: list[int] = [6, 8, 7, 10, 9]
nums += nums1  # Concatenate nums1 to the end of nums

Sorting

nums.sort()

List implementation

To understand how lists work, we'll implement a simplified version focusing on three key design aspects:

Initial Capacity: Start with an array of size 10.
Size Recording: Keep a variable size to track the current number of elements, updating it with each insertion or deletion.
Expansion Mechanism: When the array reaches capacity, double its size and transfer all elements to the new array. This approach helps manage dynamic arrays efficiently by balancing memory usage and performance.

class MyList:
    """List class"""

    def __init__(self):
        """Constructor"""
        self._capacity: int = 10  # List capacity
        self._arr: list[int] = [0] * self._capacity  # Array (stores list elements)
        self._size: int = 0  # List length (current number of elements)
        self._extend_ratio: int = 2  # Multiple for each list expansion

    def size(self) -> int:
        """Get list length (current number of elements)"""
        return self._size

    def capacity(self) -> int:
        """Get list capacity"""
        return self._capacity

    def get(self, index: int) -> int:
        """Access element"""
        # If the index is out of bounds, throw an exception, as below
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")
        return self._arr[index]

    def set(self, num: int, index: int):
        """Update element"""
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")
        self._arr[index] = num

    def add(self, num: int):
        """Add element at the end"""
        # When the number of elements exceeds capacity, trigger the expansion mechanism
        if self.size() == self.capacity():
            self.extend_capacity()
        self._arr[self._size] = num
        self._size += 1

    def insert(self, num: int, index: int):
        """Insert element in the middle"""
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")
        # When the number of elements exceeds capacity, trigger the expansion mechanism
        if self._size == self.capacity():
            self.extend_capacity()
        # Move all elements after `index` one position backward
        for j in range(self._size - 1, index - 1, -1):
            self._arr[j + 1] = self._arr[j]
        self._arr[index] = num
        # Update the number of elements
        self._size += 1

    def remove(self, index: int) -> int:
        """Remove element"""
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")
        num = self._arr[index]
        # Move all elements after `index` one position forward
        for j in range(index, self._size - 1):
            self._arr[j] = self._arr[j + 1]
        # Update the number of elements
        self._size -= 1
        # Return the removed element
        return num

    def extend_capacity(self):
        """Extend list"""
        # Create a new array of _extend_ratio times the length of the original array and copy the original array to the new array
        self._arr = self._arr + [0] * self.capacity() * (self._extend_ratio - 1)
        # Update list capacity
        self._capacity = len(self._arr)

    def to_array(self) -> list[int]:
        """Return a list of valid lengths"""
        return self._arr[: self._size]

Reference

List

Blog

Đặng Đình Sáng

Common list operations

List implementation

Reference

Join Our Newsletter. No Spam, Only the good stuff.

Related