Linked list

From Wikipedia for FEVERv2
Jump to navigation Jump to search

"Dynamic list" redirects here. Linked list_sentence_0

For the Wikipedia guideline which describes list articles which may never be completed, see Wikipedia:WikiProject Lists. Linked list_sentence_1

In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Linked list_sentence_2

Instead, each element points to the next. Linked list_sentence_3

It is a data structure consisting of a collection of nodes which together represent a sequence. Linked list_sentence_4

In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence. Linked list_sentence_5

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

More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. Linked list_sentence_7

A drawback of linked lists is that access time is linear (and difficult to pipeline). Linked list_sentence_8

Faster access, such as random access, is not feasible. Linked list_sentence_9

Arrays have better cache locality compared to linked lists. Linked list_sentence_10

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

They can be used to implement several other common abstract data types, including lists, stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement those data structures directly without using a linked list as the basis. Linked list_sentence_12

The principal benefit of a linked list over a conventional array is that the list elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored in memory or on disk, while restructuring an array at run-time is a much more expensive operation. Linked list_sentence_13

Linked lists allow insertion and removal of nodes at any point in the list, and allow doing so with a constant number of operations by keeping the link previous to the link being added or removed in memory during list traversal. Linked list_sentence_14

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

The advantages and disadvantages of using linked lists are given below. Linked list_sentence_16

Linked list are dynamic, so the length of list can increase or decrease as necessary. Linked list_sentence_17

Each node does not necessarily follow the previous one physically in the memory. Linked list_sentence_18

Disadvantages Linked list_section_0

Linked list_unordered_list_0

  • They use more memory than arrays because of the storage used by their pointers.Linked list_item_0_0
  • Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.Linked list_item_0_1
  • Nodes are stored noncontiguously, greatly increasing the time periods required to access individual elements within the list, especially with a CPU cache.Linked list_item_0_2
  • Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly-linked lists are cumbersome to navigate backward and while doubly linked lists are somewhat easier to read, memory is consumed in allocating space for a back-pointer.Linked list_item_0_3

History Linked list_section_1

Linked lists were developed in 1955–1956 by Allen Newell, Cliff Shaw and Herbert A. Simon at RAND Corporation as the primary data structure for their Information Processing Language. Linked list_sentence_19

IPL was used by the authors to develop several early artificial intelligence programs, including the Logic Theory Machine, the General Problem Solver, and a computer chess program. Linked list_sentence_20

Reports on their work appeared in IRE Transactions on Information Theory in 1956, and several conference proceedings from 1957 to 1959, including Proceedings of the Western Joint Computer Conference in 1957 and 1958, and Information Processing (Proceedings of the first UNESCO International Conference on Information Processing) in 1959. Linked list_sentence_21

The now-classic diagram consisting of blocks representing list nodes with arrows pointing to successive list nodes appears in "Programming the Logic Theory Machine" by Newell and Shaw in Proc. Linked list_sentence_22

WJCC, February 1957. Linked list_sentence_23

Newell and Simon were recognized with the ACM Turing Award in 1975 for having "made basic contributions to artificial intelligence, the psychology of human cognition, and list processing". Linked list_sentence_24

The problem of machine translation for natural language processing led Victor Yngve at Massachusetts Institute of Technology (MIT) to use linked lists as data structures in his COMIT programming language for computer research in the field of linguistics. Linked list_sentence_25

A report on this language entitled "A programming language for mechanical translation" appeared in Mechanical Translation in 1958. Linked list_sentence_26

LISP, standing for list processor, was created by John McCarthy in 1958 while he was at MIT and in 1960 he published its design in a paper in the Communications of the ACM, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". Linked list_sentence_27

One of LISP's major data structures is the linked list. Linked list_sentence_28

By the early 1960s, the utility of both linked lists and languages which use these structures as their primary data representation was well established. Linked list_sentence_29

Bert Green of the MIT Lincoln Laboratory published a review article entitled "Computer languages for symbol manipulation" in IRE Transactions on Human Factors in Electronics in March 1961 which summarized the advantages of the linked list approach. Linked list_sentence_30

A later review article, "A Comparison of list-processing computer languages" by Bobrow and Raphael, appeared in Communications of the ACM in April 1964. Linked list_sentence_31

Several operating systems developed by Technical Systems Consultants (originally of West Lafayette Indiana, and later of Chapel Hill, North Carolina) used singly linked lists as file structures. Linked list_sentence_32

A directory entry pointed to the first sector of a file, and succeeding portions of the file were located by traversing pointers. Linked list_sentence_33

Systems using this technique included Flex (for the Motorola 6800 CPU), mini-Flex (same CPU), and Flex9 (for the Motorola 6809 CPU). Linked list_sentence_34

