Linked List

In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum 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. They can be used to implement several other common abstract data types, including stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation.

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.

On the other hand, 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 scanning most or all of the list elements.

Read more about Linked ListHistory, Basic Concepts and Nomenclature, Tradeoffs, Linked List Operations, Linked Lists Using Arrays of Nodes, Language Support, Internal and External Storage, Speeding Up Search, Related Data Structures

Other articles related to "linked list, linked lists, list, linked":

Microsoft Interview - Further Information - Interview Questions Previously Used By Microsoft
... What do you do? You have a linked list and don't know how long it is how do you find the middle of it? How would you test a keyboard? How would you test a pen? Write code for finding a duplicate in an array ... Reverse a Singly Linked List with and without using Recursion ... Find cycles in a singly linked list, using minimal storage ...
Linked List - 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 ...
B+ Tree - Implementation
... leaves (the bottom-most index blocks) of the B+ tree are often linked to one another in a linked list this makes range queries or an (ordered) iteration through ... over a B-tree in a B-tree, since not all keys are present in the leaves, such an ordered linked list cannot be constructed ... space taken up by the index blocks (for example, the linked list references in the leaf blocks) ...
PDP-8 - Examples - Linked List
... Another possible subroutine for the PDP-8 was a linked list ... GETN, 0 /Gets the number pointed to and moves the pointer CLA CLL /Clear accumulator TAD I PTR /Gets the number pointed to DCA TEMP /Save current value ISZ PTR /Increment pointer TAD I PTR /Get next address DCA PTR /Put in pointer JMP I GETN /return PTR, 0 TEMP, 0 ...
Unrolled Linked List
... In computer programming, an unrolled linked list is a variation on the linked list which stores multiple elements in each node ... cache performance, while decreasing the memory overhead associated with storing list metadata such as references ...

Famous quotes containing the words list and/or linked:

    We saw the machinery where murderers are now executed. Seven have been executed. The plan is better than the old one. It is quietly done. Only a few, at the most about thirty or forty, can witness [an execution]. It excites nobody outside of the list permitted to attend. I think the time for capital punishment has passed. I would abolish it. But while it lasts this is the best mode.
    Rutherford Birchard Hayes (1822–1893)

    In the dominant Western religious system, the love of God is essentially the same as the belief in God, in God’s existence, God’s justice, God’s love. The love of God is essentially a thought experience. In the Eastern religions and in mysticism, the love of God is an intense feeling experience of oneness, inseparably linked with the expression of this love in every act of living.
    Erich Fromm (1900–1980)