Implementing a Doubly Linked List in C
Following on from the discussion on implementing a singly linked list in C, a logical follow-up data structure is the doubly linked list.
Implementing a Singly Linked-List in C
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 commonplace data structures found in development, but unlike previous attempts, these will be in straight C.
Experimenting with the XOR Swap Method in Java
The exclusive disjunction (or XOR) swap algorithm is a little trick to swap values of the same 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 it is considered bad practice in most use cases, it does help to highlight implementation details which can seem foreign to higher-level programmers. Due to the high levels of abstraction implemented to aid the development of complex systems, we sometimes lose the beauty of working with the underlying bits and bytes. An example of such an abstraction is the garbage collector found in the JVM, which handles memory management concerns that, in lower-level languages, would require significant attention.
Least Significant Digit (LSD) Radix Sort in Java
Radix sort is an O(digits·keys) sorting algorithm that relies on grouping integer keys to efficiently process and naturally order the specified dataset. Based on structure and positional notation, many other data types that can be represented in integer form (e.g. ASCII characters) can benefit from the algorithm. Sorting occurs by comparing digits in the same position of the items. Two alternative versions of the algorithm exist, each tackling the problem from the opposite direction. In this post, I will describe an iterative least significant digit implementation which, as the name suggests, begins processing from the right-most digit position. This implementation results in a stable sort, whereas the other implementation, which tackles the most significant digit first, cannot guarantee stability. In a stable sorting algorithm, the initial ordering of equal keys remains unchanged in the result.
Using Partial Application in PHP
Partial function application is a commonplace 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 science, such as lambda calculus. Currying, however, is not that useful in general-purpose languages, unlike 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.