Educational ordered linked list implementation with automatic sorting, comprehensive examples, and thorough documentation.
This package provides a complete implementation of an ordered linked list data structure that automatically maintains elements in ascending sorted order. Perfect for learning about sorted linked lists, linked list algorithms, and maintaining ordered data.
- Automatic Sorting: All insertions maintain ascending order
- Complete API: Insert, search, remove, index, pop, and utility operations
- Educational Focus: Well-documented code with complexity analysis
- Type Hints: Full type annotations for better IDE support
- Python Integration: Supports len(), in, iteration, and indexing
- Interactive CLI: Comprehensive demonstrations and use cases
- Extensive Tests: 50+ tests covering all operations and edge cases
# Clone the repository
git clone https://github.com/maxwell-hauser/ordered-list-examples.git
cd ordered-list-examples
# Install the package
pip install -e .- Python 3.9 or higher
- pytest (for running tests)
from ordered_list_examples import OrderedList
# Create an ordered list
ol = OrderedList()
# Add elements in any order - they're automatically sorted
ol.add(30)
ol.add(10)
ol.add(20)
print(ol) # Output: [10, 20, 30]
# Search for elements
print(20 in ol) # Output: True
# Get index of element
print(ol.index(20)) # Output: 1
# Access by index
print(ol[0]) # Output: 10
# Remove elements
ol.remove(20)
print(ol) # Output: [10, 30]
# Iterate over elements
for item in ol:
print(item)# Run interactive demonstrations
ordered-list-demo
# Or run directly with Python
python -m ordered_list_examples.cli# Run all tests
pytest
# Run with verbose output
pytest -v
# Run specific test file
pytest tests/test_ordered_list.py| Operation | Time Complexity | Description |
|---|---|---|
add(item) |
O(n) | Must find insertion point to maintain order |
search(item) |
O(n) | Linear search with early termination |
remove(item) |
O(n) | Must find element to remove |
index(item) |
O(n) | Must traverse to find element |
pop() |
O(n) | Must traverse to last element |
pop(pos) |
O(n) | Must traverse to specific position |
get_item(pos) |
O(n) | Must traverse to position |
is_empty() |
O(1) | Check head only |
size() / len() |
O(n) | Must count all elements |
clear() |
O(1) | Remove reference to head |
reverse() |
O(n) | Must traverse and reverse links |
delete_duplicates() |
O(n) | Single pass through list |
count_item(item) |
O(n) | Must check all elements |
- Storage: O(n) where n is the number of elements
- Operations: O(1) auxiliary space for all operations
class OrderedList:
def __init__(self)
def add(self, item: Any) -> None
def search(self, item: Any) -> bool
def remove(self, item: Any) -> None
def index(self, item: Any) -> int
def pop(self, pos: Optional[int] = None) -> Any
def get_item(self, pos: int) -> Any
def is_empty(self) -> bool
def size(self) -> int
def clear(self) -> None
def reverse(self) -> None
def delete_duplicates(self) -> None
def count_item(self, item: Any) -> int
def to_list(self) -> list
# Magic methods
def __len__(self) -> int
def __contains__(self, item: Any) -> bool
def __iter__(self) -> Iterator[Any]
def __getitem__(self, index: int) -> Any
def __str__(self) -> str
def __repr__(self) -> strclass Node:
def __init__(self, data: Any)
def get_data(self) -> Any
def get_next(self) -> Optional['Node']
def set_data(self, new_data: Any) -> None
def set_next(self, new_next: Optional['Node']) -> Nonefrom ordered_list_examples import OrderedList
# Automatically maintain leaderboard scores
leaderboard = OrderedList()
leaderboard.add(850) # Alice
leaderboard.add(920) # Bob
leaderboard.add(780) # Charlie
# Always sorted: [780, 850, 920]
print(f"Top score: {leaderboard[-1]}")# Lower numbers = higher priority
task_queue = OrderedList()
task_queue.add(5) # Low priority
task_queue.add(1) # High priority
task_queue.add(3) # Medium priority
# Process highest priority first
while not task_queue.is_empty():
priority = task_queue.pop(0)
print(f"Processing task with priority {priority}")data = OrderedList()
for value in [15, 8, 23, 4, 16]:
data.add(value)
sorted_data = list(data)
mid = len(sorted_data) // 2
median = sorted_data[mid] if len(sorted_data) % 2 == 1 else \
(sorted_data[mid-1] + sorted_data[mid]) / 2
print(f"Current median: {median}")ol = OrderedList()
for val in [5, 3, 5, 1, 3, 1]:
ol.add(val)
# Count duplicates
for val in sorted(set(ol)):
count = ol.count_item(val)
print(f"Value {val} appears {count} times")
# Remove duplicates
ol.delete_duplicates()
print(f"Unique values: {ol}")The test suite includes:
- Node Tests: Initialization, data/next manipulation, string representation
- Basic Operations: Add, search, remove with various data patterns
- Index Operations: Finding elements, accessing by position, error handling
- Pop Operations: Remove from end, specific positions, empty list handling
- Duplicate Handling: Counting, removing consecutive duplicates
- Iteration: For loops, list conversion, empty list iteration
- Utility Operations: Clear, reverse, string representations
- Edge Cases: Mixed types, negative numbers, large lists, operations after reverse
- Magic Methods: len(), in, [], iter(), str(), repr()
Run tests with:
pytest tests/test_ordered_list.py -vordered_list_examples/
├── src/
│ └── ordered_list_examples/
│ ├── __init__.py # Package initialization
│ ├── ordered_list.py # OrderedList and Node implementations
│ └── cli.py # Interactive demonstrations
├── tests/
│ └── test_ordered_list.py # Comprehensive test suite
├── scripts/
│ └── verify.ps1 # PowerShell verification script
├── .github/
│ └── workflows/
│ ├── ci.yml # Continuous integration
│ └── release.yml # Release automation
├── pyproject.toml # Project configuration
├── LICENSE # MIT License
└── README.md # This file
| Feature | OrderedList | Python list |
|---|---|---|
| Maintains sort order | Yes (automatic) | No (manual sort) |
| Index access | O(n) | O(1) |
| Search | O(n) early-stop | O(n) |
| Insert at position | O(n) sorted | O(n) |
| Append | O(n) sorted | O(1) |
| Remove by value | O(n) | O(n) |
| Memory overhead | Higher (node refs) | Lower (array) |
Use OrderedList when:
- You need automatic sorting on insertion
- Sort order is more important than fast random access
- You're learning about linked list data structures
- You want to avoid explicit sorting calls
Use Python list when:
- You need fast random access by index
- You don't need automatic sorting
- Memory efficiency is critical
- You're working with large datasets
This implementation is designed for learning:
- Linked List Fundamentals: Node-based structure, pointer manipulation
- Sorted Data Structures: Maintaining order during insertions
- Algorithm Complexity: Understanding O(n) vs O(1) operations
- Python Integration: Implementing magic methods and protocols
- Testing Practices: Comprehensive test coverage patterns
- Software Design: Clean API, type hints, documentation
# PowerShell verification script
.\scripts\verify.ps1Contributions are welcome! Please ensure:
- All tests pass:
pytest tests/ - Code follows existing style and documentation standards
- New features include corresponding tests
- Docstrings are complete and accurate
Authored 20 November, 2025 by Maxwell Hauser
This project is licensed under the MIT License. See the LICENSE file for details.
- Linked Lists: Foundation for dynamic data structures
- Sorted Data Structures: Binary search trees, skip lists, heaps
- Algorithm Design: Trade-offs between time and space complexity
- Python Data Model: Special methods and operator overloading
For issues, questions, or contributions, please visit the GitHub repository or contact the author through https://www.ambersartisanalknits.com