Editing Linked list (section)

{{Short description|Data structure with nodes pointing to the next node}}
{{Redirect|Dynamic list|text=For the Wikipedia guideline which describes list articles which may never be completed, see [[Wikipedia:WikiProject Lists]].}}
{{More footnotes needed|date=March 2012}}
[[File:Singly-linked-list.svg|frame|A linked list is a sequence of nodes that contain two fields: data (an integer value here as an example) and a link to the next node. The last node is linked to a terminator used to signify the end of the list.]]
In [[computer science]], a '''linked list''' is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element [[pointer (computer programming)|points]] to the next. It is a [[data structure]] consisting of a collection of [[node (computer science)|node]]s which together represent a [[sequence]]. In its most basic form, each node contains [[Data (computing)|data]], and a [[reference (computer science)|reference]] (in other words, a ''link'') to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that data access time is [[Time complexity|linear]] in respect to the number of nodes in the list. Because nodes are serially linked, accessing any node requires that the prior node be accessed beforehand (which introduces difficulties in [[instruction pipelining|pipelining]]). Faster access, such as random access, is not feasible. [[Array data structure|Arrays]] have better [[locality of reference|cache locality]] compared to linked lists.

Linked lists are among the simplest and most common data structures. They can be used to implement several other common [[abstract data type]]s, including [[List (abstract data type)|lists]], [[Stack (abstract data type)|stacks]], [[Queue (abstract data type)|queues]], [[associative array]]s, and [[S-expression]]s, though it is not uncommon to implement those data structures directly without using a linked list as the basis.

The principal benefit of a linked list over a conventional [[array data structure|array]] is that the list elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items do not need to be stored [[wikt:contiguous|contiguously]] in memory or on disk, while restructuring an array at [[Run time (program lifecycle phase)|run-time]] is a much more expensive operation. Linked lists allow insertion and removal of nodes at any point in the list, and allow doing so with a constant number of operations by keeping the link previous to the link being added or removed in memory during list traversal.

On the other hand, since simple linked lists by themselves do not allow [[random access]] to the data or any form of efficient indexing, many basic operations—such as obtaining the last node of the list, finding a node that contains a given datum, or locating the place where a new node should be inserted—may require iterating through most or all of the list elements.