 | This article needs additional citations for verification .(January 2021) |
In computer programming, a sentinel node is a specifically designated node used with linked lists and trees as a traversal path terminator. This type of node does not hold or reference any data managed by the data structure.
| |
Sentinels are used as an alternative over using NULL as the path terminator in order to get one or more of the following benefits:
Below are two versions of a subroutine (implemented in the C programming language) for looking up a given search key in a singly linked list. The first one uses the sentinel value NULL, and the second one a (pointer to the) sentinel node Sentinel, as the end-of-list indicator. The declarations of the singly linked list data structure and the outcomes of both subroutines are the same.
structsll_node{// one node of the singly linked liststructsll_node*next;// end-of-list indicator or -> next nodeintkey;}sll,*first;// global initializationfirst=NULL;// before the first insertion (not shown)structsll_node*Search(structsll_node*first,intsearch_key){structsll_node*node;for(node=first;node!=NULL;node=node->next){if(node->key==search_key)returnnode;// found}// search_key is not contained in the list:returnNULL;}The for-loop contains two tests (yellow lines) per iteration:
node != NULL;if (node->key == search_key).The globally available pointer sentinel to the deliberately prepared data structure Sentinel is used as end-of-list indicator.
// global variablesll_nodeSentinel,*sentinel=&Sentinel;// global initializationsentinel->next=sentinel;first=sentinel;// before the first insertion (not shown)Note that the pointer sentinel has always to be kept at the end of the list. This has to be maintained by the insert and delete functions. It is, however, about the same effort as when using a NULL pointer.
structsll_node*SearchWithSentinelnode(structsll_node*first,intsearch_key){structsll_node*node;// Prepare the “node” Sentinel for the search:sentinel->key=search_key;for(node=first;node->key!=search_key;node=node->next){}// Post-processing:if(node!=sentinel)returnnode;// found// search_key is not contained in the list:returnNULL;}The for-loop contains only one test (yellow line) per iteration:
node->key != search_key;.Linked list implementations, especially one of a circular, doubly-linked list, can be simplified remarkably using a sentinel node to demarcate the beginning and end of the list.
Following is a Python implementation of a circular doubly-linked list:
classNode:def__init__(self,data,next=None,prev=None):self.data=dataself.next=nextself.prev=prevdef__repr__(self)->str:returnf'Node(data={self.data})'classLinkedList:def__init__(self):self._sentinel=Node(data=None)self._sentinel.next=self._sentinelself._sentinel.prev=self._sentineldefpop_left(self)->Node:returnself.remove_by_ref(self._sentinel.next)defpop(self)->Node:returnself.remove_by_ref(self._sentinel.prev)defappend_nodeleft(self,node):self.add_node(self._sentinel,node)defappend_node(self,node):self.add_node(self._sentinel.prev,node)defappend_left(self,data):node=Node(data=data)self.append_nodeleft(node)defappend(self,data):node=Node(data=data)self.append_node(node)defremove_by_ref(self,node)->Node:ifnodeisself._sentinel:raiseException('Can never remove sentinel.')node.prev.next=node.nextnode.next.prev=node.prevnode.prev=Nonenode.next=Nonereturnnodedefadd_node(self,curnode,newnode):newnode.next=curnode.nextnewnode.prev=curnodecurnode.next.prev=newnodecurnode.next=newnodedefsearch(self,value):self._sentinel.data=valuenode=self._sentinel.nextwhilenode.data!=value:node=node.nextself._sentinel.data=Noneifnodeisself._sentinel:returnNonereturnnodedef__iter__(self):node=self._sentinel.nextwhilenodeisnotself._sentinel:yieldnode.datanode=node.nextdefreviter(self):node=self._sentinel.prevwhilenodeisnotself._sentinel:yieldnode.datanode=node.prevNotice how the add_node() method takes the node that will be displaced by the new node in the parameter curnode. For appending to the left, this is the head of a non-empty list, while for appending to right, it is the tail. But because of how the linkage is set up to refer back to the sentinel, the code just works for empty lists as well, where curnode will be the sentinel node.
General declarations, similar to article Binary search tree:
structbst_node{// one node of the binary search treestructbst_node*child[2];// each: ->node or end-of-path indicatorintkey;};structbst{// binary search treestructbst_node*root;// ->node or end-of-path indicator}*BST;The globally available pointersentinel to the single deliberately prepared data structure Sentinel = *sentinel is used to indicate the absence of a child.
// global variablebst_nodeSentinel,*sentinel=&Sentinel;// global initializationSentinel.child[0]=Sentinel.child[1]=sentinel;BST->root=sentinel;// before the first insertion (not shown)Note that the pointer sentinel has always to represent every leaf of the tree. This has to be maintained by the insert and delete functions. It is, however, about the same effort as when using a NULL pointer.
structbst_node*SearchWithSentinelnode(structbst*bst,intsearch_key){structbst_node*node;// Prepare the “node” Sentinel for the search:sentinel->key=search_key;for(node=bst->root;;){if(search_key==node->key)break;ifsearch_key<node->key:node=node->child[0];// go leftelsenode=node->child[1];// go right}// Post-processing:if(node!=sentinel)returnnode;// found// search_key is not contained in the tree:returnNULL;}
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is linear with respect to the height of the tree.
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains data, and a reference 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 linear 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. Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists.
In computer science, a red–black tree is a self-balancing binary search tree data structure noted for fast storage and retrieval of ordered information. The nodes in a red-black tree hold an extra "color" bit, often drawn as red and black, which help ensure that the tree is always approximately balanced.
In computer science, a trie, also called digital tree or prefix tree, is a type of search tree: specifically, a k-ary tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In order to access a key, the trie is traversed depth-first, following the links between nodes, which represent each character in the key.
In computer programming, lazy initialization is the tactic of delaying the creation of an object, the calculation of a value, or some other expensive process until the first time it is needed. It is a kind of lazy evaluation that refers specifically to the instantiation of objects or other resources.
In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type, or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. Only one of the types can be in use at any one time, and a tag field explicitly indicates which type is in use. It can be thought of as a type that has several "cases", each of which should be handled correctly when that type is manipulated. This is critical in defining recursive datatypes, in which some component of a value may have the same type as that value, for example in defining a type for representing trees, where it is necessary to distinguish multi-node subtrees and leaves. Like ordinary unions, tagged unions can save storage by overlapping storage areas for each type, since only one is in use at a time.
The syntax of the C programming language is the set of rules governing writing of software in C. It is designed to allow for programs that are extremely terse, have a close relationship with the resulting object code, and yet provide relatively high-level data abstraction. C was the first widely successful high-level language for portable operating-system development.
In computer science, a pointer is an object in many programming languages that stores a memory address. This can be that of another value located in computer memory, or in some cases, that of memory-mapped computer hardware. A pointer references a location in memory, and obtaining the value stored at that location is known as dereferencing the pointer. As an analogy, a page number in a book's index could be considered a pointer to the corresponding page; dereferencing such a pointer would be done by flipping to the page with the given page number and reading the text found on that page. The actual format and content of a pointer variable is dependent on the underlying computer architecture.
In computer science, tree traversal is a form of graph traversal and refers to the process of visiting each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a binary tree, but they may be generalized to other trees as well.
In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data. A similar but distinct concept is generative recursion, which may lack a definite "direction" inherent in corecursion and recursion.
In computer science, pointer swizzling is the conversion of references based on name or position into direct pointer references. It is typically performed during deserialization or loading of a relocatable object from a disk file, such as an executable file or pointer-based data structure.
typedef is a reserved keyword in the programming languages C, C++, and Objective-C. It is used to create an additional name (alias) for another data type, but does not create a new type, except in the obscure case of a qualified typedef of an array type where the typedef qualifiers are transferred to the array element type. As such, it is often used to simplify the syntax of declaring complex data structures consisting of struct and union types, although it is also commonly used to provide specific descriptive type names for integer data types of varying sizes.
In computer science, a ternary search tree is a type of trie where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather than the binary tree's limit of two. Like other prefix trees, a ternary search tree can be used as an associative map structure with the ability for incremental string search. However, ternary search trees are more space efficient compared to standard prefix trees, at the cost of speed. Common applications for ternary search trees include spell-checking and auto-completion.
In computer programming, a sentinel value is a special value in the context of an algorithm which uses its presence as a condition of termination, typically in a loop or recursive algorithm.
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.
The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.
In computing, a threaded binary tree is a binary tree variant that facilitates traversal in a particular order.
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields and one data field. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.
In object-oriented computer programming, a null object is an object with no referenced value or with defined neutral (null) behavior. The null object design pattern, which describes the uses of such objects and their behavior, was first published as "Void Value" and later in the Pattern Languages of Program Design book series as "Null Object".
C's offsetof macro is an ANSI C library feature found in stddef.h. It evaluates to the offset of a given member within a struct or union type, an expression of type size_t. The offsetof macro takes two parameters, the first being a structure or union name, and the second being the name of a subobject of the structure/union that is not a bit field. It cannot be described as a C prototype.
In computer science, a linked data structure is a data structure which consists of a set of data records (nodes) linked together and organized by references. The link between data can also be called a connector.