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)