25,161
edits
Changes
Created page with "'''Home * Programming * Data * Linked List''' '''Linked List''',<br/> a data structure to [https://en.wikipedia.org/wiki/Collection_%28abstract_data_typ..."
'''[[Main Page|Home]] * [[Programming]] * [[Data]] * Linked List'''
'''Linked List''',<br/>
a data structure to [https://en.wikipedia.org/wiki/Collection_%28abstract_data_type%29 collect] data entities in [https://en.wikipedia.org/wiki/Sequence sequential] order. Unlike an [[Array|array]] or vector, where consecutive nodes or elements remain in sequential order in [[Memory|memory]] for sequential as well as random access, each node of a linked list is composed of a datum and one or more explicit links, a [https://en.wikipedia.org/wiki/Pointer_%28computer_programming%29 pointer], [https://en.wikipedia.org/wiki/Reference_%28computer_science%29 reference] or index to the next and/or previous node of the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence, without copying other nodes around but only to update some references. The ratio of the pure data size to the complete size of a node with its references is somehow a measure of the lists data efficiency. In choosing data structures like arrays versus linked lists, one has to consider [https://en.wikipedia.org/wiki/Time_complexity time complexity] issues in traversing and maintaining the collection, that is in [https://en.wikipedia.org/wiki/Big_O_notation Big O notation] constant O(1) versus linear O(n).
=Forward List=
[[FILE:Singly-linked-list.svg|none|border|text-bottom]] <ref>A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list, Diagram of a singly linked list made in [https://en.wikipedia.org/wiki/Inkscape Inkscape], [https://en.wikipedia.org/wiki/Linked_list Linked list from Wikipedia]</ref>
A forward list or '''singly linked''' list consists of one reference per node to the next element. A '''head''' reference is used to indicate the first element of the list, and in linear lists the last node is linked to a terminator used to signify the end of the list, either a [https://en.wikipedia.org/wiki/Sentinel_value sentinel value] like a [https://en.wikipedia.org/wiki/Null_pointer#Null_pointer null-pointer] in [[C]] or a [https://en.wikipedia.org/wiki/Sentinel_node sentinel node] with a terminator symbol in its data field. Another convention is to refer the first node from the last node for a so called circular or circularly linked list, opposed to the open or linear list.
==Iteration==
[[Iteration]] is the act of repeating instructions inside an [[Algorithms|algorithm]] with associated [[Data|data]], for instance all elements of a linked list.
<pre>
TNode* pNode = m_pHead;
while ( pNode ) {
doSomething( pNode );
pNode = pNode->pNext;
}
</pre>
==Lookup==
To find a particular node requires traversal, that is iteration, starting from the head of the list. Since some actions require modifications on the previous node, not only the found node if any is returned, but also the pointer to the previous node if any.
<pre>
TNode* TList::findNode(Property property, TNode **ppPrevious) {
TNode* pNode = m_pHead;
*ppPrevious = NULL
while ( pNode ) {
if ( pNode->hasProperty(property) )
return pNode;
*ppPrevious = pNode;
pNode = pNode->pNext;
}
return NULL; /* not found */
}
</pre>
==Insertion==
To insert behind a found node requires modification of two references. The found node need to refer the new node, and the new node to refer the node which was previously the next node of the found node. If no node is found, the new node is appended at the end of the list. If the list is empty, the head is set accordantly, with the new node's next referring nil.
<pre>
TNode* TList::insertBehind(TNode *pNewNode, Property property) {
TNode* pPrevious;
TNode* pNode = findNode(property, &pPrevious);
if ( pNode ) {
pNewNode->pNext = pNode->pNext;
pNode->pNext = pNewNode;
} else if ( pPrevious ) {
pNewNode->pNext = NULL;
pPrevious->pNext = pNewNode;
} else {
pNewNode->pNext = NULL;
m_pHead = pNewNode;
}
return pNewNode;
}
</pre>
[[FILE:CPT-LinkedLists-addingnode.svg|none|border|text-bottom]] <ref>Diagram of inserting a node into a singly linked list, for [https://en.wikipedia.org/wiki/Linked_list linked list] article. Made and granted into the public domain by [https://en.wikipedia.org/wiki/User:Dcoetzee Derrick Coetzee] in [https://en.wikipedia.org/wiki/Adobe_Photoshop Adobe Photoshop] and [https://en.wikipedia.org/wiki/Adobe_Illustrator Illustrator], April 24, 2011, [https://en.wikipedia.org/wiki/Linked_list Linked list from Wikipedia]</ref>
==Removal==
The removal of a node requires to refer the previous node no longer to the found node to be removed, but to its next node. In case the found node is the first one, the head reference is modified to skip that node as well.
<pre>
TNode* TList::remove(Property property) {
TNode* pPrevious;
TNode* pNode = findNode(property, &pPrevious);
if ( pNode ) {
if ( pPrevious ) {
pPrevious->pNext = pNode->pNext;
} else {
m_pHead = pNode->pNext;
}
}
return pNode; /* if NULL, nothing was removed */
}
</pre>
[[FILE:CPT-LinkedLists-deletingnode.svg|none|border|text-bottom]] <ref>Diagram of deleting a node from a singly linked list, for [https://en.wikipedia.org/wiki/Linked_list linked list] article. Created and released into the public domain by [https://en.wikipedia.org/wiki/User:Dcoetzee Derrick Coetzee] in [https://en.wikipedia.org/wiki/Adobe_Photoshop Adobe Photoshop] and [https://en.wikipedia.org/wiki/Adobe_Illustrator Illustrator], April 24, 2011, [https://en.wikipedia.org/wiki/Linked_list Linked list from Wikipedia]</ref>
==Keeping a Tail==
As demonstrated above, appending nodes at the end of the forward list has a [https://en.wikipedia.org/wiki/Asymptotic_computational_complexity asymptotic computational complexity] of O(n), because one has to traverse the entire list from its head. Therefor to speed up appending, some implementations keep not only the head as reference the first element of the list, but also a reference to the last element, dubbed tail. In an video interview, [https://en.wikipedia.org/wiki/Anders_Hejlsberg Anders Hejlsberg] elaborates on the question on his favorite data structure. Instead of a singly linked list with a head, he preferred a circularly linked list with a tail pointer only, to avoid traversal of the complete lists in order to append at the end, and to use tail->next to point to the head.
[[FILE:HejsbergLinkedList.JPG|none|border|text-bottom|link=C sharp#References]]
[https://en.wikipedia.org/wiki/Anders_Hejlsberg Anders Hejlsberg] on his favorite data structure <ref>image from [[C sharp#References|Behind the Code]] with [https://en.wikipedia.org/wiki/Anders_Hejlsberg Anders Hejlsberg], from 0:50:52, [https://en.wikipedia.org/wiki/YouTube YouTube] Video</ref>
<span id="Doubly"></span>
=Doubly Linked List=
[[FILE:Doubly-linked-list.svg|none|border|text-bottom]] <ref>Diagram of a doubly linked list made in [https://en.wikipedia.org/wiki/Inkscape Inkscape], [https://en.wikipedia.org/wiki/Linked_list Linked list from Wikipedia]</ref>
A doubly linked list allows efficient list traversal in forward and backward direction, and therefor each node requires one forward and backward reference to both next and previous node with little bit more effort to insert and remove nodes.
=Linked Lists in Programming Languages=
Programming languages such as the [https://en.wikipedia.org/wiki/Functional_programming functional] [[Lisp]] and [[Scheme]] have singly linked lists built in along with [https://en.wikipedia.org/wiki/Cons cons]. In fact, Lisp derives from "LISt Processing". [https://en.wikipedia.org/wiki/Imperative_programming Imperative], [https://en.wikipedia.org/wiki/Object-oriented_programming object oriented] programming languages such as [[Cpp|C++]] or [[Java]] or their libraries provide [https://en.wikipedia.org/wiki/Container_%28abstract_data_type%29 abstract] or [[Generic Programming|generic]] container with an [https://en.wikipedia.org/wiki/Protocol_%28object-oriented_programming%29 interface] to [[Iteration|iterate]] the elements of the container in sequential fashion. For instance [[Cpp|C++]] std::forward_list <ref>[http://www.cplusplus.com/reference/stl/forward_list/begin/ forward_list::begin - C++ Reference]</ref> with an iterator in a for-loop:
<pre>
std::forward_list<TSquare> knightTargetsd4 = {e6,f5,f3,e2,c2,b3,b5,c6};
std::cout << "knight on d4 attacks:";
for ( auto it = mylist.begin(); it != mylist.end(); ++it )
std::cout << " " << *it;
std::cout << std::endl;
</pre>
or, alternatively with modifying or non-modifying sequence operation <ref>[http://www.cplusplus.com/reference/algorithm/ STL Algorithms - C++ Reference]</ref> :
<pre>
std::forward_list<TSquare> knightTargetsd4 = {e6,f5,f3,e2,c2,b3,b5,c6};
std::cout << "knight on d4 attacks:";
for_each (knightTargetsd4.begin(), knightTargetsd4.end(), print);
std::cout << std::endl;
</pre>
=Lists in Computer Chess=
In chess programming lists are applied with [[Squares|squares]], [[Pieces|pieces]] and [[Moves|moves]], most often used within the [[Search|search]] algorithm, implemented as pre-allocated arrays on the [https://en.wikipedia.org/wiki/Memory_pool heap], [[Stack|stack]] or as static list in the [https://en.wikipedia.org/wiki/Data_segment data] or [https://en.wikipedia.org/wiki/.bss bss] segment. Typical examples are [[Piece-Lists|piece-]] and [[Move List|move-lists]] inside the search, or move-lists inside a [[Chess Game|game record]]. A [[Bitboards|bitboard]] is a kind of [https://en.wikipedia.org/wiki/Encapsulation_%28object-oriented_programming%29 encapsulation] of a list of squares through an iterator interface, and requires [[Bitboard Serialization|serialization]] to produce an explicit list.
Linked lists have applications in piece-lists, where due to [[Captures|captures]] pieces are removed in [[Make Move|make move]], and re-inserted in [[Unmake Move|unmake move]], where modifying references is versatile rather than copying elements of an array around, or to tag pieces as removed, and to traverse always 16 elements rather than a few in the late [[Endgame|endgame]] with most pieces captured. A sample declaration and code was given by [[Daniel Shawul]] in [[CCC]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=468678&t=43971 Re: Is there such a thing as branchless move generation?] by [[Daniel Shawul]], [[CCC]], June 10, 2012</ref>. A special form of a linked list is the conditional [https://en.wikipedia.org/wiki/Skip_list skip list], as proposed in [[Table-driven Move Generation|table-driven move generation]].
=See also=
* [[Array]]
* [[De Bruijn Sequence]]
* [[Iteration]]
* [[Move List]]
* [[Piece-Lists]]
* [[Priority Queue]]
* [[Queue]] (FIFO)
* [[Stack]] (LIFO)
* [[Table-driven Move Generation]]
=External Links=
* [https://en.wikipedia.org/wiki/List_%28abstract_data_type%29 List (abstract data type) from Wikipedia]
* [https://en.wikipedia.org/wiki/Linked_data_structure Linked data structure from Wikipedia]
* [https://en.wikipedia.org/wiki/Linked_list Linked list from Wikipedia]
* [https://en.wikipedia.org/wiki/Doubly_linked_list Doubly linked list from Wikipedia]
* [https://en.wikipedia.org/wiki/Dancing_Links Dancing Links from Wikipedia]
* [https://en.wikipedia.org/wiki/Self-organizing_list Self-organizing list from Wikipedia]
* [https://en.wikipedia.org/wiki/Skip_list Skip list from Wikipedia]
* [https://en.wikipedia.org/wiki/Unrolled_linked_list Unrolled linked listfrom Wikipedia]
* [https://en.wikipedia.org/wiki/VList VList from Wikipedia]
* [https://en.wikipedia.org/wiki/XOR_linked_list XOR linked list from Wikipedia]
==[[Cpp|C++]]==
* [http://www.cplusplus.com/reference/stl/forward_list/ forward_list - C++ Reference]
* [http://www.cplusplus.com/reference/stl/list/ list - C++ Reference]
* [http://www.boost.org/doc/libs/1_51_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.slist Boost | Non-standard containers - 1.51.0 | slist]
* [http://qt-project.org/doc/qt-4.8/qlist.html QList | Documentation | Qt Developer Network]
* [http://qt-project.org/doc/qt-4.8/qlinkedlist.html QLinkedList | Documentation | Qt Developer Network]
* [http://msdn.microsoft.com/de-de/library/bxde0zae%28v=vs.80%29.aspx CList Class (MFC)]
* [http://www.codeproject.com/Articles/662/A-Beginner-s-Guide-to-the-Linked-List A Beginner's Guide to the Linked List - CodeProject]
==[[Java]]==
* [http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html LinkedList (Java Platform SE 6)]
==[[Lisp]]==
* [http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node147.html Common Lisp the Language, 2nd Edition | 15 Lists] by [[Mathematician#GSteele|Guy L. Steele Jr.]], 1989
* [http://www.gnu.org/software/emacs/emacs-lisp-intro/html_node/Lisp-Lists.html Lisp Lists - Programming in Emacs Lisp]
==[[Perl]]==
* [http://www.cs.cmu.edu/afs/cs/usr/rgs/mosaic/pl-exp-arr.html PERL -- Array and List Functions]
* [http://www.misc-perl-info.com/perl-lists.html Perl Lists]
* [http://perldoc.perl.org/List/Util.html List::Util - perldoc.perl.org]
==[[Python]]==
* [http://docs.python.org/tutorial/datastructures.html 5. Data Structures — Python v2.7.3 documentation]
* [http://effbot.org/zone/python-list.htm An Introduction to Python Lists] by Fredrik Lundh | August 2006
* [http://www.tutorialspoint.com/python/python_lists.htm Python - List Data Types]
* [http://www.khanacademy.org/science/computer-science/v/python-lists Python Lists | Computer Science | Khan Academy]
* [http://www.diveintopython.net/native_data_types/lists.html Dive Into Python | 3.2. Introducing Lists]
==[[Ruby]]==
* [http://langref.org/ruby/lists angref.org - ruby - Lists]
==[[TCL-TK|TCL]]==
* [http://www.tcl.tk/man/tcl/tutorial/Tcl14.html Tcl Data Structures 101 - The list]
* [http://tmml.sourceforge.net/doc/tcl/ Tcl Reference Manual]
==.NET==
* [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List(T) Class (System.Collections.Generic)] [https://en.wikipedia.org/wiki/MSDN_Library MSDN Library]
* [http://www.dotnetperls.com/list C# List Examples]
==Misc==
* [[Videos#Kraan|Kraan]] - Head, 1972, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=vNeq_C-P7ak|alignment=left|valignment=top}}
=References=
<references />
'''[[Data|Up one Level]]'''
'''Linked List''',<br/>
a data structure to [https://en.wikipedia.org/wiki/Collection_%28abstract_data_type%29 collect] data entities in [https://en.wikipedia.org/wiki/Sequence sequential] order. Unlike an [[Array|array]] or vector, where consecutive nodes or elements remain in sequential order in [[Memory|memory]] for sequential as well as random access, each node of a linked list is composed of a datum and one or more explicit links, a [https://en.wikipedia.org/wiki/Pointer_%28computer_programming%29 pointer], [https://en.wikipedia.org/wiki/Reference_%28computer_science%29 reference] or index to the next and/or previous node of the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence, without copying other nodes around but only to update some references. The ratio of the pure data size to the complete size of a node with its references is somehow a measure of the lists data efficiency. In choosing data structures like arrays versus linked lists, one has to consider [https://en.wikipedia.org/wiki/Time_complexity time complexity] issues in traversing and maintaining the collection, that is in [https://en.wikipedia.org/wiki/Big_O_notation Big O notation] constant O(1) versus linear O(n).
=Forward List=
[[FILE:Singly-linked-list.svg|none|border|text-bottom]] <ref>A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list, Diagram of a singly linked list made in [https://en.wikipedia.org/wiki/Inkscape Inkscape], [https://en.wikipedia.org/wiki/Linked_list Linked list from Wikipedia]</ref>
A forward list or '''singly linked''' list consists of one reference per node to the next element. A '''head''' reference is used to indicate the first element of the list, and in linear lists the last node is linked to a terminator used to signify the end of the list, either a [https://en.wikipedia.org/wiki/Sentinel_value sentinel value] like a [https://en.wikipedia.org/wiki/Null_pointer#Null_pointer null-pointer] in [[C]] or a [https://en.wikipedia.org/wiki/Sentinel_node sentinel node] with a terminator symbol in its data field. Another convention is to refer the first node from the last node for a so called circular or circularly linked list, opposed to the open or linear list.
==Iteration==
[[Iteration]] is the act of repeating instructions inside an [[Algorithms|algorithm]] with associated [[Data|data]], for instance all elements of a linked list.
<pre>
TNode* pNode = m_pHead;
while ( pNode ) {
doSomething( pNode );
pNode = pNode->pNext;
}
</pre>
==Lookup==
To find a particular node requires traversal, that is iteration, starting from the head of the list. Since some actions require modifications on the previous node, not only the found node if any is returned, but also the pointer to the previous node if any.
<pre>
TNode* TList::findNode(Property property, TNode **ppPrevious) {
TNode* pNode = m_pHead;
*ppPrevious = NULL
while ( pNode ) {
if ( pNode->hasProperty(property) )
return pNode;
*ppPrevious = pNode;
pNode = pNode->pNext;
}
return NULL; /* not found */
}
</pre>
==Insertion==
To insert behind a found node requires modification of two references. The found node need to refer the new node, and the new node to refer the node which was previously the next node of the found node. If no node is found, the new node is appended at the end of the list. If the list is empty, the head is set accordantly, with the new node's next referring nil.
<pre>
TNode* TList::insertBehind(TNode *pNewNode, Property property) {
TNode* pPrevious;
TNode* pNode = findNode(property, &pPrevious);
if ( pNode ) {
pNewNode->pNext = pNode->pNext;
pNode->pNext = pNewNode;
} else if ( pPrevious ) {
pNewNode->pNext = NULL;
pPrevious->pNext = pNewNode;
} else {
pNewNode->pNext = NULL;
m_pHead = pNewNode;
}
return pNewNode;
}
</pre>
[[FILE:CPT-LinkedLists-addingnode.svg|none|border|text-bottom]] <ref>Diagram of inserting a node into a singly linked list, for [https://en.wikipedia.org/wiki/Linked_list linked list] article. Made and granted into the public domain by [https://en.wikipedia.org/wiki/User:Dcoetzee Derrick Coetzee] in [https://en.wikipedia.org/wiki/Adobe_Photoshop Adobe Photoshop] and [https://en.wikipedia.org/wiki/Adobe_Illustrator Illustrator], April 24, 2011, [https://en.wikipedia.org/wiki/Linked_list Linked list from Wikipedia]</ref>
==Removal==
The removal of a node requires to refer the previous node no longer to the found node to be removed, but to its next node. In case the found node is the first one, the head reference is modified to skip that node as well.
<pre>
TNode* TList::remove(Property property) {
TNode* pPrevious;
TNode* pNode = findNode(property, &pPrevious);
if ( pNode ) {
if ( pPrevious ) {
pPrevious->pNext = pNode->pNext;
} else {
m_pHead = pNode->pNext;
}
}
return pNode; /* if NULL, nothing was removed */
}
</pre>
[[FILE:CPT-LinkedLists-deletingnode.svg|none|border|text-bottom]] <ref>Diagram of deleting a node from a singly linked list, for [https://en.wikipedia.org/wiki/Linked_list linked list] article. Created and released into the public domain by [https://en.wikipedia.org/wiki/User:Dcoetzee Derrick Coetzee] in [https://en.wikipedia.org/wiki/Adobe_Photoshop Adobe Photoshop] and [https://en.wikipedia.org/wiki/Adobe_Illustrator Illustrator], April 24, 2011, [https://en.wikipedia.org/wiki/Linked_list Linked list from Wikipedia]</ref>
==Keeping a Tail==
As demonstrated above, appending nodes at the end of the forward list has a [https://en.wikipedia.org/wiki/Asymptotic_computational_complexity asymptotic computational complexity] of O(n), because one has to traverse the entire list from its head. Therefor to speed up appending, some implementations keep not only the head as reference the first element of the list, but also a reference to the last element, dubbed tail. In an video interview, [https://en.wikipedia.org/wiki/Anders_Hejlsberg Anders Hejlsberg] elaborates on the question on his favorite data structure. Instead of a singly linked list with a head, he preferred a circularly linked list with a tail pointer only, to avoid traversal of the complete lists in order to append at the end, and to use tail->next to point to the head.
[[FILE:HejsbergLinkedList.JPG|none|border|text-bottom|link=C sharp#References]]
[https://en.wikipedia.org/wiki/Anders_Hejlsberg Anders Hejlsberg] on his favorite data structure <ref>image from [[C sharp#References|Behind the Code]] with [https://en.wikipedia.org/wiki/Anders_Hejlsberg Anders Hejlsberg], from 0:50:52, [https://en.wikipedia.org/wiki/YouTube YouTube] Video</ref>
<span id="Doubly"></span>
=Doubly Linked List=
[[FILE:Doubly-linked-list.svg|none|border|text-bottom]] <ref>Diagram of a doubly linked list made in [https://en.wikipedia.org/wiki/Inkscape Inkscape], [https://en.wikipedia.org/wiki/Linked_list Linked list from Wikipedia]</ref>
A doubly linked list allows efficient list traversal in forward and backward direction, and therefor each node requires one forward and backward reference to both next and previous node with little bit more effort to insert and remove nodes.
=Linked Lists in Programming Languages=
Programming languages such as the [https://en.wikipedia.org/wiki/Functional_programming functional] [[Lisp]] and [[Scheme]] have singly linked lists built in along with [https://en.wikipedia.org/wiki/Cons cons]. In fact, Lisp derives from "LISt Processing". [https://en.wikipedia.org/wiki/Imperative_programming Imperative], [https://en.wikipedia.org/wiki/Object-oriented_programming object oriented] programming languages such as [[Cpp|C++]] or [[Java]] or their libraries provide [https://en.wikipedia.org/wiki/Container_%28abstract_data_type%29 abstract] or [[Generic Programming|generic]] container with an [https://en.wikipedia.org/wiki/Protocol_%28object-oriented_programming%29 interface] to [[Iteration|iterate]] the elements of the container in sequential fashion. For instance [[Cpp|C++]] std::forward_list <ref>[http://www.cplusplus.com/reference/stl/forward_list/begin/ forward_list::begin - C++ Reference]</ref> with an iterator in a for-loop:
<pre>
std::forward_list<TSquare> knightTargetsd4 = {e6,f5,f3,e2,c2,b3,b5,c6};
std::cout << "knight on d4 attacks:";
for ( auto it = mylist.begin(); it != mylist.end(); ++it )
std::cout << " " << *it;
std::cout << std::endl;
</pre>
or, alternatively with modifying or non-modifying sequence operation <ref>[http://www.cplusplus.com/reference/algorithm/ STL Algorithms - C++ Reference]</ref> :
<pre>
std::forward_list<TSquare> knightTargetsd4 = {e6,f5,f3,e2,c2,b3,b5,c6};
std::cout << "knight on d4 attacks:";
for_each (knightTargetsd4.begin(), knightTargetsd4.end(), print);
std::cout << std::endl;
</pre>
=Lists in Computer Chess=
In chess programming lists are applied with [[Squares|squares]], [[Pieces|pieces]] and [[Moves|moves]], most often used within the [[Search|search]] algorithm, implemented as pre-allocated arrays on the [https://en.wikipedia.org/wiki/Memory_pool heap], [[Stack|stack]] or as static list in the [https://en.wikipedia.org/wiki/Data_segment data] or [https://en.wikipedia.org/wiki/.bss bss] segment. Typical examples are [[Piece-Lists|piece-]] and [[Move List|move-lists]] inside the search, or move-lists inside a [[Chess Game|game record]]. A [[Bitboards|bitboard]] is a kind of [https://en.wikipedia.org/wiki/Encapsulation_%28object-oriented_programming%29 encapsulation] of a list of squares through an iterator interface, and requires [[Bitboard Serialization|serialization]] to produce an explicit list.
Linked lists have applications in piece-lists, where due to [[Captures|captures]] pieces are removed in [[Make Move|make move]], and re-inserted in [[Unmake Move|unmake move]], where modifying references is versatile rather than copying elements of an array around, or to tag pieces as removed, and to traverse always 16 elements rather than a few in the late [[Endgame|endgame]] with most pieces captured. A sample declaration and code was given by [[Daniel Shawul]] in [[CCC]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=468678&t=43971 Re: Is there such a thing as branchless move generation?] by [[Daniel Shawul]], [[CCC]], June 10, 2012</ref>. A special form of a linked list is the conditional [https://en.wikipedia.org/wiki/Skip_list skip list], as proposed in [[Table-driven Move Generation|table-driven move generation]].
=See also=
* [[Array]]
* [[De Bruijn Sequence]]
* [[Iteration]]
* [[Move List]]
* [[Piece-Lists]]
* [[Priority Queue]]
* [[Queue]] (FIFO)
* [[Stack]] (LIFO)
* [[Table-driven Move Generation]]
=External Links=
* [https://en.wikipedia.org/wiki/List_%28abstract_data_type%29 List (abstract data type) from Wikipedia]
* [https://en.wikipedia.org/wiki/Linked_data_structure Linked data structure from Wikipedia]
* [https://en.wikipedia.org/wiki/Linked_list Linked list from Wikipedia]
* [https://en.wikipedia.org/wiki/Doubly_linked_list Doubly linked list from Wikipedia]
* [https://en.wikipedia.org/wiki/Dancing_Links Dancing Links from Wikipedia]
* [https://en.wikipedia.org/wiki/Self-organizing_list Self-organizing list from Wikipedia]
* [https://en.wikipedia.org/wiki/Skip_list Skip list from Wikipedia]
* [https://en.wikipedia.org/wiki/Unrolled_linked_list Unrolled linked listfrom Wikipedia]
* [https://en.wikipedia.org/wiki/VList VList from Wikipedia]
* [https://en.wikipedia.org/wiki/XOR_linked_list XOR linked list from Wikipedia]
==[[Cpp|C++]]==
* [http://www.cplusplus.com/reference/stl/forward_list/ forward_list - C++ Reference]
* [http://www.cplusplus.com/reference/stl/list/ list - C++ Reference]
* [http://www.boost.org/doc/libs/1_51_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.slist Boost | Non-standard containers - 1.51.0 | slist]
* [http://qt-project.org/doc/qt-4.8/qlist.html QList | Documentation | Qt Developer Network]
* [http://qt-project.org/doc/qt-4.8/qlinkedlist.html QLinkedList | Documentation | Qt Developer Network]
* [http://msdn.microsoft.com/de-de/library/bxde0zae%28v=vs.80%29.aspx CList Class (MFC)]
* [http://www.codeproject.com/Articles/662/A-Beginner-s-Guide-to-the-Linked-List A Beginner's Guide to the Linked List - CodeProject]
==[[Java]]==
* [http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html LinkedList (Java Platform SE 6)]
==[[Lisp]]==
* [http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node147.html Common Lisp the Language, 2nd Edition | 15 Lists] by [[Mathematician#GSteele|Guy L. Steele Jr.]], 1989
* [http://www.gnu.org/software/emacs/emacs-lisp-intro/html_node/Lisp-Lists.html Lisp Lists - Programming in Emacs Lisp]
==[[Perl]]==
* [http://www.cs.cmu.edu/afs/cs/usr/rgs/mosaic/pl-exp-arr.html PERL -- Array and List Functions]
* [http://www.misc-perl-info.com/perl-lists.html Perl Lists]
* [http://perldoc.perl.org/List/Util.html List::Util - perldoc.perl.org]
==[[Python]]==
* [http://docs.python.org/tutorial/datastructures.html 5. Data Structures — Python v2.7.3 documentation]
* [http://effbot.org/zone/python-list.htm An Introduction to Python Lists] by Fredrik Lundh | August 2006
* [http://www.tutorialspoint.com/python/python_lists.htm Python - List Data Types]
* [http://www.khanacademy.org/science/computer-science/v/python-lists Python Lists | Computer Science | Khan Academy]
* [http://www.diveintopython.net/native_data_types/lists.html Dive Into Python | 3.2. Introducing Lists]
==[[Ruby]]==
* [http://langref.org/ruby/lists angref.org - ruby - Lists]
==[[TCL-TK|TCL]]==
* [http://www.tcl.tk/man/tcl/tutorial/Tcl14.html Tcl Data Structures 101 - The list]
* [http://tmml.sourceforge.net/doc/tcl/ Tcl Reference Manual]
==.NET==
* [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List(T) Class (System.Collections.Generic)] [https://en.wikipedia.org/wiki/MSDN_Library MSDN Library]
* [http://www.dotnetperls.com/list C# List Examples]
==Misc==
* [[Videos#Kraan|Kraan]] - Head, 1972, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=vNeq_C-P7ak|alignment=left|valignment=top}}
=References=
<references />
'''[[Data|Up one Level]]'''