A variant developed by TSC for and marketed by Smoke Signal Broadcasting in California, used doubly linked lists in the same manner. Linked list_sentence_35

The TSS/360 operating system, developed by IBM for the System 360/370 machines, used a double linked list for their file system catalog. Linked list_sentence_36

The directory structure was similar to Unix, where a directory could contain files and other directories and extend to any depth. Linked list_sentence_37

Basic concepts and nomenclature Linked list_section_2

Each record of a linked list is often called an 'element' or 'node'. Linked list_sentence_38

The field of each node that contains the address of the next node is usually called the 'next link' or 'next pointer'. Linked list_sentence_39

The remaining fields are known as the 'data', 'information', 'value', 'cargo', or 'payload' fields. Linked list_sentence_40

The 'head' of a list is its first node. Linked list_sentence_41

The 'tail' of a list may refer either to the rest of the list after the head, or to the last node in the list. Linked list_sentence_42

In Lisp and some derived languages, the next node may be called the 'cdr' (pronounced could-er) of the list, while the payload of the head node may be called the 'car'. Linked list_sentence_43

Singly linked list Linked list_section_3

Singly linked lists contain nodes which have a data field as well as 'next' field, which points to the next node in line of nodes. Linked list_sentence_44

Operations that can be performed on singly linked lists include insertion, deletion and traversal. Linked list_sentence_45

The following code demonstrates how to add a new node with data "value" to the end of a singly linked list: Linked list_sentence_46

Doubly linked list Linked list_section_4

Main article: Doubly linked list Linked list_sentence_47

In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. Linked list_sentence_48

The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous'). Linked list_sentence_49

A technique known as XOR-linking allows a doubly linked list to be implemented using a single link field in each node. Linked list_sentence_50

However, this technique requires the ability to do bit operations on addresses, and therefore may not be available in some high-level languages. Linked list_sentence_51

Many modern operating systems use doubly linked lists to maintain references to active processes, threads, and other dynamic objects. Linked list_sentence_52

A common strategy for rootkits to evade detection is to unlink themselves from these lists. Linked list_sentence_53

Multiply linked list Linked list_section_5

In a 'multiply linked list', each node contains two or more link fields, each field being used to connect the same set of data records in a different order of same set(e.g., by name, by department, by date of birth, etc.). Linked list_sentence_54

While doubly linked lists can be seen as special cases of multiply linked list, the fact that the two and more orders are opposite to each other leads to simpler and more efficient algorithms, so they are usually treated as a separate case. Linked list_sentence_55

Circular linked list Linked list_section_6

In the last node of a list, the link field often contains a null reference, a special value is used to indicate the lack of further nodes. Linked list_sentence_56

A less common convention is to make it point to the first node of the list; in that case, the list is said to be 'circular' or 'circularly linked'; otherwise, it is said to be 'open' or 'linear'. Linked list_sentence_57

It is a list where the last pointer points to the first node. Linked list_sentence_58

In the case of a circular doubly linked list, the first node also points to the last node of the list. Linked list_sentence_59

Sentinel nodes Linked list_section_7

Main article: Sentinel node Linked list_sentence_60

In some implementations an extra 'sentinel' or 'dummy' node may be added before the first data record or after the last one. Linked list_sentence_61

This convention simplifies and accelerates some list-handling algorithms, by ensuring that all links can be safely dereferenced and that every list (even one that contains no data elements) always has a "first" and "last" node. Linked list_sentence_62

Empty lists Linked list_section_8

An empty list is a list that contains no data records. Linked list_sentence_63

This is usually the same as saying that it has zero nodes. Linked list_sentence_64

If sentinel nodes are being used, the list is usually said to be empty when it has only sentinel nodes. Linked list_sentence_65

Hash linking Linked list_section_9

The link fields need not be physically part of the nodes. Linked list_sentence_66

If the data records are stored in an array and referenced by their indices, the link field may be stored in a separate array with the same indices as the data records. Linked list_sentence_67

List handles Linked list_section_10

Since a reference to the first node gives access to the whole list, that reference is often called the 'address', 'pointer', or 'handle' of the list. Linked list_sentence_68

Algorithms that manipulate linked lists usually get such handles to the input lists and return the handles to the resulting lists. Linked list_sentence_69

In fact, in the context of such algorithms, the word "list" often means "list handle". Linked list_sentence_70

In some situations, however, it may be convenient to refer to a list by a handle that consists of two links, pointing to its first and last nodes. Linked list_sentence_71

Combining alternatives Linked list_section_11

The alternatives listed above may be arbitrarily combined in almost every way, so one may have circular doubly linked lists without sentinels, circular singly linked lists with sentinels, etc. Linked list_sentence_72

