2277:
routines can be created that use the minimal structure to perform linked list type operations, but separate routines can then handle the specific data. 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. 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. The message type field is then used to call the correct routine to process the specific type of message.
32:
1117:
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). 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. 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. However, it is exceptionally easy to find the
1495:
1437:
721:
672:
369:
89:
1086:, because the storage overhead for the links may exceed by a factor of two or more the size of the data. In contrast, a dynamic array requires only the space for the data itself (and a very small amount of control data). 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
1221:), 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. In a doubly linked list, one can insert or delete a node in a constant number of operations given only that node's address. To do the same in a singly linked list, one must have the
133:) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that data access time is
313:(originally of West Lafayette Indiana, and later of Chapel Hill, North Carolina) used singly linked lists as file structures. A directory entry pointed to the first sector of a file, and succeeding portions of the file were located by traversing pointers. Systems using this technique included Flex (for the
1324:
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. With this convention, an empty list consists of the sentinel node alone, pointing to itself via the
1268:
A circular list can be split into two circular lists, in constant time, by giving the addresses of the last node of each piece. The operation consists in swapping the contents of the link fields of those two nodes. Applying the same operation to any two nodes in two distinct lists joins the two list
1139:
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. However, insertion and deletion operations are more expensive due to the overhead of tree manipulations to maintain balance.
244:, and a computer chess program. 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
1308:
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. 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. For example, when
1037:
Linked lists have several advantages over dynamic arrays. 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
1292:
For some applications, it can be useful to use singly linked lists that can vary between being circular and being linear, or even circular with a linear initial segment. Algorithms for searching or otherwise operating on these have to take precautions to avoid accidentally entering an endless loop.
1264:
With a circular list, a pointer to the last node gives easy access also to the first node, by following one link. 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,
1116:
th person is reached, one should remove them from the circle and have the members close the circle. The process is repeated until only one person is left. That person wins the election. This shows the strengths and weaknesses of a linked list vs. a dynamic array, because if the people are viewed as
1050:
O(1). 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. An array from which many elements are removed may also have to be resized in order to avoid wasting too much
742:
In some implementations an extra 'sentinel' or 'dummy' node may be added before the first data record or after the last one. 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
2260:
references in the node data structure, it would then be necessary to create separate routines to add or delete cells based on each field. 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
2255:
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. It also makes it easy to place the same data in multiple linked lists. Although with internal storage
699:
In a 'multiply linked list', each node contains two or more link fields, each field being used to connect the same set of data arranged in a different order (e.g., by name, by department, by date of birth, etc.). While a doubly linked list can be seen as a special case of multiply linked list, the
305:
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. A later review article, "A Comparison of list-processing computer languages" by Bobrow and
1045:
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
769:
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. Algorithms that manipulate linked lists usually get such handles to the input lists and return the handles to the resulting lists. In fact, in the
248:
International
Conference on Information Processing) in 1959. 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. WJCC, February 1957. Newell and Simon were
2276:
if double linked list) references in the same location. 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. Then generic
2264:
In general, if a set of data structures needs to be included in linked lists, external storage is the best approach. 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
1560:
Appending one linked list to another can be inefficient unless a reference to the tail is kept as part of the List structure, because we must traverse the entire first list in order to find the tail, and then append the second list to this. Thus, if two linearly linked lists are each of length
1038:
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. While one can "delete" an element from an array in constant time by somehow marking its slot as "vacant", this causes
2489:
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. 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
2497:
As long as the number of families that a member can belong to is known at compile time, internal storage works fine. 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.
2602:
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.
199:
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.
712:
reference, a special value is used to indicate the lack of further nodes. 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'. It is a
1208:
The advantages of the fancy variants are often limited to the complexity of the algorithms, not in their efficiency. 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.
786:
As with most choices in computer programming and design, no method is well suited to all circumstances. A linked list data structure might work well in one case, but cause problems in another. This is a list of some of the common tradeoffs involving linked list structures.
1791:
This function inserts a value "newVal" before a given node "node" in O(1) time. 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". Thus, a singly linked circularly linked list with only a
324:
The TSS/360 operating system, developed by IBM for the System 360/370 machines, used a double linked list for their file system catalog. The directory structure was similar to Unix, where a directory could contain files and other directories and extend to any depth.
191:
is a much more expensive operation. 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.
1432:
The following code inserts a node after an existing node in a singly linked list. The diagram shows how it works. 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.
2536:
whose elements are references to the linked list nodes. Multiple such indexes can be built on a single list. 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).
1033:
is a data structure that allocates all elements contiguously in memory, and keeps a count of the current number of elements. If the space reserved for the dynamic array is exceeded, it is reallocated and (possibly) copied, which is an expensive operation.
1328:
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. However, in this case, the handle should be a single pointer to the dummy node itself.
1182:, the use of a common final portion of sub-list as the terminal portion of two different lists. 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
1284:
list (when such a thing makes sense) is a null pointer, indicating that the list has no nodes. Without this choice, many algorithms have to test for this special case, and handle it separately. By contrast, the use of null to denote an empty
1317:
makes it unnecessary to test for end-of-list inside the loop. 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.
667:
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. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').
364:
Singly linked lists contain nodes which have a 'value' field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.
1337:
When manipulating linked lists in-place, care must be taken to not use values that you have invalidated in previous assignments. This makes algorithms for inserting or deleting linked list nodes somewhat subtle. This section gives
683:
allows a doubly linked list to be implemented using a single link field in each node. However, this technique requires the ability to do bit operations on addresses, and therefore may not be available in some high-level languages.
2628:
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.
2557:, 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. Random-access lists can be implemented as
2091:
could be created to keep track of what cells are available. 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.
760:
The link fields need not be physically part of the nodes. 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.
2170:
For these reasons, this approach is mainly used for languages that do not support dynamic memory allocation. These disadvantages are also mitigated if the maximum size of the list is known at the time the array is created.
340:
The field of each node that contains the address of the next node is usually called the 'next link' or 'next pointer'. The remaining fields are known as the 'data', 'information', 'value', 'cargo', or 'payload' fields.
2594:
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.
770:
context of such algorithms, the word "list" often means "list handle". 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.
751:
An empty list is a list that contains no data records. This is usually the same as saying that it has zero nodes. If sentinel nodes are being used, the list is usually said to be empty when it has only sentinel nodes.
1623:
Many of the special cases of linked list operations can be eliminated by including a dummy element at the front of the list. This ensures that there are no special cases for the beginning of the list and renders both
1066:
to elements. Singly linked lists, in fact, can be easily traversed in only one direction. This makes linked lists unsuitable for applications where it's useful to look up an element by its index quickly, such as
2521:, which simply moves an element to the beginning of the list once it is found. This scheme, handy for creating simple caches, ensures that the most recently used items are also the quickest to find again.
2140:
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
92:
A linked list is a sequence of nodes that contain two fields: data (an integer value here as an example) and a link to the next node. The last node is linked to a terminator used to signify the end of the
2083:
would be set to 2, the location of the first entry in the list. Notice that entry 3 and 5 through 7 are not part of the list. These cells are available for any additions to the list. By creating a
1491:
a given node, and for removing a node from the beginning of the list. The diagram demonstrates the former. To find and remove a particular node, one must again keep track of the previous element.
778:
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.
1879:, where each record has integer fields indicating the index of the next (and possibly previous) node in the array. Not all nodes in the array need be used. If records are also not supported,
137:
in respect to the number of nodes in the list. Because nodes are serially linked, accessing any node requires that the prior node be accessed beforehand (which introduces difficulties in
2514:). This is one of the primary disadvantages of linked lists over other data structures. In addition to the variants discussed above, below are two simple ways to improve search time.
1321:
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).
2550:
1632:
unnecessary, i.e., every element or node is next to another node (even the first node is next to the dummy node). In this case, the first useful data in the list will be found at
2896:
1325:
next-node link. 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.
1175:. 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.
2265:
available. 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.
1108:. The Josephus problem is an election method that works by having a group of people stand in a circle. Starting at a predetermined person, one may count around the circle
301:
By the early 1960s, the utility of both linked lists and languages which use these structures as their primary data representation was well established. Bert Green of the
183:
is that the list elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items do not need to be stored
1156:
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.
1274:
2152:
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.
2682:
2614:
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.
1727:
node ≠ someNode" must be at the end of the loop. If the test was moved to the beginning of the loop, the procedure would fail whenever the list had only one node.
1612:
1833:
This function removes a non-null node from a list of size greater than 1 in O(1) time. It copies data from the next node into the node, and then sets the node's
1128:
problem concerns the efficient conversion of a linked list representation into an array. Although trivial for a conventional computer, solving this problem by a
2782:
2762:
2742:
2722:
2702:
1579:
1933:
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. For example:
700:
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.
1662:
Both types of circularly linked lists benefit from the ability to traverse the full list beginning at any given node. This often allows us to avoid storing
687:
Many modern operating systems use doubly linked lists to maintain references to active processes, threads, and other dynamic objects. A common strategy for
2866:
2546:
298:, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". One of LISP's major data structures is the linked list.
1557:
operations are not possible. Inserting to a list before a specific node requires traversing the list, which would have a worst case running time of O(n).
1078:
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
420:// declare Node pointer and initialize to point to the new Node (i.e., it will have the new Node's memory address) being added to the end of the list.
344:
The 'head' of a list is its first node. 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. In
2636:
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.
675:
A doubly linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node
1730:
This function inserts a node "newNode" into a circular linked list after a given node "node". If "node" is null, it assumes that the list is empty.
2145:
This approach has one main disadvantage, however: it creates and manages a private memory space for its nodes. This leads to the following issues:
1855:
and size of list > 1 removedData := node.data node.data := node.next.data node.next = node.next.next
1297:
is to have a second pointer walking the list at half or double the speed, and if both pointers meet at the same node, you know you found a cycle.
2240:
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
2224:
or templates, linked list ADTs or templates are available for building linked lists. In other languages, linked lists are typically built using
2137:
can produce an excessive amount of overhead storage for each node allocated; almost no allocation overhead is incurred per node in this approach.
253:
in 1975 for having "made basic contributions to artificial intelligence, the psychology of human cognition, and list processing". The problem of
2285:
Suppose you wanted to create a linked list of families and their members. Using internal storage, the structure might look like the following:
2268:
Another approach that can be used with some languages involves having different data structures, but all have the initial fields, including the
2130:
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.
1229:
node. Some algorithms require access in both directions. On the other hand, doubly linked lists do not allow tail-sharing and cannot be used as
717:
where the last node pointer points to the first node (i.e., the "next link" pointer of the last node has the memory address of the first node).
3109:
1763:
Suppose that "L" is a variable pointing to the last node of a circular linked list (or null if the list is empty). To append "newNode" to the
1046:
fragmented, although the cost of reallocation can be averaged over insertions, and the cost of an insertion due to reallocation would still be
2918:
2571:, which provides an additional operation that yields the minimum element in the entire list in constant time (without mutation complexities).
1682:
here. This representation significantly simplifies adding and removing nodes with a non-empty list, but empty lists are then a special case.
3862:
3464:
1171:
two lists, or enumerating the elements in reverse order) often have very simple recursive algorithms, much simpler than any solution using
1104:
A good example that highlights the pros and cons of using dynamic arrays vs. linked lists is by implementing a program that resolves the
2568:
1656:
node after the last node is the first node. Elements can be added to the back of the list and removed from the front in constant time.
1101:
does both these as well, by replacing references with the actual data referenced, which extends off the end of the referencing record.
1920:
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.
531:// If the linked list is empty (i.e., the head node pointer is a null pointer), then have the head node pointer point to the new Node.
3538:
273:. A report on this language entitled "A programming language for mechanical translation" appeared in Mechanical Translation in 1958.
1189:
In particular, end-sentinel nodes can be shared among singly linked non-circular lists. The same end-sentinel node may be used for
2564:
Random-access lists can be viewed as immutable linked lists in that they likewise support the same O(1) head and tail operations.
1071:. Sequential access on arrays and dynamic arrays is also faster than on linked lists on many machines, because they have optimal
2248:. Internal storage has the advantage of making access to the data more efficient, requiring less storage overall, having better
2217:, a reference to the next node. Although cons cells can be used to build other data structures, this is their primary purpose.
2840:
2166:
Using a general memory pool leaves more memory for other data if the list is smaller than expected or if many nodes are freed.
105:
is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element
3832:
3349:
3075:
2937:
2821:
2252:, and simplifying memory management for the list (its data is allocated and deallocated at the same time as the list nodes).
1186:. Again, this is not true with the other variants: a node may never belong to two different circular or doubly linked lists.
266:
19:"Dynamic list" redirects here. For the Knowledge guideline which describes list articles which may never be completed, see
3435:
2549:
is a list with support for fast random access to read or modify any element in the list. One possible implementation is a
2124:
Especially for a small list, array indexes can occupy significantly less space than a full pointer on many architectures.
2117:
The linked list is relocatable, meaning it can be moved about in memory at will, and it can also be quickly and directly
1241:
A circularly linked list may be a natural option to represent arrays that are naturally circular, e.g. the corners of a
1097:
store several elements in each list node, increasing cache performance while decreasing memory overhead for references.
152:
Linked lists are among the simplest and most common data structures. They can be used to implement several other common
3256:
291:
188:
3771:
3481:
3388:
3369:
3308:
3229:
3193:
3157:
3138:
2997:
1826:
Node(data:=node.data, next:=node.next) node.data := newVal node.next := newNode update
1136:
928:
376:
The following C language code demonstrates how to add a new node with the "value" to the end of a singly linked list:
269:(MIT) to use linked lists as data structures in his COMIT programming language for computer research in the field of
75:
53:
46:
1250:
317:
CPU), mini-Flex (same CPU), and Flex9 (for the
Motorola 6809 CPU). A variant developed by TSC for and marketed by
176:, though it is not uncommon to implement those data structures directly without using a linked list as the basis.
3561:
2967:
Proceedings of the
Seventh International Conference on Functional Programming Languages and Computer Architecture
2192:
1225:
to that node, which is either the handle for the whole list (in case of the first node) or the link field in the
233:
2873:
3566:
1342:
for adding or removing nodes from singly, doubly, and circularly linked lists in-place. Throughout we will use
106:
1652:
For lists with a front and a back (such as a queue), one stores a reference to the last node in the list. The
3531:
3076:"Ch20 –Data Structures; ID06 - PROGRAMMING with JAVA (slide part of the book 'Big Java', by CayS. Horstmann)"
2188:
310:
3640:
1694:
is some node in a non-empty circular singly linked list, this code iterates through that list starting with
2225:
1868:
1390:
126:
2587:
are often implemented using linked lists, and simply restrict the type of operations which are supported.
353:
3645:
3628:
345:
20:
372:
A singly linked list whose nodes contain two fields: an integer value (data) and a link to the next node
3844:
3611:
3606:
3220:
3184:
1582:
728:
In the case of a circular doubly linked list, the first node also points to the last node of the list.
225:
165:
161:
3601:
3265:
2558:
2554:
2486:
print information about member memNode := memNode.next famNode := famNode.next
2373:
print information about member aMember := aMember.next aFamily := aFamily.next
2229:
2184:
2134:
1876:
1230:
1194:
1183:
318:
295:
157:
3056:
2621:
may use linked lists to store the chains of items that hash to the same position in the hash table.
3635:
3594:
3524:
1670:, although if the list may be empty we need a special representation for the empty list, such as a
1270:
1039:
40:
1167:
object of the same type. For that reason, many operations on singly linked linear lists (such as
3875:
3852:
2155:
Adding elements to a dynamic array will occasionally (when it is full) unexpectedly take linear (
334:
237:
114:
3130:
3124:
3857:
3657:
3422:
3398:
2584:
2580:
2447:
To print a complete list of families and their members using external storage, we could write:
2342:
To print a complete list of families and their members using internal storage, we could write:
1886:
As an example, consider the following linked list record that uses arrays instead of pointers:
1258:
302:
241:
138:
57:
3401:(1964). "An Experiment with a Self-compiling Compiler for a Simple List-Processing Language".
2941:
3896:
3783:
3738:
3700:
2625:
2610:
is a linked list in which each node contains an array of data values. This leads to improved
2528:" a linked list using a more efficient external data structure. For example, one can build a
2249:
2127:
1513:
obsoleteNode := node.next node.next := node.next.next destroy obsoleteNode
1079:
1072:
146:
1871:
can still create links by replacing pointers with array indices. The approach is to keep an
1462:
Inserting at the beginning of the list requires a separate function. This requires updating
1414:
Traversal of a singly linked list is simple, beginning at the first node and following each
1269:
into one. This property greatly simplifies some algorithms and data structures, such as the
3723:
3207:
3171:
2655:
2633:
2607:
2180:
1094:
1055:
869:
180:
142:
3361:
3354:
1588:
381:// Each node in a linked list is a structure. The head node is the first node in the list.
284:
memorandum in
January 1953 that suggested the use of linked lists in chained hash tables.
8:
3493:(note that this technique was widely used for many decades before the patent was granted)
3331:
254:
1648:
In a circularly linked list, all nodes are linked in a continuous circle, without using
709:
3766:
3751:
3616:
3576:
3284:
3044:
2767:
2747:
2727:
2707:
2687:
2529:
2506:
Finding a specific element in a linked list, even if it is sorted, normally requires O(
2221:
2160:
1564:
1145:
1129:
1047:
1005:
907:
662:
153:
3261:"Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"
3685:
3584:
3414:
3384:
3365:
3304:
3225:
3189:
3153:
3134:
2993:
2920:
Number crunching: Why you should never, ever, EVER use linked-list in your code again
2844:
2817:
2517:
In an unordered list, one simple heuristic for decreasing average search time is the
1261:. In these applications, a pointer to any node serves as a handle to the whole list.
1121:
th person in the circle by directly referencing them by their position in the array.
1063:
989:
169:
3491:
Patent for the idea of having nodes which are in several linked lists simultaneously
3260:
3708:
3410:
3288:
3274:
3244:
3211:
3203:
3175:
3167:
2970:
2525:
1527:
obsoleteNode := list.firstNode list.firstNode := list.firstNode.next
1105:
609:// Traverse the list until p is the last Node. The last Node always points to NULL.
258:
221:
217:
122:
98:
3082:
2095:
The following code would traverse the list and display names and account balance:
1140:
Schemes exist for trees to automatically maintain themselves in a balanced state:
294:
in 1958 while he was at MIT and in 1960 he published its design in a paper in the
3728:
3670:
1872:
1294:
1218:
1168:
1093:
Some hybrid solutions try to combine the advantages of the two representations.
680:
277:
134:
3023:
1197:, for example, every proper list ends with a link to a special node, denoted by
184:
3820:
3798:
3623:
3547:
3439:
3248:
3215:
3179:
2652:
The amount of control data required for a dynamic array is usually of the form
2156:
1880:
1494:
1347:
229:
110:
3490:
3890:
3793:
3690:
3675:
3511:
3506:
3501:
3496:
2511:
2118:
1436:
1305:
1083:
1059:
1029:
891:
737:
314:
196:
3460:
3101:
2261:
lists store references to the nodes of the linked list containing the data.
1756:
newNode.next := node.next node.next := newNode update
3318:
3296:
2805:
1254:
1179:
1125:
356:) of the list, while the payload of the head node may be called the 'car'.
262:
250:
209:
173:
3279:
2974:
3788:
3239:
Green, Bert F. Jr. (1961). "Computer
Languages for Symbol Manipulation".
2599:
2213:
2207:
1484:
newNode.next := list.firstNode list.firstNode := newNode
1246:
1087:
720:
349:
270:
195:
On the other hand, since simple linked lists by themselves do not allow
3776:
3680:
2618:
2533:
1363:
Our node data structure will have two fields. We also keep a variable
1339:
1098:
213:
2943:
Resizable Arrays in
Optimal Time and Space (Technical Report CS-99-09)
1614:. In the Lisp family of languages, list appending is provided by the
3718:
3665:
3485:
3475:
3469:
3100:
Black, Paul E. (2004-08-16). Pieterse, Vreda; Black, Paul E. (eds.).
2611:
2591:
2088:
1172:
1160:
671:
368:
88:
2256:
the same data can be placed in multiple lists by including multiple
1253:("first in, first out") order, or a set of processes that should be
3815:
3761:
3589:
2468:
print information about family memNode := aFamily.members
2359:
print information about family aMember := aFamily.members
2113:
When faced with a choice, the advantages of this approach include:
1141:
1068:
708:
In the last node of a linked list, the link field often contains a
688:
118:
3516:
3381:
A Practical
Introduction to Data Structures and Algorithm Analysis
2376:
Using external storage, we would create the following structures:
3810:
3756:
1752:// assume list is empty newNode.next := newNode
1242:
1217:
Double-linked lists require more space per node (unless one uses
1716:
do something with node.value node := node.next
1459:
newNode.next := node.next node.next := newNode
561:// Assign the head node pointer to the Node pointer 'p'.
3805:
3746:
2965:
Chris
Okasaki (1995). "Purely Functional Random-Access Lists".
1659:
Circularly linked lists can be either singly or doubly linked.
1616:
245:
3321:; Shaw, F. C. (1957). "Programming the Logic Theory Machine".
333:
Each record of a linked list is often called an 'element' or '
306:
2935:
1796:
variable can both insert to the front and back in O(1) time.
1151:
691:
to evade detection is to unlink themselves from these lists.
348:
and some derived languages, the next node may be called the '
1289:
list is more natural and often creates fewer special cases.
321:
in California, used doubly linked lists in the same manner.
236:(IPL). IPL was used by the authors to develop several early
3827:
2280:
2197:
714:
287:
179:
The principal benefit of a linked list over a conventional
3427:
Proceeds of the ACM National Conference, Philadelphia 1964
1132:
is complicated and has been the subject of much research.
141:). Faster access, such as random access, is not feasible.
2867:"VICE – Catch the hookers! (Plus new rootkit techniques)"
2841:"The NT Insider:Kernel-Mode Basics: Windows Linked Lists"
1367:
which always points to the first node in the list, or is
1054:
On the other hand, dynamic arrays (as well as fixed-size
281:
2949:, Department of Computer Science, University of Waterloo
2195:, these lists are constructed from nodes, each called a
1309:
scanning the list looking for a node with a given value
1236:
3123:
Antonakos, James L.; Mansfield, Kenneth C. Jr. (1999).
633:// Make the previously last Node point to the new Node.
2159:(n)) instead of constant time (although it's still an
187:
in memory or on disk, while restructuring an array at
2770:
2750:
2730:
2710:
2690:
2658:
2494:), and this language does not have parametric types.
2244:, or merely to store a reference to the data, called
1862:
1674:
variable which points to some node in the list or is
1591:
1567:
1440:
Diagram of inserting a node into a singly linked list
743:
data elements) always has a "first" and "last" node.
3323:
Proceedings of the Western Joint Computer Conference
2992:(Second ed.). Prentice-Hall. pp. 466–467.
1498:
Diagram of deleting a node from a singly linked list
1409:// points to first node of list; null for empty list
2960:
2958:
2956:
1487:Similarly, we have functions for removing the node
1163:data structure, because it contains a pointer to a
16:
Data structure with nodes pointing to the next node
3353:
3303:(3rd ed.). Addison-Wesley. pp. 254–298.
3150:Data Structures and the Java Collections Framework
2776:
2756:
2736:
2716:
2696:
2676:
1606:
1573:
1212:
790:
328:
240:programs, including the Logic Theory Machine, the
2567:A simple extension to random-access lists is the
2211:, a reference to the data for that node, and the
3888:
3241:IRE Transactions on Human Factors in Electronics
2953:
2235:
1814:// assume list is empty newNode :=
1350:, which may be implemented in a number of ways.
276:Another early appearance of linked lists was by
3482:Open Data Structures - Chapter 3 - Linked Lists
2121:for storage on disk or transfer over a network.
474:// Add data to the value field of the new Node.
3478:, Stanford University Computer Science Library
3472:, Stanford University Computer Science Library
3383:. New Jersey: Prentice Hall. pp. 77–102.
3110:National Institute of Standards and Technology
2898:Day 1 Keynote - Bjarne Stroustrup: C++11 Style
2149:It increases complexity of the implementation.
290:, standing for list processor, was created by
3532:
3512:Implementation of a doubly linked list in C++
3502:Implementation of a singly linked list in C++
3224:(2nd ed.). MIT Press. pp. 204–209.
2964:
2816:(2nd ed.). Addison-Wesley. p. 547.
208:Linked lists were developed in 1955–1956, by
121:. In its most basic form, each node contains
3465:Dictionary of Algorithms and Data Structures
3106:Dictionary of Algorithms and Data Structures
2361:// get head of list of this family's members
1549:Since we can't iterate backwards, efficient
3507:Implementation of a doubly linked list in C
3497:Implementation of a singly linked list in C
3152:. New York: McGraw Hill. pp. 239–303.
2191:have singly linked lists built in. In many
1042:that impedes the performance of iteration.
3539:
3525:
3017:
3015:
3013:
3011:
3009:
2574:
1867:Languages that do not support any type of
1770:insertAfter(L, newNode) L := newNode
1152:Singly linked linear lists vs. other lists
3425:(1964). "Lists and Why They are Useful".
3278:
2864:
2442:// head of list of members of this family
2337:// head of list of members of this family
1643:
1546:when removing the last node in the list.
1332:
1280:The simplest representation for an empty
773:
76:Learn how and when to remove this message
3188:. MIT Press. pp. 205–213, 501–505.
2987:
2281:Example of internal and external storage
1493:
1482:// insert node before current first node
1435:
1353:
1075:and thus make good use of data caching.
719:
670:
367:
87:
39:This article includes a list of general
3434:Shanmugasundaram, Kulesh (2005-04-04).
3021:
3006:
2784:are typically on the order of 10 bytes.
2106:print i, Records.name, Records.balance
1394:to the next node, null for last node }
1313:, setting the sentinel's data field to
1300:
703:
694:
309:Several operating systems developed by
3889:
3403:Annual Review in Automatic Programming
2540:
2464:aFamily := (family) famNode.data
1818:Node(data:=newVal, next:=newNode)
1358:
1178:Linear singly linked lists also allow
3520:
3126:Practical Data Structures Using C/C++
3025:Purely Functional Random-Access Lists
2988:Ford, William; Topp, William (2002).
2804:
2501:
2482:aMember := (member)memNode.data
1346:to refer to an end-of-list marker or
1237:Circularly linked vs. linearly linked
656:
359:
267:Massachusetts Institute of Technology
3436:"Linux Kernel Linked List Explained"
2835:
2833:
2798:
1908:// previous entry (if double-linked)
1837:pointer to skip over the next node.
1382:// The data being stored in the node
25:
3546:
2936:Brodnik, Andrej; Carlsson, Svante;
2398:// generic pointer for data at node
2174:
796:Comparison of list data structures
495:// initialize invalid links to nil.
13:
3067:
2990:Data Structures with C++ using STL
1863:Linked lists using arrays of nodes
45:it lacks sufficient corresponding
14:
3908:
3454:
2940:; Munro, JI; Demaine, ED (1999),
2830:
2724:is a per-dimension constant, and
2452:// start at head of families list
2347:// start at head of families list
1159:A singly linked linear list is a
731:
2462:// loop through list of families
2357:// loop through list of families
1062:, while linked lists allow only
976:
973:
882:
879:
876:
648:// Return the head node pointer.
30:
2810:The Art of Computer Programming
2524:Another common approach is to "
2480:// loop through list of members
2371:// loop through list of members
2205:. The cons has two fields: the
1901:// index of next entry in array
1418:link until we come to the end:
1213:Doubly linked vs. singly linked
808:Mutate (insert or delete) at …
791:Linked lists vs. dynamic arrays
764:
755:
453:/// 'malloc' in stdlib.
329:Basic concepts and nomenclature
234:Information Processing Language
3218:(2001). "10.2: Linked lists".
2981:
2929:
2912:
2890:
2865:Butler, Jamie; Hoglund, Greg.
2858:
2744:is the number of dimensions.
2646:
2551:skew binary random-access list
2409:// structure for family member
1601:
1595:
1249:that are used and released in
746:
113:consisting of a collection of
1:
3379:Shaffer, Clifford A. (1998).
3148:Collins, William J. (2005) .
2791:
2470:// get list of family members
2236:Internal and external storage
1685:
1678:if it's empty; we use such a
1427:(do something with node.data)
311:Technical Systems Consultants
3470:Introduction to Linked Lists
3415:10.1016/0066-4138(64)90013-8
1511:// remove node past this one
1457:// insert newNode after node
1421:node := list.firstNode
781:
7:
3863:Directed acyclic word graph
3629:Double-ended priority queue
3360:. Addison Wesley. pp.
3081:. p. 3. Archived from
3031:. ACM Press. pp. 86–95
2484:// extract member from node
2466:// extract family from node
1883:can often be used instead.
1773:To insert "newNode" at the
117:which together represent a
21:Knowledge:WikiProject Lists
10:
3913:
3249:10.1109/THFE2.1961.4503292
3221:Introduction to Algorithms
3185:Introduction to Algorithms
3129:. Prentice-Hall. pp.
2559:persistent data structures
2220:In languages that support
1712:node := someNode
1583:asymptotic time complexity
1529:// point past deleted node
1231:persistent data structures
735:
660:
226:Carnegie Mellon University
203:
149:compared to linked lists.
18:
3871:
3843:
3737:
3699:
3656:
3575:
3554:
3266:Communications of the ACM
2909:from minute 45 or foil 44
2704:is a per-array constant,
2555:skew binary number system
2450:famNode := Families
2387:// generic link structure
2345:aFamily := Families
2135:dynamic memory allocators
1184:persistent data structure
810:
807:
802:
800:
319:Smoke Signal Broadcasting
296:Communications of the ACM
3595:Retrieval Data Structure
3409:(1). Pergamon Press: 1.
2639:
2104:// loop through the list
1780:insertAfter(L, newNode)
1777:of the list, one may do
1767:of the list, one may do
844:Θ(1), known end element;
378:
249:recognized with the ACM
3876:List of data structures
3853:Binary decision diagram
3423:Wilkes, Maurice Vincent
3399:Wilkes, Maurice Vincent
3330:Parlante, Nick (2001).
3299:(1997). "2.2.3-2.2.5".
3022:Okasaki, Chris (1995).
2575:Related data structures
2519:move-to-front heuristic
2427:// structure for family
2110:i := Records.next
1429:node := node.next
850:), unknown end element
238:artificial intelligence
60:more precise citations.
3858:Directed acyclic graph
3301:Fundamental Algorithms
2925:kjellkod.wordpress.com
2778:
2758:
2738:
2718:
2698:
2678:
2079:In the above example,
1830:variable if necessary
1760:variable if necessary
1723:Notice that the test "
1704:iterate(someNode)
1644:Circularly linked list
1608:
1575:
1499:
1441:
1333:Linked list operations
1223:address of the pointer
1058:) allow constant-time
774:Combining alternatives
725:
724:A circular linked list
676:
373:
303:MIT Lincoln Laboratory
280:who wrote an internal
242:General Problem Solver
94:
3337:. Stanford University
3280:10.1145/367177.367199
3208:Leiserson, Charles E.
3172:Leiserson, Charles E.
2975:10.1145/224164.224187
2814:Sorting and Searching
2779:
2759:
2739:
2719:
2699:
2679:
2677:{\displaystyle K+B*n}
2296:// member of a family
2250:locality of reference
2181:programming languages
2128:Locality of reference
1609:
1581:, list appending has
1576:
1531:destroy obsoleteNode
1497:
1439:
1354:Linearly linked lists
1095:Unrolled linked lists
1073:locality of reference
1056:array data structures
723:
679:A technique known as
674:
371:
109:to the next. It is a
91:
3724:Unrolled linked list
3476:Linked List Problems
3332:"Linked list basics"
3074:Juan, Angel (2006).
2768:
2748:
2728:
2708:
2688:
2656:
2634:self-organizing list
2608:unrolled linked list
2318:// the family itself
2193:functional languages
2087:integer variable, a
1607:{\displaystyle O(n)}
1589:
1565:
1525:// remove first node
1301:Using sentinel nodes
704:Circular linked list
695:Multiply linked list
3772:Self-balancing tree
2541:Random-access lists
2222:abstract data types
2098:i := listHead
1371:for an empty list.
1359:Singly linked lists
797:
255:machine translation
154:abstract data types
129:(in other words, a
3752:Binary search tree
3617:Double-ended queue
3429:(P–64). ACM: F1–1.
2774:
2754:
2734:
2714:
2694:
2674:
2547:random-access list
2502:Speeding up search
1806:node, newVal)
1788:L := newNode
1604:
1571:
1500:
1442:
1425:node not null
1173:iterative commands
1130:parallel algorithm
795:
726:
677:
663:Doubly linked list
657:Doubly linked list
374:
360:Singly linked list
170:associative arrays
95:
3884:
3883:
3686:Hashed array tree
3585:Associative array
3350:Sedgewick, Robert
3212:Rivest, Ronald L.
3204:Cormen, Thomas H.
3176:Rivest, Ronald L.
3168:Cormen, Thomas H.
2938:Sedgewick, Robert
2907:channel9.msdn.com
2823:978-0-201-89685-5
2777:{\displaystyle B}
2757:{\displaystyle K}
2737:{\displaystyle n}
2717:{\displaystyle B}
2697:{\displaystyle K}
2077:
2076:
2014:Ignore, Ignatius
1630:removeBeginning()
1626:insertBeginning()
1574:{\displaystyle n}
1536:removeBeginning()
1295:well-known method
1259:round-robin order
1064:sequential access
1025:
1024:
990:Hashed array tree
86:
85:
78:
3904:
3709:Association list
3541:
3534:
3527:
3518:
3517:
3450:
3448:
3447:
3438:. Archived from
3430:
3418:
3394:
3375:
3359:
3345:
3343:
3342:
3336:
3326:
3314:
3292:
3282:
3252:
3235:
3199:
3163:
3144:
3119:
3117:
3116:
3096:
3094:
3093:
3087:
3080:
3061:
3060:
3054:
3050:
3048:
3040:
3038:
3036:
3030:
3019:
3004:
3003:
2985:
2979:
2978:
2962:
2951:
2950:
2948:
2933:
2927:
2916:
2910:
2903:GoingNative 2012
2894:
2888:
2887:
2885:
2884:
2878:
2872:. Archived from
2871:
2862:
2856:
2855:
2853:
2852:
2843:. Archived from
2837:
2828:
2827:
2802:
2785:
2783:
2781:
2780:
2775:
2763:
2761:
2760:
2755:
2743:
2741:
2740:
2735:
2723:
2721:
2720:
2715:
2703:
2701:
2700:
2695:
2683:
2681:
2680:
2675:
2650:
2246:external storage
2242:internal storage
2175:Language support
2086:
2082:
1936:
1935:
1822:newNode :=
1720:node ≠ someNode
1639:
1631:
1627:
1619:
1613:
1611:
1610:
1605:
1580:
1578:
1577:
1572:
1556:
1552:
1545:
1541:
1537:
1519:removeBeginning(
1472:insertBeginning(
1265:instead of two.
1204:
1200:
1112:times. Once the
1106:Josephus problem
965:
798:
794:
652:
649:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
610:
607:
604:
601:
598:
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
565:
562:
559:
556:
553:
550:
547:
544:
541:
538:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
496:
493:
490:
487:
484:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
439:
436:
433:
430:
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
385:
382:
355:
259:natural language
222:RAND Corporation
218:Herbert A. Simon
99:computer science
81:
74:
70:
67:
61:
56:this article by
47:inline citations
34:
33:
26:
3912:
3911:
3907:
3906:
3905:
3903:
3902:
3901:
3887:
3886:
3885:
3880:
3867:
3839:
3733:
3729:XOR linked list
3695:
3671:Circular buffer
3652:
3571:
3550:
3548:Data structures
3545:
3457:
3445:
3443:
3433:
3421:
3397:
3391:
3378:
3372:
3356:Algorithms in C
3348:
3340:
3338:
3334:
3329:
3317:
3311:
3295:
3255:
3238:
3232:
3216:Stein, Clifford
3202:
3196:
3180:Stein, Clifford
3166:
3160:
3147:
3141:
3122:
3114:
3112:
3099:
3091:
3089:
3085:
3078:
3073:
3070:
3068:Further reading
3065:
3064:
3052:
3051:
3042:
3041:
3034:
3032:
3028:
3020:
3007:
3000:
2986:
2982:
2963:
2954:
2946:
2934:
2930:
2917:
2913:
2895:
2891:
2882:
2880:
2876:
2869:
2863:
2859:
2850:
2848:
2839:
2838:
2831:
2824:
2812:. Vol. 3:
2803:
2799:
2794:
2789:
2788:
2769:
2766:
2765:
2749:
2746:
2745:
2729:
2726:
2725:
2709:
2706:
2705:
2689:
2686:
2685:
2657:
2654:
2653:
2651:
2647:
2642:
2577:
2543:
2504:
2487:
2445:
2414:firstName;
2374:
2340:
2305:firstName;
2283:
2238:
2177:
2111:
2084:
2080:
2031:Another, Anita
1931:
1918:
1881:parallel arrays
1865:
1860:
1831:
1789:
1771:
1761:
1721:
1688:
1646:
1633:
1629:
1625:
1615:
1590:
1587:
1586:
1566:
1563:
1562:
1554:
1550:
1543:
1539:
1535:
1532:
1514:
1485:
1460:
1430:
1412:
1395:
1361:
1356:
1335:
1303:
1239:
1215:
1202:
1198:
1193:such list. In
1154:
1146:red–black trees
963:
845:
812:
804:
793:
784:
776:
767:
758:
749:
740:
734:
706:
697:
665:
659:
654:
653:
650:
647:
644:
641:
638:
635:
632:
629:
626:
623:
620:
617:
614:
611:
608:
605:
602:
599:
596:
593:
590:
587:
584:
581:
578:
575:
572:
569:
566:
563:
560:
557:
554:
551:
548:
545:
542:
539:
536:
533:
530:
527:
524:
521:
518:
515:
512:
509:
506:
503:
500:
497:
494:
491:
488:
485:
482:
479:
476:
473:
470:
467:
464:
461:
458:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
395:
392:
389:
386:
383:
380:
362:
331:
278:Hans Peter Luhn
261:processing led
228:as the primary
206:
82:
71:
65:
62:
52:Please help to
51:
35:
31:
24:
17:
12:
11:
5:
3910:
3900:
3899:
3882:
3881:
3879:
3878:
3872:
3869:
3868:
3866:
3865:
3860:
3855:
3849:
3847:
3841:
3840:
3838:
3837:
3836:
3835:
3825:
3824:
3823:
3821:Hilbert R-tree
3818:
3813:
3803:
3802:
3801:
3799:Fibonacci heap
3796:
3791:
3781:
3780:
3779:
3774:
3769:
3767:Red–black tree
3764:
3759:
3749:
3743:
3741:
3735:
3734:
3732:
3731:
3726:
3721:
3716:
3711:
3705:
3703:
3697:
3696:
3694:
3693:
3688:
3683:
3678:
3673:
3668:
3662:
3660:
3654:
3653:
3651:
3650:
3649:
3648:
3643:
3633:
3632:
3631:
3624:Priority queue
3621:
3620:
3619:
3609:
3604:
3599:
3598:
3597:
3592:
3581:
3579:
3573:
3572:
3570:
3569:
3564:
3558:
3556:
3552:
3551:
3544:
3543:
3536:
3529:
3521:
3515:
3514:
3509:
3504:
3499:
3494:
3488:
3479:
3473:
3467:
3456:
3455:External links
3453:
3452:
3451:
3431:
3419:
3395:
3389:
3376:
3370:
3346:
3327:
3315:
3309:
3293:
3257:McCarthy, John
3253:
3236:
3230:
3200:
3194:
3164:
3158:
3145:
3139:
3120:
3097:
3069:
3066:
3063:
3062:
3005:
2998:
2980:
2952:
2928:
2911:
2889:
2857:
2829:
2822:
2796:
2795:
2793:
2790:
2787:
2786:
2773:
2753:
2733:
2713:
2693:
2673:
2670:
2667:
2664:
2661:
2644:
2643:
2641:
2638:
2576:
2573:
2542:
2539:
2530:red–black tree
2503:
2500:
2449:
2432:lastName;
2378:
2344:
2327:lastName;
2287:
2282:
2279:
2237:
2234:
2228:together with
2176:
2173:
2168:
2167:
2164:
2153:
2150:
2143:
2142:
2138:
2131:
2125:
2122:
2108:// print entry
2097:
2075:
2074:
2072:
2070:
2068:
2066:
2062:
2061:
2059:
2057:
2055:
2053:
2049:
2048:
2046:
2044:
2042:
2040:
2036:
2035:
2032:
2029:
2026:
2023:
2019:
2018:
2015:
2012:
2010:
2008:
2004:
2003:
2000:
1997:
1994:
1991:
1987:
1986:
1983:
1982:Smith, Joseph
1980:
1977:
1974:
1970:
1969:
1966:
1963:
1960:
1957:
1953:
1952:
1949:
1946:
1943:
1940:
1922:
1888:
1864:
1861:
1839:
1798:
1779:
1769:
1732:
1700:
1690:Assuming that
1687:
1684:
1645:
1642:
1603:
1600:
1597:
1594:
1570:
1540:list.firstNode
1515:
1501:
1468:
1443:
1420:
1396:
1373:
1360:
1357:
1355:
1352:
1334:
1331:
1302:
1299:
1238:
1235:
1214:
1211:
1153:
1150:
1084:Boolean values
1023:
1022:
1015:
1008:
1002:
995:
992:
986:
985:
978:
975:
972:
969:
966:
959:
958:
951:
944:
937:
934:
931:
925:
924:
917:
910:
904:
897:
894:
888:
887:
884:
881:
878:
875:
872:
866:
865:
858:
851:
842:
839:
832:
826:
825:
822:
819:
815:
814:
811:Excess space,
809:
806:
801:
792:
789:
783:
780:
775:
772:
766:
763:
757:
754:
748:
745:
736:Main article:
733:
732:Sentinel nodes
730:
705:
702:
696:
693:
661:Main article:
658:
655:
379:
361:
358:
352:' (pronounced
330:
327:
230:data structure
205:
202:
147:cache locality
111:data structure
84:
83:
38:
36:
29:
15:
9:
6:
4:
3:
2:
3909:
3898:
3895:
3894:
3892:
3877:
3874:
3873:
3870:
3864:
3861:
3859:
3856:
3854:
3851:
3850:
3848:
3846:
3842:
3834:
3831:
3830:
3829:
3826:
3822:
3819:
3817:
3814:
3812:
3809:
3808:
3807:
3804:
3800:
3797:
3795:
3794:Binomial heap
3792:
3790:
3787:
3786:
3785:
3782:
3778:
3775:
3773:
3770:
3768:
3765:
3763:
3760:
3758:
3755:
3754:
3753:
3750:
3748:
3745:
3744:
3742:
3740:
3736:
3730:
3727:
3725:
3722:
3720:
3717:
3715:
3712:
3710:
3707:
3706:
3704:
3702:
3698:
3692:
3691:Sparse matrix
3689:
3687:
3684:
3682:
3679:
3677:
3676:Dynamic array
3674:
3672:
3669:
3667:
3664:
3663:
3661:
3659:
3655:
3647:
3644:
3642:
3639:
3638:
3637:
3634:
3630:
3627:
3626:
3625:
3622:
3618:
3615:
3614:
3613:
3610:
3608:
3605:
3603:
3600:
3596:
3593:
3591:
3588:
3587:
3586:
3583:
3582:
3580:
3578:
3574:
3568:
3565:
3563:
3560:
3559:
3557:
3553:
3549:
3542:
3537:
3535:
3530:
3528:
3523:
3522:
3519:
3513:
3510:
3508:
3505:
3503:
3500:
3498:
3495:
3492:
3489:
3487:
3483:
3480:
3477:
3474:
3471:
3468:
3466:
3462:
3459:
3458:
3442:on 2009-09-25
3441:
3437:
3432:
3428:
3424:
3420:
3416:
3412:
3408:
3404:
3400:
3396:
3392:
3390:0-13-660911-2
3386:
3382:
3377:
3373:
3371:0-201-31452-5
3367:
3363:
3358:
3357:
3351:
3347:
3333:
3328:
3324:
3320:
3319:Newell, Allen
3316:
3312:
3310:0-201-89683-4
3306:
3302:
3298:
3297:Knuth, Donald
3294:
3290:
3286:
3281:
3276:
3272:
3268:
3267:
3262:
3258:
3254:
3250:
3246:
3242:
3237:
3233:
3231:0-262-03293-7
3227:
3223:
3222:
3217:
3213:
3209:
3205:
3201:
3197:
3195:0-262-03293-7
3191:
3187:
3186:
3181:
3177:
3173:
3169:
3165:
3161:
3159:0-07-282379-8
3155:
3151:
3146:
3142:
3140:0-13-280843-9
3136:
3132:
3128:
3127:
3121:
3111:
3107:
3103:
3102:"linked list"
3098:
3088:on 2012-01-06
3084:
3077:
3072:
3071:
3058:
3046:
3027:
3026:
3018:
3016:
3014:
3012:
3010:
3001:
2999:0-13-085850-1
2995:
2991:
2984:
2976:
2972:
2968:
2961:
2959:
2957:
2945:
2944:
2939:
2932:
2926:
2922:
2921:
2915:
2908:
2904:
2900:
2899:
2893:
2879:on 2016-10-01
2875:
2868:
2861:
2847:on 2015-09-23
2846:
2842:
2836:
2834:
2825:
2819:
2815:
2811:
2807:
2806:Knuth, Donald
2801:
2797:
2771:
2751:
2731:
2711:
2691:
2671:
2668:
2665:
2662:
2659:
2649:
2645:
2637:
2635:
2630:
2627:
2622:
2620:
2615:
2613:
2609:
2604:
2601:
2596:
2593:
2588:
2586:
2582:
2572:
2570:
2565:
2562:
2560:
2556:
2552:
2548:
2538:
2535:
2531:
2527:
2522:
2520:
2515:
2513:
2512:linear search
2509:
2499:
2495:
2493:
2485:
2481:
2478:
2474:
2471:
2467:
2463:
2460:
2456:
2453:
2448:
2443:
2439:
2436:address;
2435:
2431:
2428:
2424:
2421:
2417:
2413:
2410:
2406:
2403:
2399:
2395:
2391:
2388:
2384:
2381:
2377:
2372:
2369:
2365:
2362:
2358:
2355:
2351:
2348:
2343:
2338:
2334:
2331:address;
2330:
2326:
2322:
2319:
2315:
2312:
2308:
2304:
2300:
2297:
2293:
2290:
2286:
2278:
2275:
2271:
2266:
2262:
2259:
2253:
2251:
2247:
2243:
2233:
2231:
2227:
2223:
2218:
2216:
2215:
2210:
2209:
2204:
2200:
2199:
2194:
2190:
2186:
2182:
2172:
2165:
2162:
2158:
2154:
2151:
2148:
2147:
2146:
2139:
2136:
2132:
2129:
2126:
2123:
2120:
2116:
2115:
2114:
2109:
2105:
2101:
2096:
2093:
2090:
2073:
2071:
2069:
2067:
2064:
2063:
2060:
2058:
2056:
2054:
2051:
2050:
2047:
2045:
2043:
2041:
2038:
2037:
2033:
2030:
2027:
2024:
2021:
2020:
2016:
2013:
2011:
2009:
2006:
2005:
2001:
1998:
1995:
1992:
1990:2 (listHead)
1989:
1988:
1984:
1981:
1978:
1975:
1972:
1971:
1967:
1964:
1961:
1958:
1955:
1954:
1950:
1947:
1944:
1941:
1938:
1937:
1934:
1929:
1925:
1921:
1916:
1912:
1909:
1905:
1902:
1898:
1894:
1891:
1887:
1884:
1882:
1878:
1874:
1870:
1858:
1854:
1850:
1846:
1842:
1838:
1836:
1829:
1825:
1821:
1817:
1813:
1809:
1805:
1802:insertBefore(
1801:
1797:
1795:
1787:
1783:
1778:
1776:
1768:
1766:
1759:
1755:
1751:
1747:
1744:newNode)
1743:
1739:
1735:
1731:
1728:
1726:
1719:
1715:
1711:
1707:
1703:
1699:
1697:
1693:
1683:
1681:
1677:
1673:
1669:
1665:
1660:
1657:
1655:
1651:
1641:
1637:
1621:
1618:
1598:
1592:
1584:
1568:
1558:
1547:
1530:
1526:
1522:
1518:
1512:
1508:
1504:
1496:
1492:
1490:
1483:
1479:
1475:
1471:
1467:
1465:
1458:
1454:
1450:
1446:
1438:
1434:
1428:
1424:
1419:
1417:
1410:
1406:
1402:
1399:
1393:
1392:
1386:
1383:
1379:
1376:
1372:
1370:
1366:
1351:
1349:
1345:
1341:
1330:
1326:
1322:
1319:
1316:
1312:
1307:
1306:Sentinel node
1298:
1296:
1290:
1288:
1283:
1278:
1276:
1272:
1266:
1262:
1260:
1256:
1252:
1248:
1244:
1234:
1232:
1228:
1224:
1220:
1210:
1206:
1196:
1192:
1187:
1185:
1181:
1176:
1174:
1170:
1166:
1162:
1157:
1149:
1147:
1143:
1138:
1137:balanced tree
1133:
1131:
1127:
1122:
1120:
1115:
1111:
1107:
1102:
1100:
1096:
1091:
1089:
1085:
1081:
1076:
1074:
1070:
1065:
1061:
1060:random access
1057:
1052:
1049:
1043:
1041:
1040:fragmentation
1035:
1032:
1031:
1030:dynamic array
1020:
1016:
1013:
1009:
1007:
1003:
1000:
996:
993:
991:
988:
987:
983:
979:
970:
967:
961:
960:
956:
952:
949:
945:
942:
938:
935:
932:
930:
929:Balanced tree
927:
926:
922:
918:
915:
911:
909:
905:
902:
898:
895:
893:
892:Dynamic array
890:
889:
885:
873:
871:
868:
867:
863:
859:
856:
852:
849:
843:
840:
837:
833:
831:
828:
827:
823:
820:
817:
816:
799:
788:
779:
771:
762:
753:
744:
739:
738:Sentinel node
729:
722:
718:
716:
711:
701:
692:
690:
685:
682:
673:
669:
664:
390:addNodeToTail
377:
370:
366:
357:
351:
347:
342:
338:
336:
326:
322:
320:
316:
315:Motorola 6800
312:
307:
304:
299:
297:
293:
292:John McCarthy
289:
285:
283:
279:
274:
272:
268:
264:
260:
256:
252:
247:
243:
239:
235:
231:
227:
223:
219:
215:
211:
201:
198:
197:random access
193:
190:
186:
182:
177:
175:
174:S-expressions
171:
167:
163:
159:
155:
150:
148:
144:
140:
136:
132:
128:
124:
120:
116:
112:
108:
104:
100:
90:
80:
77:
69:
59:
55:
49:
48:
42:
37:
28:
27:
22:
3897:Linked lists
3713:
3646:Disjoint-set
3444:. Retrieved
3440:the original
3426:
3406:
3402:
3380:
3355:
3339:. Retrieved
3322:
3300:
3270:
3264:
3240:
3219:
3183:
3149:
3125:
3113:. Retrieved
3105:
3090:. Retrieved
3083:the original
3033:. Retrieved
3024:
2989:
2983:
2966:
2942:
2931:
2924:
2919:
2914:
2906:
2902:
2897:
2892:
2881:. Retrieved
2874:the original
2860:
2849:. Retrieved
2845:the original
2813:
2809:
2800:
2648:
2631:
2623:
2616:
2605:
2597:
2589:
2578:
2566:
2563:
2544:
2523:
2518:
2516:
2507:
2505:
2496:
2491:
2488:
2483:
2479:
2476:
2472:
2469:
2465:
2461:
2458:
2454:
2451:
2446:
2441:
2437:
2433:
2429:
2426:
2422:
2419:
2415:
2411:
2408:
2404:
2401:
2397:
2393:
2389:
2386:
2382:
2379:
2375:
2370:
2367:
2363:
2360:
2356:
2353:
2349:
2346:
2341:
2336:
2332:
2328:
2324:
2320:
2317:
2313:
2310:
2306:
2302:
2298:
2295:
2291:
2288:
2284:
2273:
2269:
2267:
2263:
2257:
2254:
2245:
2241:
2239:
2219:
2212:
2206:
2202:
2196:
2178:
2169:
2144:
2112:
2107:
2103:
2099:
2094:
2078:
1999:Adams, Adam
1965:Jones, John
1932:
1927:
1923:
1919:
1914:
1910:
1907:
1903:
1900:
1896:
1892:
1889:
1885:
1866:
1859:removedData
1856:
1852:
1848:
1844:
1840:
1834:
1832:
1827:
1823:
1819:
1815:
1811:
1807:
1803:
1799:
1793:
1790:
1785:
1781:
1774:
1772:
1764:
1762:
1757:
1753:
1749:
1745:
1741:
1737:
1736:insertAfter(
1733:
1729:
1724:
1722:
1717:
1713:
1709:
1705:
1701:
1695:
1691:
1689:
1679:
1675:
1671:
1667:
1663:
1661:
1658:
1653:
1649:
1647:
1635:
1622:
1559:
1555:removeBefore
1551:insertBefore
1548:
1534:Notice that
1533:
1528:
1524:
1520:
1516:
1510:
1506:
1505:removeAfter(
1502:
1488:
1486:
1481:
1477:
1473:
1469:
1463:
1461:
1456:
1452:
1448:
1447:insertAfter(
1444:
1431:
1426:
1422:
1415:
1413:
1408:
1404:
1400:
1397:
1388:
1384:
1381:
1380:{ data;
1377:
1374:
1368:
1364:
1362:
1343:
1336:
1327:
1323:
1320:
1314:
1310:
1304:
1291:
1286:
1281:
1279:
1267:
1263:
1245:, a pool of
1240:
1226:
1222:
1216:
1207:
1190:
1188:
1180:tail-sharing
1177:
1164:
1158:
1155:
1134:
1126:list ranking
1123:
1118:
1113:
1109:
1103:
1092:
1088:memory pools
1077:
1053:
1044:
1036:
1028:
1026:
1018:
1011:
998:
981:
954:
947:
940:
920:
913:
900:
861:
854:
847:
835:
829:
785:
777:
768:
765:List handles
759:
756:Hash linking
750:
741:
727:
707:
698:
686:
678:
666:
375:
363:
343:
339:
332:
323:
308:
300:
286:
275:
263:Victor Yngve
251:Turing Award
210:Allen Newell
207:
194:
185:contiguously
178:
156:, including
151:
145:have better
130:
102:
96:
72:
63:
44:
3789:Binary heap
3714:Linked list
3461:Description
3053:|work=
2600:binary tree
1917:balance; }
1708:someNode ≠
1620:procedure.
1255:time-shared
1219:XOR-linking
964:access list
830:Linked list
747:Empty lists
681:XOR-linking
271:linguistics
103:linked list
58:introducing
3777:Splay tree
3681:Hash table
3562:Collection
3446:2009-09-21
3341:2009-09-21
3325:: 230–240.
3273:(4): 184.
3243:(2): 3–8.
3115:2004-12-14
3092:2011-07-10
2883:2021-08-31
2851:2015-07-31
2792:References
2619:hash table
2553:using the
2534:hash table
2475:memNode ≠
2457:famNode ≠
2392:next;
2366:aMember ≠
2352:aFamily ≠
2323:next;
2301:next;
2226:references
2163:constant).
2119:serialized
1913:name;
1847:node)
1686:Algorithms
1407:firstNode
1340:pseudocode
1099:CDR coding
1080:characters
818:Beginning
232:for their
214:Cliff Shaw
139:pipelining
66:March 2012
41:references
3833:Hash tree
3719:Skip list
3666:Bit array
3567:Container
3486:Pat Morin
3463:from the
3055:ignored (
3045:cite book
2969:: 86–95.
2669:∗
2592:skip list
2203:cons cell
2161:amortized
2089:free list
1926:listHead
1869:reference
1828:firstNode
1794:firstNode
1775:beginning
1664:firstNode
1636:firstNode
1480:newNode)
1464:firstNode
1455:newNode)
1391:reference
1365:firstNode
1275:face-edge
1271:quad-edge
1161:recursive
1142:AVL trees
1048:amortized
1006:amortized
968:Θ(log n)
936:Θ(log n)
933:Θ(log n)
908:amortized
782:Tradeoffs
354:/'kʊd.əɹ/
127:reference
3891:Category
3762:AVL tree
3641:Multiset
3590:Multimap
3577:Abstract
3352:(1998).
3259:(1960).
3182:(2003).
2808:(1998).
2684:, where
2569:min-list
2510:) time (
2440:members
2335:members
2183:such as
2085:ListFree
2081:ListHead
1951:Balance
1930:Records
1841:function
1800:function
1758:lastNode
1734:function
1702:function
1696:someNode
1692:someNode
1680:lastNode
1672:lastNode
1668:lastNode
1517:function
1503:function
1470:function
1445:function
1348:sentinel
1282:circular
1227:previous
1069:heapsort
813:average
805:(index)
689:rootkits
189:run-time
125:, and a
119:sequence
3816:R+ tree
3811:R* tree
3757:AA tree
3289:1489409
3131:165–190
2416:integer
2394:pointer
2309:age; }
2307:integer
2230:records
2034:876.54
2017:999.99
1985:234.56
1968:123.45
1924:integer
1904:integer
1897:integer
1877:records
1851:node ≠
1843:remove(
1810:node =
1748:node =
1247:buffers
1243:polygon
1169:merging
1165:smaller
1051:space.
962:Random-
824:Middle
204:History
54:improve
3845:Graphs
3806:R-tree
3747:B-tree
3701:Linked
3658:Arrays
3387:
3368:
3362:90–109
3307:
3287:
3228:
3192:
3156:
3137:
3035:May 7,
2996:
2820:
2585:queues
2581:stacks
2434:string
2430:string
2423:family
2420:record
2418:age }
2412:string
2405:member
2402:record
2380:record
2333:member
2329:string
2325:string
2321:family
2314:family
2311:record
2303:string
2299:member
2292:member
2289:record
2189:Scheme
2133:Naïve
2102:i ≥ 0
1939:Index
1911:string
1906:prev;
1899:next;
1895:{
1890:record
1857:return
1740:node,
1617:append
1523:list)
1509:node)
1476:list,
1451:node,
1403:{
1398:record
1375:record
1287:linear
946:Θ(log
939:Θ(log
639:return
441:sizeof
435:malloc
246:UNESCO
172:, and
166:queues
162:stacks
143:Arrays
135:linear
107:points
43:, but
3739:Trees
3612:Queue
3607:Stack
3555:Types
3335:(PDF)
3285:S2CID
3086:(PDF)
3079:(PDF)
2947:(PDF)
2877:(PDF)
2870:(PDF)
2640:Notes
2612:cache
2579:Both
2526:index
2473:while
2455:while
2396:data
2364:while
2350:while
2272:(and
2179:Many
2141:size.
2100:while
2002:0.00
1948:Name
1945:Prev
1942:Next
1928:Entry
1893:Entry
1873:array
1725:while
1718:while
1650:null.
1638:.next
1634:list.
1538:sets
1489:after
1423:while
1389:// A
1387:next
1191:every
1004:Θ(1)
994:Θ(1)
971:Θ(1)
906:Θ(1)
896:Θ(1)
874:Θ(1)
870:Array
841:Θ(1)
803:Peek
618:->
600:->
573:->
564:while
480:->
468:value
462:value
459:->
411:value
181:array
158:lists
115:nodes
93:list.
3828:Trie
3784:Heap
3602:List
3385:ISBN
3366:ISBN
3305:ISBN
3226:ISBN
3190:ISBN
3154:ISBN
3135:ISBN
3057:help
3037:2015
3029:(PS)
2994:ISBN
2818:ISBN
2764:and
2626:heap
2590:The
2583:and
2492:node
2477:null
2459:null
2438:node
2390:node
2383:node
2368:null
2354:null
2274:prev
2270:next
2258:next
2198:cons
2187:and
2185:Lisp
1915:real
1853:null
1845:Node
1835:next
1820:else
1812:null
1804:Node
1786:null
1784:L =
1754:else
1750:null
1742:Node
1738:Node
1710:null
1676:null
1666:and
1654:next
1628:and
1544:null
1521:List
1507:Node
1478:Node
1474:List
1453:Node
1449:Node
1416:next
1405:Node
1401:List
1385:Node
1378:Node
1369:null
1344:null
1293:One
1273:and
1251:FIFO
1195:Lisp
1124:The
821:End
715:list
710:null
642:head
627:temp
621:next
603:next
582:NULL
576:next
555:head
543:Node
537:else
525:temp
519:head
510:NULL
504:head
489:NULL
483:next
477:temp
456:temp
447:temp
429:temp
423:Node
402:head
396:Node
384:Node
346:Lisp
335:node
288:LISP
257:for
224:and
216:and
131:link
123:data
101:, a
3636:Set
3411:doi
3275:doi
3245:doi
2971:doi
2923:at
2905:on
2901:at
2606:An
2532:or
2214:cdr
2208:car
2201:or
1996:−1
1976:−1
1875:of
1824:new
1816:new
1765:end
1585:of
1553:or
1542:to
1257:in
1201:or
1199:nil
1144:or
1082:or
1017:Θ(√
408:int
350:cdr
337:'.
282:IBM
265:at
220:at
97:In
3893::
3484:,
3405:.
3364:.
3283:.
3269:.
3263:.
3214:;
3210:;
3206:;
3178:;
3174:;
3170:;
3133:.
3108:.
3104:.
3049::
3047:}}
3043:{{
3008:^
2955:^
2832:^
2632:A
2624:A
2617:A
2598:A
2561:.
2545:A
2444:}
2425:{
2407:{
2400:}
2385:{
2339:}
2316:{
2294:{
2232:.
2065:7
2052:6
2039:5
2028:2
2025:0
2022:4
2007:3
1993:4
1979:0
1973:1
1962:4
1959:1
1956:0
1849:if
1808:if
1782:if
1746:if
1714:do
1706:if
1698::
1640:.
1466:.
1411:}
1277:.
1233:.
1205:.
1203:()
1148:.
1135:A
1090:.
1027:A
1021:)
1014:)
1010:Θ(
1001:)
997:Θ(
984:)
980:Θ(
977:—
974:—
957:)
953:Θ(
950:)
943:)
923:)
919:Θ(
916:)
912:Θ(
903:)
899:Θ(
886:0
883:—
880:—
877:—
864:)
860:Θ(
857:)
853:Θ(
846:Θ(
838:)
834:Θ(
579:!=
507:==
498:if
450:);
212:,
168:,
164:,
160:,
3540:e
3533:t
3526:v
3449:.
3417:.
3413::
3407:4
3393:.
3374:.
3344:.
3313:.
3291:.
3277::
3271:3
3251:.
3247::
3234:.
3198:.
3162:.
3143:.
3118:.
3095:.
3059:)
3039:.
3002:.
2977:.
2973::
2886:.
2854:.
2826:.
2772:B
2752:K
2732:n
2712:B
2692:K
2672:n
2666:B
2663:+
2660:K
2508:n
2490:(
2157:O
1602:)
1599:n
1596:(
1593:O
1569:n
1315:x
1311:x
1119:n
1114:n
1110:n
1019:n
1012:n
999:n
982:n
955:n
948:n
941:n
921:n
914:n
901:n
862:n
855:n
848:n
836:n
651:}
645:;
636:}
630:;
624:=
615:p
612:}
606:;
597:p
594:=
591:p
588:{
585:)
570:p
567:(
558:;
552:=
549:p
546:*
540:{
534:}
528:;
522:=
516:{
513:)
501:(
492:;
486:=
471:;
465:=
444:*
438:(
432:=
426:*
417:{
414:)
405:,
399:*
393:(
387:*
79:)
73:(
68:)
64:(
50:.
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.