A data structure is a particular way of organizing data in a computer so that it can be used effectively, while an algorithm is a step-by-step procedure that defines a set of instructions to be executed in a certain order to produce the desired output. Together, these two concepts form the backbone of computer science, since the choice of data structure profoundly affects the efficiency of any algorithm that operates on it. To reason about efficiency, we use Big O notation, which describes the upper bound of an algorithm's time complexity and represents its worst-case scenario. Time complexity measures the amount of time an algorithm takes to run as a function of the input length, while space complexity measures the working storage it requires. Amortized analysis, a complementary technique, considers the average cost of an operation over a sequence of operations rather than the worst-case cost of a single one, which is especially useful for structures like dynamic arrays. The Master Theorem provides a direct solution for recurrence relations of the form \(T(n) = aT(n/b) + f(n)\), which commonly arise in divide-and-conquer analyses.
The simplest and most widely used data structures are linear collections. An array stores multiple items of the same type at contiguous memory locations, enabling fast random access but at the cost of a fixed size. A linked list, by contrast, stores elements at non-contiguous memory locations connected via pointers, giving it dynamic size and easier insertions and deletions, though it sacrifices fast indexed access. Several linked list variants exist: a doubly linked list contains both a previous and next pointer, a circular linked list forms a closed ring with no NULL end, an XOR linked list stores the XOR of two pointers to save space, and an unrolled linked list stores an array of elements in each node to improve cache locality. A dynamic array, supplied as a standard library in most modern languages, simulates the convenience of a variable-size list while preserving the random-access performance of contiguous storage. The Iterator pattern decouples traversal logic from the underlying container, allowing different data structures to be enumerated uniformly.
Beyond general-purpose lists, two specialized linear structures dictate the order of operations. A stack follows LIFO (Last In First Out) or FILO (First In Last Out) order, supporting the main operations Push (add an item), Pop (remove an item), Peek or Top (view the top item), and isEmpty (check whether it is empty). A queue follows FIFO (First In First Out) order, with Enqueue (add an item), Dequeue (remove an item), Front (get the first item), and Rear (get the last item) as its primary operations. A priority queue is an extension of the queue in which every item carries a priority, so that an element with high priority is dequeued before one with low priority. These structures underpin the management of function calls, breadth-first search, scheduling, and many other computational tasks, making them essential building blocks for more sophisticated algorithms.