Tradeoffs Linked list_section_12

As with most choices in computer programming and design, no method is well suited to all circumstances. Linked list_sentence_73

A linked list data structure might work well in one case, but cause problems in another. Linked list_sentence_74

This is a list of some of the common tradeoffs involving linked list structures. Linked list_sentence_75

Linked lists vs. dynamic arrays Linked list_section_13

Linked list_table_general_0

Comparison of list data structuresLinked list_table_caption_0
Linked list_header_cell_0_0_0 Linked listLinked list_header_cell_0_0_1 ArrayLinked list_header_cell_0_0_2 Dynamic arrayLinked list_header_cell_0_0_3 Balanced treeLinked list_header_cell_0_0_4 Random access listLinked list_header_cell_0_0_5 Hashed array treeLinked list_header_cell_0_0_6
IndexingLinked list_cell_0_1_0 Θ(n)Linked list_cell_0_1_1 Θ(1)Linked list_cell_0_1_2 Θ(1)Linked list_cell_0_1_3 Θ(log n)Linked list_cell_0_1_4 Θ(log n)Linked list_cell_0_1_5 Θ(1)Linked list_cell_0_1_6
Insert/delete at beginningLinked list_cell_0_2_0 Θ(1)Linked list_cell_0_2_1 N/ALinked list_cell_0_2_2 Θ(n)Linked list_cell_0_2_3 Θ(log n)Linked list_cell_0_2_4 Θ(1)Linked list_cell_0_2_5 Θ(n)Linked list_cell_0_2_6
Insert/delete at endLinked list_cell_0_3_0 Θ(1) when last element is known;

Θ(n) when last element is unknownLinked list_cell_0_3_1

N/ALinked list_cell_0_3_2 Θ(1) amortizedLinked list_cell_0_3_3 Θ(log n)Linked list_cell_0_3_4 N/ALinked list_cell_0_3_5 Θ(1) amortizedLinked list_cell_0_3_6
Insert/delete in middleLinked list_cell_0_4_0 search time + Θ(1)Linked list_cell_0_4_1 N/ALinked list_cell_0_4_2 Θ(n)Linked list_cell_0_4_3 Θ(log n)Linked list_cell_0_4_4 N/ALinked list_cell_0_4_5 Θ(n)Linked list_cell_0_4_6
Wasted space (average)Linked list_cell_0_5_0 Θ(n)Linked list_cell_0_5_1 0Linked list_cell_0_5_2 Θ(n)Linked list_cell_0_5_3 Θ(n)Linked list_cell_0_5_4 Θ(n)Linked list_cell_0_5_5 Θ(√n)Linked list_cell_0_5_6

A dynamic array is a data structure that allocates all elements contiguously in memory, and keeps a count of the current number of elements. Linked list_sentence_76

If the space reserved for the dynamic array is exceeded, it is reallocated and (possibly) copied, which is an expensive operation. Linked list_sentence_77

Linked lists have several advantages over dynamic arrays. Linked list_sentence_78

Insertion or deletion of an element at a specific point of a list, assuming that we have indexed a pointer to the node (before the one to be removed, or before the insertion point) already, is a constant-time operation (otherwise without this reference it is O(n)), whereas insertion in a dynamic array at random locations will require moving half of the elements on average, and all the elements in the worst case. Linked list_sentence_79

While one can "delete" an element from an array in constant time by somehow marking its slot as "vacant", this causes fragmentation that impedes the performance of iteration. Linked list_sentence_80

Moreover, arbitrarily many elements may be inserted into a linked list, limited only by the total memory available; while a dynamic array will eventually fill up its underlying array data structure and will have to reallocate—an expensive operation, one that may not even be possible if memory is fragmented, although the cost of reallocation can be averaged over insertions, and the cost of an insertion due to reallocation would still be amortized O(1). Linked list_sentence_81

This helps with appending elements at the array's end, but inserting into (or removing from) middle positions still carries prohibitive costs due to data moving to maintain contiguity. Linked list_sentence_82

An array from which many elements are removed may also have to be resized in order to avoid wasting too much space. Linked list_sentence_83

On the other hand, dynamic arrays (as well as fixed-size array data structures) allow constant-time random access, while linked lists allow only sequential access to elements. Linked list_sentence_84

Singly linked lists, in fact, can be easily traversed in only one direction. Linked list_sentence_85

This makes linked lists unsuitable for applications where it's useful to look up an element by its index quickly, such as heapsort. Linked list_sentence_86

Sequential access on arrays and dynamic arrays is also faster than on linked lists on many machines, because they have optimal locality of reference and thus make good use of data caching. Linked list_sentence_87

