Operations

1. Create an empty list.
2. Insert a value at a permitted position.
3. Delete an element or selected occurrence.
4. Retrieve, search or update a value.
5. Traverse all elements and obtain the current size when needed.

Logical versus physical order

In an array list, consecutive logical positions normally occupy consecutive element positions. In a linked list, explicit links describe the sequence even when nodes are physically separate. Neither representation requires the values themselves to be sorted.

Example

The list 10, 30, 20 has a first value 10 and last value 20. Inserting 15 after the first value produces 10, 15, 30, 20. Deleting 30 produces 10, 15, 20. The operation contract should specify whether positions are zero-based and whether duplicate values are allowed.

Boundary cases

An empty list has no first element to read or remove. Insertion can create its first element. Deleting the only element must restore a valid empty representation. Reject invalid positions rather than writing outside storage or following a missing link.

Complexity

The logical list does not prescribe one performance table. Arrays support O(1) indexed retrieval but may shift O(n) elements on insertion. Singly linked lists require O(n) indexed traversal, while head insertion uses O(1) link work. Choose and document the implementation.