List

Intro

The list Abstract Data Type is a collection of elements with a specific order that can grow or shrink dynamically, supporting index-based access, insertion, and removal. Lists can be implemented by an Array or Linked List.

Characteristics

• Ordered collection – Each element has a position (index)
• Duplicate elements allowed
• Heterogeneous or homogeneous – Depends on the implementation

Operations

Defining the List ADT

• • get(i) – to read the value of an element at the given position i
• • set(i, x) – to set the value at position i to value x
• • add(i, x) – to add (insert) an element x at position i, thus increasing the size of the list
• • remove(i) – to remove the element at position i, thus decreasing the size of the list

Implementations

Array-based List

• Elements stored in contiguous memory.
• Fast access by index (O(1))
• slower insert/delete in the middle (O(n)).

Python Built-in List

# List ADT operations using Python list
my_list = [10, 20, 30]
my_list.append(40)      # Add to end
my_list.insert(1, 15)   # Insert at index
del my_list[0]          # Remove by index
my_list.remove(20)      # Remove by value
val = my_list[0]        # Access
length = len(my_list)   # Size

Python Class Implementation

class List:
    def __init__(self):
        """Initialize an empty list."""
        self.items = []
 
    def get(self, position):
        """Return the element at the given position."""
        return self.items[position]
  
    def add(self, n):
        """Append an element at the end of the list."""
        self.items.append(n)
 
    def add_at(self, position, n):
        """Insert an element at the specified position."""
        self.items.insert(position, n)
 
    def set(self, position, n):
        """Update the element at the given position."""
        self.items[position] = n
 
    def remove(self, position):
        """Remove and return the element at the specified position."""
        return self.items.pop(position)

Usage

# Create a new List
my_list = List()
 
# Add elements at the end
my_list.add(10)
my_list.add(20)
my_list.add(30)
print("After adding elements:", my_list.items)  
# Output: [10, 20, 30]
 
# Insert an element at a specific position
my_list.add_at(1, 15)  
print("After inserting 15 at index 1:", my_list.items)  
# Output: [10, 15, 20, 30]
 
# Access elements by index
print("Element at index 2:", my_list.get(2))  
# Output: 20
 
# Update an element
my_list.set(2, 25)  
print("After setting index 2 to 25:", my_list.items)  
# Output: [10, 15, 25, 30]
 
# Remove an element
removed = my_list.remove(1)  
print("Removed element:", removed)  
print("After removal:", my_list.items)  
# Output: Removed element: 15
# Output: [10, 25, 30]

Linked List

• Elements stored in nodes connected by pointers.
• Slower access by index (O(n))
• faster insert/delete at arbitrary positions (O(1) if you have the node).