A list is an ordered collection of elements, commonly used as a fundamental data structure in computer science and programming. Lists allow for the storage, retrieval, and manipulation of sequences of items, which can be of any data type (e.g., numbers, strings, objects). They are distinguished from arrays by features such as dynamic sizing, heterogeneous elements, and built-in methods for insertion, deletion, and iteration. Lists appear across programming languages (e.g., Python, Java, Lisp) and in non‑computational contexts (e.g., to‑do lists, inventories) as a simple way to organize data.

1 Overview and definitions

1.1 General concept

A list is a finite, ordered sequence of zero or more elements. The order is preserved from the first element (the head) to the last (the tail). Lists are often abstracted as a linear arrangement where each element (except the first) has a unique predecessor and each (except the last) a unique successor. In computing, lists serve as mutable or immutable containers and are typically accessed by position (index) or by iteration.

1.2 List vs. array vs. tuple

Lists, arrays, and tuples all represent ordered collections but differ in key properties. An array is typically a fixed‑size, homogeneous block of memory with constant‑time index access; lists are often dynamic and can grow or shrink. A tuple is an immutable ordered collection—once created its length and elements cannot change. Lists are usually mutable. Additionally, arrays in many languages (e.g., C, Java) store elements of a single type, whereas lists may allow mixed types.

1.2.1 Mutable vs. immutable lists

Mutable lists allow in‑place modification—adding, removing, or changing elements without creating a new list. Immutable lists (or persistent lists) return a new list with each modification, leaving the original unchanged. Functional programming languages (e.g., Clojure, Haskell) favor immutable lists to avoid side effects.

1.2.2 Homogeneous vs. heterogeneous lists

Homogeneous lists contain elements of the same type (e.g., a list of integers). Heterogeneous lists can store items of different types (e.g., integers, strings, objects). Many dynamically typed languages (Python, JavaScript) support heterogeneous lists by default; statically typed languages often require a generic or union type to achieve heterogeneity.

2 Types of lists in computing

2.1 Linear lists

Linear lists maintain a one‑to‑one sequential relationship between elements. The most common linear list implementations are based on linked nodes or dynamic arrays.

2.1.1 Singly linked lists

A singly linked list consists of nodes, each containing a data value and a pointer (or reference) to the next node. The list is traversed from the head node to the tail node, which points to null. Insertion and deletion at the head are O(1); access by index requires O(n) traversal.

2.1.2 Doubly linked lists

Each node in a doubly linked list holds pointers to both the next and the previous node. This enables bidirectional traversal and O(1) insertion or deletion at both ends, at the cost of extra memory per node.

2.1.3 Circular lists

In a circular list, the last node’s pointer (next in singly, also prev in doubly) points back to the first node, forming a ring. Circular lists are useful for round‑robin scheduling and buffer management.

2.2 Abstract data types (ADTs)

An abstract data type (ADT) defines a list by its behavior—operations such as insert, delete, get, and size—rather than by its underlying implementation.

2.2.1 Dynamic array lists

A dynamic array list (e.g., Python’s list, Java’s ArrayList) uses a contiguous array that can be resized. When the array is full, a new, larger array is allocated and the old elements are copied over. This provides O(1) amortized insertion at the end and O(n) insertion in the middle.

2.2.1.1 Amortized resizing strategies

Common resizing strategies include doubling the capacity each time the array is full or using a geometric growth factor (e.g., 1.5x). The cost of periodic copies is amortized over many insertions, yielding O(1) average time per operation.

2.2.2 Stack and queue as list specializations

A stack follows last‑in, first‑out (LIFO) order—elements are added (pushed) and removed (popped) only at one end (the top). A queue follows first‑in, first‑out (FIFO) order—elements are added at the rear and removed from the front. Both can be implemented using a dynamic array or linked list.

2.2.3 Deque (double‑ended queue)

A deque extends the queue ADT by allowing insertion and removal at both ends. It is typically implemented with a dynamic array (circular buffer) or a doubly linked list, providing O(1) operations at both ends.

2.3 Specialized list variants

2.3.1 Sparse lists

A sparse list stores only non‑default or non‑zero elements, often in a linked structure or a dictionary of indices. Memory is saved when the list is mostly empty or filled with a default value.

2.3.2 Skip lists

A skip list is a multi‑level linked list where higher levels “skip” over several nodes, providing faster search, insertion, and deletion—O(log n) on average. It is often used as an alternative to balanced trees.

2.3.2.1 Probabilistic balancing

Skip lists use randomization: each node is promoted to the next level with a fixed probability (commonly 1/2). This probabilistic process ensures approximate O(log n) performance without the rebalancing overhead of tree structures.

2.3.3 Immutable (persistent) lists

Persistent lists preserve all previous versions after updates. Typically implemented as linked structures (e.g., singly linked with sharing), they allow efficient branching and are central to functional programming languages.

3 Implementations and language support

3.1 Python: list built‑in methods

Python’s list is a dynamic array that supports mixed types. Common methods include append, extend, insert, remove, pop, index, count, sort, reverse, and slicing via list[start:stop:step]. List comprehensions provide concise element generation.

3.2 Java: ArrayList vs. LinkedList