Another disadvantage of linked lists is the extra storage needed for references, which often makes them impractical for lists of small data items such as characters or boolean values, because the storage overhead for the links may exceed by a factor of two or more the size of the data. Linked list_sentence_88

In contrast, a dynamic array requires only the space for the data itself (and a very small amount of control data). Linked list_sentence_89

It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element, a problem generally solved using memory pools. Linked list_sentence_90

Some hybrid solutions try to combine the advantages of the two representations. Linked list_sentence_91

Unrolled linked lists store several elements in each list node, increasing cache performance while decreasing memory overhead for references. Linked list_sentence_92

CDR coding does both these as well, by replacing references with the actual data referenced, which extends off the end of the referencing record. Linked list_sentence_93

A good example that highlights the pros and cons of using dynamic arrays vs. linked lists is by implementing a program that resolves the Josephus problem. Linked list_sentence_94

The Josephus problem is an election method that works by having a group of people stand in a circle. Linked list_sentence_95

Starting at a predetermined person, one may count around the circle n times. Linked list_sentence_96

Once the nth person is reached, one should remove them from the circle and have the members close the circle. Linked list_sentence_97

The process is repeated until only one person is left. Linked list_sentence_98

That person wins the election. Linked list_sentence_99

This shows the strengths and weaknesses of a linked list vs. a dynamic array, because if the people are viewed as connected nodes in a circular linked list, then it shows how easily the linked list is able to delete nodes (as it only has to rearrange the links to the different nodes). Linked list_sentence_100

However, the linked list will be poor at finding the next person to remove and will need to search through the list until it finds that person. Linked list_sentence_101

A dynamic array, on the other hand, will be poor at deleting nodes (or elements) as it cannot remove one node without individually shifting all the elements up the list by one. Linked list_sentence_102

However, it is exceptionally easy to find the nth person in the circle by directly referencing them by their position in the array. Linked list_sentence_103

The list ranking problem concerns the efficient conversion of a linked list representation into an array. Linked list_sentence_104

Although trivial for a conventional computer, solving this problem by a parallel algorithm is complicated and has been the subject of much research. Linked list_sentence_105

A balanced tree has similar memory access patterns and space overhead to a linked list while permitting much more efficient indexing, taking O(log n) time instead of O(n) for a random access. Linked list_sentence_106

However, insertion and deletion operations are more expensive due to the overhead of tree manipulations to maintain balance. Linked list_sentence_107

Schemes exist for trees to automatically maintain themselves in a balanced state: AVL trees or red-black trees. Linked list_sentence_108

Singly linked linear lists vs. other lists Linked list_section_14

While doubly linked and circular lists have advantages over singly linked linear lists, linear lists offer some advantages that make them preferable in some situations. Linked list_sentence_109

A singly linked linear list is a recursive data structure, because it contains a pointer to a smaller object of the same type. Linked list_sentence_110

For that reason, many operations on singly linked linear lists (such as merging two lists, or enumerating the elements in reverse order) often have very simple recursive algorithms, much simpler than any solution using iterative commands. Linked list_sentence_111

While those recursive solutions can be adapted for doubly linked and circularly linked lists, the procedures generally need extra arguments and more complicated base cases. Linked list_sentence_112

Linear singly linked lists also allow tail-sharing, the use of a common final portion of sub-list as the terminal portion of two different lists. Linked list_sentence_113

In particular, if a new node is added at the beginning of a list, the former list remains available as the tail of the new one—a simple example of a persistent data structure. Linked list_sentence_114

Again, this is not true with the other variants: a node may never belong to two different circular or doubly linked lists. Linked list_sentence_115

In particular, end-sentinel nodes can be shared among singly linked non-circular lists. Linked list_sentence_116

The same end-sentinel node may be used for every such list. Linked list_sentence_117

In Lisp, for example, every proper list ends with a link to a special node, denoted by nil or (), whose CAR and CDR links point to itself. Linked list_sentence_118

Thus a Lisp procedure can safely take the CAR or CDR of any list. Linked list_sentence_119

The advantages of the fancy variants are often limited to the complexity of the algorithms, not in their efficiency. Linked list_sentence_120

A circular list, in particular, can usually be emulated by a linear list together with two variables that point to the first and last nodes, at no extra cost. Linked list_sentence_121

Doubly linked vs. singly linked Linked list_section_15

Double-linked lists require more space per node (unless one uses XOR-linking), and their elementary operations are more expensive; but they are often easier to manipulate because they allow fast and easy sequential access to the list in both directions. Linked list_sentence_122

In a doubly linked list, one can insert or delete a node in a constant number of operations given only that node's address. Linked list_sentence_123

