Difference between revisions of "Linked list"

Latest revision as of 15:43, 20 April 2016

In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence.

Description

Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links.

This structure allows for efficient insertion or removal of elements from any position in the sequence.

Linked lists are among the simplest and most common data structures.

Integer value and link to next node

A linked list whose nodes contain two fields: an integer value and a link to the next node.

The last node is linked to a terminator used to signify the end of the list.

Basis for other abstract data types

They can be used to implement several other common abstract data types, including:

• Lists (the abstract data type)
• Stacks
• Queues
• Associative arrays
• S-expressions

It is not uncommon to implement these other data structures directly without using a list as the basis of implementation.

Advantages

The principal benefit of a linked list over a conventional array is that the list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk

Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.

An array, by contrast, has to be declared in the source code, before compiling and running the program.

Disadvantages

Simple 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 (assuming that the last node is not maintained as separate node reference in the list structure), or finding a node that contains a given datum, or locating the place where a new node should be inserted -- may require sequential scanning of most or all of the list elements.

Related data structures

Both stacks and queues are often implemented using linked lists, and simply restrict the type of operations which are supported.

The skip list is a linked list augmented with layers of pointers for quickly jumping over large numbers of elements, and then descending to the next layer. This process continues down to the bottom layer, which is the actual list.

A binary tree can be seen as a type of linked list where the elements are themselves linked lists of the same nature. The result is that each node may include a reference to the first node of one or two other linked lists, which, together with their contents, form the subtrees below that node.

An unrolled linked list is a linked list in which each node contains an array of data values. This leads to improved cache performance, since more list elements are contiguous in memory, and reduced memory overhead, because less metadata needs to be stored for each element of the list.

A hash table may use linked lists to store the chains of items that hash to the same position in the hash table.

A heap shares some of the ordering properties of a linked list, but is almost always implemented using an array. Instead of references from node to node, the next and previous data indexes are calculated using the current data's index.

A self-organizing list rearranges its nodes based on some heuristic which reduces search times for data retrieval by keeping commonly accessed nodes at the head of the list.

See also

• Computer science
• Data structure
• Hash table
• Node (computer science)
• Sequence

External links

• Linked list @ Wikipedia