Array list

Contiguous elements permit direct indexed access and good locality. Fixed-capacity arrays need an overflow policy, while a dynamic array needs allocation management. Inserting or deleting in the middle can shift O(n) elements.

Singly linked list

Each node has a next link. Head insertion needs O(1) link work, but finding an arbitrary position or predecessor may take O(n). Nodes can be allocated separately as the list grows, with allocation failures handled.

Circular singly linked list

The last link returns to the first. A tail-based representation supports constant link work at the beginning and end and suits cycling tasks. Traversal must stop when it returns to its start, not when it sees NULL.

Doubly linked list

Each node has previous and next links. A known node can be removed using its neighbours without a predecessor search. More memory and more careful link updates are required. Searching by value remains linear.

Choosing and counting

Include the cost of locating a position before claiming an update is constant time. All n-element representations need O(n) data storage; linked representations add per-node links and allocator overhead. A maintained tail helps append but does not create random access. Choose the simplest representation meeting the required workload.

Reference table