To do the same in a singly linked list, one must have the address of the pointer to that node, which is either the handle for the whole list (in case of the first node) or the link field in the previous node. Linked list_sentence_124

Some algorithms require access in both directions. Linked list_sentence_125

On the other hand, doubly linked lists do not allow tail-sharing and cannot be used as persistent data structures. Linked list_sentence_126

Circularly linked vs. linearly linked Linked list_section_16

A circularly linked list may be a natural option to represent arrays that are naturally circular, e.g. the corners of a polygon, a pool of buffers that are used and released in FIFO ("first in, first out") order, or a set of processes that should be time-shared in round-robin order. Linked list_sentence_127

In these applications, a pointer to any node serves as a handle to the whole list. Linked list_sentence_128

With a circular list, a pointer to the last node gives easy access also to the first node, by following one link. Linked list_sentence_129

Thus, in applications that require access to both ends of the list (e.g., in the implementation of a queue), a circular structure allows one to handle the structure by a single pointer, instead of two. Linked list_sentence_130

A circular list can be split into two circular lists, in constant time, by giving the addresses of the last node of each piece. Linked list_sentence_131

The operation consists in swapping the contents of the link fields of those two nodes. Linked list_sentence_132

Applying the same operation to any two nodes in two distinct lists joins the two list into one. Linked list_sentence_133

This property greatly simplifies some algorithms and data structures, such as the quad-edge and face-edge. Linked list_sentence_134

The simplest representation for an empty circular list (when such a thing makes sense) is a null pointer, indicating that the list has no nodes. Linked list_sentence_135

Without this choice, many algorithms have to test for this special case, and handle it separately. Linked list_sentence_136

By contrast, the use of null to denote an empty linear list is more natural and often creates fewer special cases. Linked list_sentence_137

Using sentinel nodes Linked list_section_17

Sentinel node may simplify certain list operations, by ensuring that the next or previous nodes exist for every element, and that even empty lists have at least one node. Linked list_sentence_138

One may also use a sentinel node at the end of the list, with an appropriate data field, to eliminate some end-of-list tests. Linked list_sentence_139

For example, when scanning the list looking for a node with a given value x, setting the sentinel's data field to x makes it unnecessary to test for end-of-list inside the loop. Linked list_sentence_140

Another example is the merging two sorted lists: if their sentinels have data fields set to +∞, the choice of the next output node does not need special handling for empty lists. Linked list_sentence_141

However, sentinel nodes use up extra space (especially in applications that use many short lists), and they may complicate other operations (such as the creation of a new empty list). Linked list_sentence_142

However, if the circular list is used merely to simulate a linear list, one may avoid some of this complexity by adding a single sentinel node to every list, between the last and the first data nodes. Linked list_sentence_143

With this convention, an empty list consists of the sentinel node alone, pointing to itself via the next-node link. Linked list_sentence_144

The list handle should then be a pointer to the last data node, before the sentinel, if the list is not empty; or to the sentinel itself, if the list is empty. Linked list_sentence_145

The same trick can be used to simplify the handling of a doubly linked linear list, by turning it into a circular doubly linked list with a single sentinel node. Linked list_sentence_146

However, in this case, the handle should be a single pointer to the dummy node itself. Linked list_sentence_147

Linked list operations Linked list_section_18

When manipulating linked lists in-place, care must be taken to not use values that you have invalidated in previous assignments. Linked list_sentence_148

This makes algorithms for inserting or deleting linked list nodes somewhat subtle. Linked list_sentence_149

This section gives pseudocode for adding or removing nodes from singly, doubly, and circularly linked lists in-place. Linked list_sentence_150

Throughout we will use null to refer to an end-of-list marker or sentinel, which may be implemented in a number of ways. Linked list_sentence_151

Linearly linked lists Linked list_section_19

Singly linked lists Linked list_section_20

Our node data structure will have two fields. Linked list_sentence_152

We also keep a variable firstNode which always points to the first node in the list, or is null for an empty list. Linked list_sentence_153

Traversal of a singly linked list is simple, beginning at the first node and following each next link until we come to the end: Linked list_sentence_154

The following code inserts a node after an existing node in a singly linked list. Linked list_sentence_155

The diagram shows how it works. Linked list_sentence_156

Inserting a node before an existing one cannot be done directly; instead, one must keep track of the previous node and insert a node after it. Linked list_sentence_157

Inserting at the beginning of the list requires a separate function. Linked list_sentence_158

This requires updating firstNode. Linked list_sentence_159

Similarly, we have functions for removing the node after a given node, and for removing a node from the beginning of the list. Linked list_sentence_160

The diagram demonstrates the former. Linked list_sentence_161

To find and remove a particular node, one must again keep track of the previous element. Linked list_sentence_162

