prepend

Prepend is an operation that adds an element to the beginning of a sequence, placing it before all existing elements. It is commonly described as the opposite of append. The term derives from Latin prae- meaning before and pendere meaning to hang, reflecting the idea of hanging something before the rest.

In data structures and algorithms, the cost and method of prepending depend on the structure. For linked lists, prepending is typically O(1) because a new node is created that points to the current head. In arrays and array-backed lists, prepending usually requires shifting or copying existing elements, which is O(n). With immutable strings, prepending a substring creates a new string, often involving copying both parts.

In programming languages, prepend is often implemented by a dedicated operator or function. The cons operator in Lisp and the (:) operator in Haskell prepend an element to the front of a list. In JavaScript, unshift adds one or more elements to the beginning of an array. In Python, prepending can be performed with [x] + lst or, less efficiently, with lst.insert(0, x), since insertion at the front is typically O(n).

Examples illustrate the concept. Python: l = [2, 3, 4]; l = [1] + l yields [1, 2, 3, 4]. Haskell: 1 : [2, 3, 4] yields [1, 2, 3, 4]. Lisp: (cons 1 '(2 3 4)) returns (1 2 3 4). When choosing a prepending method, considerations include the data structure’s mutability and performance implications, particularly for large sequences or repeated operations.