Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Linked data structure
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a linked data structure is a <a href="/facts/Data_structure/yNsNvL1I">data structure</a> which consists of a set of <a href="/facts/Record_(computer_science)/1fvSgenB">data records</a> (<i><a href="/facts/Node_(computer_science)/eYlvVE0z">nodes</a></i>) linked together and organized by <a href="/facts/Reference_(computer_science)/1vm2Bph1">references</a> (<i>links</i> or <i><a href="/facts/Pointer_(computer_programming)/fPoNzy9b">pointers</a></i>). The link between data can also be called a connector. </p><p>In linked data structures, the links are usually treated as special <a href="/facts/Data_type/fcx5hgVL">data types</a> that can only be <a href="/facts/Reference_(computer_science)/1vm2Bph1">dereferenced</a> or compared for equality. Linked data structures are thus contrasted with <a href="/facts/Array_data_structure/BKGvF8AM">arrays</a> and other data structures that require performing arithmetic operations on pointers. This distinction holds even when the nodes are actually implemented as elements of a single array, and the references are actually array <a href="/facts/Array_data_structure/BKGvF8AM">indices</a>: as long as no arithmetic is done on those indices, the data structure is essentially a linked one. </p><p>Linking can be done in two ways – using dynamic allocation and using array index linking. </p><p>Linked data structures include <a href="/facts/Linked_list/Ik4JTgJW">linked lists</a>, <a href="/facts/Search_tree/zJIIMEH8">search trees</a>, <a href="/facts/Expression_tree/HqbKYU43">expression trees</a>, and many other widely used data structures. They are also key building blocks for many efficient algorithms, such as <a href="/facts/Topological_sort/VY7gNtYA">topological sort</a> and <a href="/facts/Disjoint-set_data_structure/QnFQNedE">set union-find</a>. </p>