Notice that removeBeginning() sets list.firstNode to null when removing the last node in the list. Linked list_sentence_163

Since we can't iterate backwards, efficient insertBefore or removeBefore operations are not possible. Linked list_sentence_164

Inserting to a list before a specific node requires traversing the list, which would have a worst case running time of O(n). Linked list_sentence_165

Many of the special cases of linked list operations can be eliminated by including a dummy element at the front of the list. Linked list_sentence_166

This ensures that there are no special cases for the beginning of the list and renders both insertBeginning() and removeBeginning() unnecessary. Linked list_sentence_167

In this case, the first useful data in the list will be found at list.firstNode.next. Linked list_sentence_168

Circularly linked list Linked list_section_21

In a circularly linked list, all nodes are linked in a continuous circle, without using null. Linked list_sentence_169

For lists with a front and a back (such as a queue), one stores a reference to the last node in the list. Linked list_sentence_170

The next node after the last node is the first node. Linked list_sentence_171

Elements can be added to the back of the list and removed from the front in constant time. Linked list_sentence_172

Circularly linked lists can be either singly or doubly linked. Linked list_sentence_173

Both types of circularly linked lists benefit from the ability to traverse the full list beginning at any given node. Linked list_sentence_174

This often allows us to avoid storing firstNode and lastNode, although if the list may be empty we need a special representation for the empty list, such as a lastNode variable which points to some node in the list or is null if it's empty; we use such a lastNode here. Linked list_sentence_175

This representation significantly simplifies adding and removing nodes with a non-empty list, but empty lists are then a special case. Linked list_sentence_176

Algorithms Linked list_section_22

Assuming that someNode is some node in a non-empty circular singly linked list, this code iterates through that list starting with someNode: Linked list_sentence_177

Notice that the test "while node ≠ someNode" must be at the end of the loop. Linked list_sentence_178

If the test was moved to the beginning of the loop, the procedure would fail whenever the list had only one node. Linked list_sentence_179

This function inserts a node "newNode" into a circular linked list after a given node "node". Linked list_sentence_180

If "node" is null, it assumes that the list is empty. Linked list_sentence_181

Suppose that "L" is a variable pointing to the last node of a circular linked list (or null if the list is empty). Linked list_sentence_182

To append "newNode" to the end of the list, one may do Linked list_sentence_183

To insert "newNode" at the beginning of the list, one may do Linked list_sentence_184

This function inserts a value "newVal" before a given node "node" in O(1) time. Linked list_sentence_185

We create a new node between "node" and the next node, and then put the value of "node" into that new node, and put "newVal" in "node". Linked list_sentence_186

Thus, a singly linked circularly linked list with only a firstNode variable can both insert to the front and back in O(1) time. Linked list_sentence_187

This function removes a non-null node from a list of size greater than 1 in O(1) time. Linked list_sentence_188

It copies data from the next node into the node, and then sets the node's next pointer to skip over the next node. Linked list_sentence_189

Linked lists using arrays of nodes Linked list_section_23

Languages that do not support any type of reference can still create links by replacing pointers with array indices. Linked list_sentence_190

The approach is to keep an array of records, where each record has integer fields indicating the index of the next (and possibly previous) node in the array. Linked list_sentence_191

Not all nodes in the array need be used. Linked list_sentence_192

If records are also not supported, parallel arrays can often be used instead. Linked list_sentence_193

As an example, consider the following linked list record that uses arrays instead of pointers: Linked list_sentence_194

A linked list can be built by creating an array of these structures, and an integer variable to store the index of the first element. Linked list_sentence_195

Links between elements are formed by placing the array index of the next (or previous) cell into the Next or Prev field within a given element. Linked list_sentence_196

For example: Linked list_sentence_197

Linked list_table_general_1

