Following on from the discussion on implementing a singly linked-list in C, a logical follow-up data-structure is the doubly linked-list.
In a similar fashion, the structure is composed from a set of sequentially linked nodes, each now containing references (pointers) to not only the next node but the previous one to.
This structure is useful if the use-case dictates the desire to traverse the list both forwards and backwards, or quickly determine preceding and following elements from a given node.
The head and tail nodes can be terminated with either sentinel nodes (referred to as ‘circularly linked’ if only one is used) or like in the implementation shown below, NULL.
An observational implementation difference between the two structures is that through storing the previous and next reference, it can significantly simplify the complexity and running time of certain operations (removal from the tail being the most obvious).
Over the past couple of days I have become very interested in brushing up on my limited C knowledge.
As I discussed in my previous post on using the XOR swap method, everyday languages are becoming very high-level, and as a result taking away some of the fun.
In the next couple of posts I wish to implement some of the common place data-structures found in development, but unlike previous attempts, these will be in straight C.
The Exclusive disjunction (or) swap algorithm is a little trick to swap values of equal data type without the use of a temporary variable.
Typically, low-level data types like integers are used in practice, but in theory any value represented by fixed-length bit-strings will work.
Though bad practice in most use-cases, it does help to highlight implementation details which can seem foreign to higher-level programmers.
Due to the strong levels of abstraction put in place to help aid development of complicated systems we sometimes lose the beautify in working with the underlying bits and bytes.
An example of such an abstraction is the garbage collector found in the JVM, which takes care of memory management concerns which in other lower-level languages would be of huge consideration.
Radix sort is a O(digits·keys) sorting algorithm which relies on integer key grouping to successfully process and naturally order the specified data set.
Basing the sort on structure and positional notation, many other data types which can be represented in integer form (i.e. ASCII characters) can take advantage of the algorithm.
Sorting occurs by acting on the comparison between item digits in the same position.
Two alternative version of the algorithm exists, both tackling the problem from the opposite direction.
In this post I will be describing an iterative lowest significant digit implementation which as the name hints at, starts processing from the right most digit position.
This implementation results in a stable sort, where as the other implementation, tackles the most significant digit first and can not make such guarantees.
In a stable sorting algorithm the initial ordering of equal keys is left unchanged in the result.
Partial function application is a common place feature found in many languages that lean towards the functional paradigm.
Unlike some functional concepts (monads) it can be simply explained as taking a function and binding argument values to one or more of its parameters, resulting in a new function.
Function argument size in computer science circles is described as its arity, and through this process we are reducing the arity based on the partial application call.
Discussion of partial application typically brings up the related topic of currying, which follows the stricter rule of transforming a multiple argument function into a chain of single argument calls.
This is useful as it helps simplify the study of functions in theoretical computer sciences, such as lambda calculus.
Currying however is not that useful in general-purpose languages, dissimilar to Haskell which at its core only supports the mathematical notion of single argument functions.
Using a combination of syntactic sugar and currying, the language is able to give the misguided impression of multi-argument calls, when in-fact it is just a chain of single argument curried calls.