In this post I will implement one of the most fundamental data structure in computer science – linked list. Linked list – is a dynamic sequence of linked nodes where each node composed of a datum and a reference to the next node. Lists, stacks, queues and many other data types can be implemented using linked list. There are several types of linked lists:

• singly linked list
• doubly linked list
• circular linked list

In this post I will implement the most frequent type – singly linked list. Let’s start with the definition of node:

Usually linked list has following functions:

• isEmpty() – to check whether the list is empty or not
• length() – to get the number of nodes in the list
• find() – to find existing node by value
• addAfter(), addBefore() – to add new node after / before the specified node

• remove() – to remove existing node In more advance cases linked list can also have functions:

• addFirst(), addLast() - to add new node at given position
• removeFirst(), removeLast() - to remove existing node at given position
• reverse() – to reverse existing nodes
• copy() – to create deep copy of the existing list
• merge() – to merge given list with the current one

Instead of the specific functions addFirst(), addLast(), removeFirst() and removeLast() I will implement more generic addFromStart(), addFromEnd(), removeFromStart() and removeFromEnd(), where one can specify the exact position a node has to be added or removed. Also it’s worth mentioning, that my implementation heavily relies on a notion of a dummy (or sentinel) node.

In this post I will implement basic algorithm to raise floating point number (also known as base) to integer power (also known as exponent). In academic world this process usually referred as Exponentiation. The most naïve implementation is based on the definition of x^y, i.e. repetitive y-time multiplication of x.

Complexity: O(n).

This implementation can be optimized by using following exponentiation properties:

• b^m = b · b^m-1
• b^m+n = b^m · bⁿ
• b^m·n = (b^m)ⁿ In other words, given 2⁷ we can calculate the result as follows:

2⁷ = 2 · 2⁶ = 2 · 2²⁺⁴ = 2 · 2² · 2⁴ = 2 · 2² · 2^2·2 = 2 · 2² · (2²)²

As you can see, instead of 7 iterations now we have only 3.

Complexity: O(log n).

In this post I will implement basic algorithm to detect whether a given number is a prime. In more academic terms – check a number for primality. According to Wikipedia - a prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Naïve implementation will test whether n is a multiple of any number between 2 and n-1. Slightly more optimized version will minimize the test range up-to √n (i.e. between 2 and √n). In this post I’ll use test range between 2 and ⌊n/2⌋ due to the fact calculation of √n itself is more complex than single right shift operation.

Complexity: O(n/2) or just O(n).