IndexLinked list_header_cell_1_0_0 NextLinked list_header_cell_1_0_1 PrevLinked list_header_cell_1_0_2 NameLinked list_header_cell_1_0_3 BalanceLinked list_header_cell_1_0_4
0Linked list_cell_1_1_0 1Linked list_cell_1_1_1 4Linked list_cell_1_1_2 Jones, JohnLinked list_cell_1_1_3 123.45Linked list_cell_1_1_4
1Linked list_cell_1_2_0 −1Linked list_cell_1_2_1 0Linked list_cell_1_2_2 Smith, JosephLinked list_cell_1_2_3 234.56Linked list_cell_1_2_4
2 (listHead)Linked list_cell_1_3_0 4Linked list_cell_1_3_1 −1Linked list_cell_1_3_2 Adams, AdamLinked list_cell_1_3_3 0.00Linked list_cell_1_3_4
3Linked list_cell_1_4_0 Linked list_cell_1_4_1 Linked list_cell_1_4_2 Ignore, IgnatiusLinked list_cell_1_4_3 999.99Linked list_cell_1_4_4
4Linked list_cell_1_5_0 0Linked list_cell_1_5_1 2Linked list_cell_1_5_2 Another, AnitaLinked list_cell_1_5_3 876.54Linked list_cell_1_5_4
5Linked list_cell_1_6_0 Linked list_cell_1_6_1 Linked list_cell_1_6_2 Linked list_cell_1_6_3 Linked list_cell_1_6_4
6Linked list_cell_1_7_0 Linked list_cell_1_7_1 Linked list_cell_1_7_2 Linked list_cell_1_7_3 Linked list_cell_1_7_4
7Linked list_cell_1_8_0 Linked list_cell_1_8_1 Linked list_cell_1_8_2 Linked list_cell_1_8_3 Linked list_cell_1_8_4

In the above example, ListHead would be set to 2, the location of the first entry in the list. Linked list_sentence_198

Notice that entry 3 and 5 through 7 are not part of the list. Linked list_sentence_199

These cells are available for any additions to the list. Linked list_sentence_200

By creating a ListFree integer variable, a free list could be created to keep track of what cells are available. Linked list_sentence_201

If all entries are in use, the size of the array would have to be increased or some elements would have to be deleted before new entries could be stored in the list. Linked list_sentence_202

The following code would traverse the list and display names and account balance: Linked list_sentence_203

When faced with a choice, the advantages of this approach include: Linked list_sentence_204

Linked list_unordered_list_1

  • The linked list is relocatable, meaning it can be moved about in memory at will, and it can also be quickly and directly serialized for storage on disk or transfer over a network.Linked list_item_1_4
  • Especially for a small list, array indexes can occupy significantly less space than a full pointer on many architectures.Linked list_item_1_5
  • Locality of reference can be improved by keeping the nodes together in memory and by periodically rearranging them, although this can also be done in a general store.Linked list_item_1_6
  • Naïve dynamic memory allocators can produce an excessive amount of overhead storage for each node allocated; almost no allocation overhead is incurred per node in this approach.Linked list_item_1_7
  • Seizing an entry from a pre-allocated array is faster than using dynamic memory allocation for each node, since dynamic memory allocation typically requires a search for a free memory block of the desired size.Linked list_item_1_8

This approach has one main disadvantage, however: it creates and manages a private memory space for its nodes. Linked list_sentence_205

This leads to the following issues: Linked list_sentence_206

