View source for Linked data structure

In [[computer science]], a '''linked data structure''' is a [[data structure]] which consists of a set of [[Data record (computer science)|data records]] ([[Node (computer science)|nodes]]) linked together and organized by [[Reference (computer science)|references]] (links or [[Pointer (computer programming)|pointers]]).

The link between data can also be called a connector.

== Description ==

In linked data structures, the links are usually treated as special data types that can only be dereferenced or compared for equality.

Linked data structures are thus contrasted with [[arrays]] 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 indices: as long as no arithmetic is done on those indices, the data structure is essentially a linked one.

Linking can be done in two ways:

* [[Dynamic allocation]]
* [[Array index linking]]

Linked data structures include many other widely used data structures:

* [[Linked lists]]
* [[Search trees]]
* [[Expression trees]]

They are also key building blocks for many efficient algorithms, such as topological sort and set union-find.

== See also ==

* [[Data record (computer science)]]
* [[Expression tree]]
* [[Linked list]]
* [[List of data structures]]
* [[Pointer (computer programming)]]
* [[Reference (computer science)]]
* [[Search tree]]

== External links ==

* [https://en.wikipedia.org/wiki/Linked_data_structure Linked data structure] @ Wikipedia



[[Category:Computer science]]
[[Category:Data structures]]