Linked list

related topics
{math, number, function}
{system, computer, user}
{style, bgcolor, rowspan}
{work, book, publish}
{group, member, jewish}
{build, building, house}
{household, population, female}
{album, band, music}
{car, race, vehicle}

In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

Linked lists are among the simplest and most common data structures; they provide an easy implementation for several important abstract data structures, including stacks, queues, associative arrays, and symbolic expressions.

The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk. For that reason, linked lists allow insertion and removal of nodes at any point in the list, with a constant number of operations.

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

Linked lists can be implemented in most languages. Functional languages such as Lisp and Scheme have the data structure built in, along with operations to access the linked list. Procedural languages, such as C, or object-oriented languages, such as C++ and Java, typically rely on mutable references to create linked lists.

Contents

Full article ▸

related documents
Computer numbering formats
Field (mathematics)
Binary search algorithm
Fibonacci number
Bernoulli number
Turing machine
C++
Distribution (mathematics)
Quadratic reciprocity
Spinor
Trigonometric functions
System of linear equations
Prolog
Mandelbrot set
Laplace transform
Relational model
Wikipedia:Free On-line Dictionary of Computing/R - S
Combinatory logic
Linear programming
Big O notation
Forth (programming language)
History of mathematics
Red-black tree
Banach–Tarski paradox
Formal power series
Lebesgue integration
Objective-C
Lambda calculus
P-adic number
Determinant