Linked List

From Chessprogramming wiki
Jump to: navigation, search

Home * Programming * Data * Linked List

Linked List,
a data structure to collect data entities in sequential order. Unlike an array or vector, where consecutive nodes or elements remain in sequential order in 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 pointer, 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 time complexity issues in traversing and maintaining the collection, that is in Big O notation constant O(1) versus linear O(n).

Forward List

Singly-linked-list.svg
[1]

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 sentinel value like a null-pointer in C or a 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 algorithm with associated data, for instance all elements of a linked list.

TNode* pNode = m_pHead;
while ( pNode ) {
   doSomething( pNode );
   pNode = pNode->pNext;
}

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.

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 */
}

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.

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;
}
CPT-LinkedLists-addingnode.svg
[2]

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.

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 */
}
CPT-LinkedLists-deletingnode.svg
[3]

Keeping a Tail

As demonstrated above, appending nodes at the end of the forward list has a 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, 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.

HejsbergLinkedList.JPG

Anders Hejlsberg on his favorite data structure [4]

Doubly Linked List

Doubly-linked-list.svg
[5]

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 functional Lisp and Scheme have singly linked lists built in along with cons. In fact, Lisp derives from "LISt Processing". Imperative, object oriented programming languages such as C++ or Java or their libraries provide abstract or generic container with an interface to iterate the elements of the container in sequential fashion. For instance C++ std::forward_list [6] with an iterator in a for-loop:

  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;

or, alternatively with modifying or non-modifying sequence operation [7] :

  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;

Lists in Computer Chess

In chess programming lists are applied with squares, pieces and moves, most often used within the search algorithm, implemented as pre-allocated arrays on the heap, stack or as static list in the data or bss segment. Typical examples are piece- and move-lists inside the search, or move-lists inside a game record. A bitboard is a kind of encapsulation of a list of squares through an iterator interface, and requires serialization to produce an explicit list.

Linked lists have applications in piece-lists, where due to captures pieces are removed in make move, and re-inserted in 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 with most pieces captured. A sample declaration and code was given by Daniel Shawul in CCC [8]. A special form of a linked list is the conditional skip list, as proposed in table-driven move generation.

See also

External Links

C++

Java

Lisp

Perl

Python

Ruby

TCL

.NET

Misc

References

  1. 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 Inkscape, Linked list from Wikipedia
  2. Diagram of inserting a node into a singly linked list, for linked list article. Made and granted into the public domain by Derrick Coetzee in Adobe Photoshop and Illustrator, April 24, 2011, Linked list from Wikipedia
  3. Diagram of deleting a node from a singly linked list, for linked list article. Created and released into the public domain by Derrick Coetzee in Adobe Photoshop and Illustrator, April 24, 2011, Linked list from Wikipedia
  4. image from Behind the Code with Anders Hejlsberg, from 0:50:52, YouTube Video
  5. Diagram of a doubly linked list made in Inkscape, Linked list from Wikipedia
  6. forward_list::begin - C++ Reference
  7. STL Algorithms - C++ Reference
  8. Re: Is there such a thing as branchless move generation? by Daniel Shawul, CCC, June 10, 2012

Up one Level