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]
Top comments (0)