Java provides two primary list implementations: ArrayList (dynamic array) and LinkedList (doubly linked). ArrayList offers O(1) positional access and O(n) middle insertion; LinkedList offers O(1) insertion/removal at ends but O(n) search. Both implement the List interface.

3.3 Functional languages: Lisp cons cells

In Lisp, lists are built from cons cells—pairs of a value (car) and a pointer to the rest of the list (cdr). The empty list is nil. This recursive structure makes list processing natural with functions like car, cdr, cons, and append.

3.4 JavaScript: arrays as lists

JavaScript arrays are dynamic, resizable, and can hold heterogeneous elements. Despite the name “array,” they behave more like lists, providing methods such as push, pop, shift, unshift, splice, slice, forEach, map, and filter.

4 Common operations and algorithms

4.1 Traversal and iteration

Traversing a list means visiting each element in order. Iteration can be implemented with loops (while, for) or recursive calls. Performance is O(n) for linear lists.

4.1.1 For‑each vs. index‑based loops

For‑each loops (e.g., Python’s for x in lst) iterate directly over elements without an explicit index. Index‑based loops (e.g., for i in range(len(lst))) provide access to the position but may be slower in languages with linked lists due to O(n) indexing.

4.2 Search and lookup

Linear search checks each element sequentially until a match is found or the list ends. It runs in O(n) time and is suitable for unsorted lists.

4.2.2 Binary search on sorted lists

Binary search repeatedly divides the sorted list in half, comparing the target to the middle element. It runs in O(log n) time but requires random‑access indexing (e.g., dynamic arrays) or specialized linked structures (e.g., skip lists).

4.3 Modification

4.3.1 Insertion at head/tail/middle

Insertion at the head (front) is O(1) for linked lists but O(n) for dynamic arrays (which must shift all elements). Insertion at the tail is O(1) amortized for dynamic arrays and O(1) for linked lists (if a tail pointer is maintained). Middle insertion requires shifting (array) or pointer manipulation (linked list) and is O(n).

4.3.2 Deletion by value/position

Deleting by value typically requires O(n) search plus O(1) or O(n) removal depending on list type. Deletion by position (index) is O(1) for linked lists (given a pointer) and O(n) for arrays due to shifting.

4.3.3 Reversal, concatenation, slicing

Reversing a list can be done in O(n) time by iterating with multiple pointers (for linked) or using built‑in methods (e.g., Python’s reverse()). Concatenation of two lists is O(1) for linked lists (if tail pointer is updated) and O(n) for arrays (copying elements). Slicing creates a new list from a contiguous subsequence; for dynamic arrays this is O(k) (where k is slice length).

5 Use cases and applications

5.1 Data storage and processing

5.1.1 Staging input data streams

Lists serve as buffers to hold data arriving from files, networks, or user input. A program can read a stream into a list, then process the data sequentially or by index.

5.1.2 Implementing adjacency lists for graphs

In graph algorithms, an adjacency list stores for each vertex a list of its neighbors. This representation saves memory for sparse graphs and is commonly implemented with lists (e.g., list[list[int]] in Python).

5.2 User‑interface component

5.2.1 E‑commerce product lists

Online shopping websites display product listings as ordered, scrollable lists. Each item is a list entry containing name, price, image, etc. User interaction (sorting, filtering) operates on the underlying data list.

5.2.2 Inbox and notification feeds

Email inboxes and social‑media notification feeds are ordered lists of messages or activities. The list grows as new items are appended and is often rendered with infinite scrolling or pagination.

5.3 Mathematical and combinatorial contexts

5.3.1 Permutations and sequences

Lists represent permutations (ordered arrangements) and are used in combinatorial algorithms to generate, store, and compare sequences.

5.3.2 Polynomial representation

A polynomial can be represented as a list of coefficients, where the index corresponds to the exponent (e.g., [3, 0, 5] for 3 + 5x²). This enables efficient addition and evaluation.

6 Diagrams and notation

6.1 Visual representation of linked lists

A linked list is often drawn as a chain of boxes (nodes) separated by arrows. For example: `[datanext] → [datanext] → [datanull]`. Doubly linked lists show arrows in both directions. Circular lists indicate a loop from the last node back to the first.

6.2 Formal notation: set‑theoretic and Lisp notation

In set theory, a list can be denoted as an ordered tuple: ⟨a₁, a₂, …, aₙ⟩. Lisp notation uses parentheses: (a b c). The empty list is represented as (). The cons operation constructs a new list: (cons x lst).

7.1 Sequences (deque, vector)

Deques and vectors are sequence ADTs that extend or restrict list behavior. A vector (in functional languages) is an immutable, indexable sequence with efficient random access. The deque (double‑ended queue) is a specialization of a list optimized for operations at both ends.

7.2 Associative structures (hash maps, trees)

While lists store elements by position, associative structures like hash maps and trees store key‑value pairs for lookup by key. Lists are often used as buckets in hash‑map implementations (separate chaining) or as ordered lists in tree‑based structures.

7.3 Buffers and streams

A buffer is a list‑like container used for temporary storage of data being transferred between devices or processes. Streams are abstract sequences of data that can be read or written incrementally, often backed by lists or arrays.