Linked list_unordered_list_2

  • It increases complexity of the implementation.Linked list_item_2_9
  • Growing a large array when it is full may be difficult or impossible, whereas finding space for a new linked list node in a large, general memory pool may be easier.Linked list_item_2_10
  • Adding elements to a dynamic array will occasionally (when it is full) unexpectedly take linear (O(n)) instead of constant time (although it's still an amortized constant).Linked list_item_2_11
  • Using a general memory pool leaves more memory for other data if the list is smaller than expected or if many nodes are freed.Linked list_item_2_12

For these reasons, this approach is mainly used for languages that do not support dynamic memory allocation. Linked list_sentence_207

These disadvantages are also mitigated if the maximum size of the list is known at the time the array is created. Linked list_sentence_208

Language support Linked list_section_24

Many programming languages such as Lisp and Scheme have singly linked lists built in. Linked list_sentence_209

In many functional languages, these lists are constructed from nodes, each called a cons or cons cell. Linked list_sentence_210

The cons has two fields: the car, a reference to the data for that node, and the cdr, a reference to the next node. Linked list_sentence_211

Although cons cells can be used to build other data structures, this is their primary purpose. Linked list_sentence_212

In languages that support abstract data types or templates, linked list ADTs or templates are available for building linked lists. Linked list_sentence_213

In other languages, linked lists are typically built using references together with records. Linked list_sentence_214

Internal and external storage Linked list_section_25

When constructing a linked list, one is faced with the choice of whether to store the data of the list directly in the linked list nodes, called internal storage, or merely to store a reference to the data, called external storage. Linked list_sentence_215

Internal storage has the advantage of making access to the data more efficient, requiring less storage overall, having better locality of reference, and simplifying memory management for the list (its data is allocated and deallocated at the same time as the list nodes). Linked list_sentence_216

External storage, on the other hand, has the advantage of being more generic, in that the same data structure and machine code can be used for a linked list no matter what the size of the data is. Linked list_sentence_217

It also makes it easy to place the same data in multiple linked lists. Linked list_sentence_218

Although with internal storage the same data can be placed in multiple lists by including multiple next references in the node data structure, it would then be necessary to create separate routines to add or delete cells based on each field. Linked list_sentence_219

It is possible to create additional linked lists of elements that use internal storage by using external storage, and having the cells of the additional linked lists store references to the nodes of the linked list containing the data. Linked list_sentence_220

In general, if a set of data structures needs to be included in linked lists, external storage is the best approach. Linked list_sentence_221

If a set of data structures need to be included in only one linked list, then internal storage is slightly better, unless a generic linked list package using external storage is available. Linked list_sentence_222

Likewise, if different sets of data that can be stored in the same data structure are to be included in a single linked list, then internal storage would be fine. Linked list_sentence_223

Another approach that can be used with some languages involves having different data structures, but all have the initial fields, including the next (and prev if double linked list) references in the same location. Linked list_sentence_224

After defining separate structures for each type of data, a generic structure can be defined that contains the minimum amount of data shared by all the other structures and contained at the top (beginning) of the structures. Linked list_sentence_225

Then generic routines can be created that use the minimal structure to perform linked list type operations, but separate routines can then handle the specific data. Linked list_sentence_226

This approach is often used in message parsing routines, where several types of messages are received, but all start with the same set of fields, usually including a field for message type. Linked list_sentence_227

The generic routines are used to add new messages to a queue when they are received, and remove them from the queue in order to process the message. Linked list_sentence_228

The message type field is then used to call the correct routine to process the specific type of message. Linked list_sentence_229

Example of internal and external storage Linked list_section_26

Suppose you wanted to create a linked list of families and their members. Linked list_sentence_230

Using internal storage, the structure might look like the following: Linked list_sentence_231

To print a complete list of families and their members using internal storage, we could write: Linked list_sentence_232

Using external storage, we would create the following structures: Linked list_sentence_233

To print a complete list of families and their members using external storage, we could write: Linked list_sentence_234

Notice that when using external storage, an extra step is needed to extract the record from the node and cast it into the proper data type. Linked list_sentence_235

This is because both the list of families and the list of members within the family are stored in two linked lists using the same data structure (node), and this language does not have parametric types. Linked list_sentence_236

As long as the number of families that a member can belong to is known at compile time, internal storage works fine. Linked list_sentence_237

If, however, a member needed to be included in an arbitrary number of families, with the specific number known only at run time, external storage would be necessary. Linked list_sentence_238

Speeding up search Linked list_section_27

Finding a specific element in a linked list, even if it is sorted, normally requires O(n) time (linear search). Linked list_sentence_239

This is one of the primary disadvantages of linked lists over other data structures. Linked list_sentence_240

In addition to the variants discussed above, below are two simple ways to improve search time. Linked list_sentence_241

In an unordered list, one simple heuristic for decreasing average search time is the move-to-front heuristic, which simply moves an element to the beginning of the list once it is found. Linked list_sentence_242

This scheme, handy for creating simple caches, ensures that the most recently used items are also the quickest to find again. Linked list_sentence_243

Another common approach is to "index" a linked list using a more efficient external data structure. Linked list_sentence_244

For example, one can build a red-black tree or hash table whose elements are references to the linked list nodes. Linked list_sentence_245

Multiple such indexes can be built on a single list. Linked list_sentence_246

The disadvantage is that these indexes may need to be updated each time a node is added or removed (or at least, before that index is used again). Linked list_sentence_247

Random access lists Linked list_section_28

A random access list is a list with support for fast random access to read or modify any element in the list. Linked list_sentence_248

One possible implementation is a skew binary random access list using the skew binary number system, which involves a list of trees with special properties; this allows worst-case constant time head/cons operations, and worst-case logarithmic time random access to an element by index. Linked list_sentence_249

Random access lists can be implemented as persistent data structures. Linked list_sentence_250

Random access lists can be viewed as immutable linked lists in that they likewise support the same O(1) head and tail operations. Linked list_sentence_251

A simple extension to random access lists is the min-list, which provides an additional operation that yields the minimum element in the entire list in constant time (without mutation complexities). Linked list_sentence_252

Related data structures Linked list_section_29

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

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. Linked list_sentence_254

This process continues down to the bottom layer, which is the actual list. Linked list_sentence_255

A binary tree can be seen as a type of linked list where the elements are themselves linked lists of the same nature. Linked list_sentence_256

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. Linked list_sentence_257

An unrolled linked list is a linked list in which each node contains an array of data values. Linked list_sentence_258

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. Linked list_sentence_259

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

A heap shares some of the ordering properties of a linked list, but is almost always implemented using an array. Linked list_sentence_261

Instead of references from node to node, the next and previous data indexes are calculated using the current data's index. Linked list_sentence_262

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. Linked list_sentence_263


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Linked list.