Category: Code algorithm a day

I have observed and code several versions of linked lists and came with my own implementation of linked list. This linked list uses smart pointers and supports operations like insert after, insert before, reverse and print etc for the list.

#include <iostream>
#include <memory>

template <typename T>
struct Node{
  T value;
  bool head = false;
  std::shared_ptr<Node<T>> next;

  Node(): head(true), value(-1){}; // head with -1 value
  Node(T value): head(false), value(value){}; // node

  std::shared_ptr<Node<T>> add_next(T value){
  next = std::make_shared<Node<T>>(value);
  return next;
  }
};

template<typename T>
struct List{
  std::shared_ptr<Node<T>> head;
  std::shared_ptr<Node<T>> tail;

  List(){
   head = std::make_shared<Node<T>>();
   tail = head;
  }

  void add_node(T value){
    tail->add_next(value);
    tail = tail->next; 
  }

 void print(){
   std::cout << std::string(100, '-') << '\n';
   auto current = head;
   while(current != nullptr){
     std::cout << current->value << '\t';
     current = current->next;
   }
   std::cout << '\n' << std::string(100, '-') << '\n';
 }

void reverse(){
  auto current = head;
  std::shared_ptr<Node<T>> next, prev;
  while(current != nullptr){
    next = current->next;
    current->next = prev;
    prev = current;
    current = next;
   }
   head = prev;
 }

void insert_after(T after_value, T value){
  auto current = head;
  while(current != nullptr){
   if(current->value == after_value){
     auto temp_next = current->next;
     auto node = create_node(value);
     current->next = node;
     node->next = temp_next;
     break;
   }
   current = current->next;
  }
 }

void insert_before(T before_value, T value){
  auto current = head;
  std::shared_ptr<Node<T>> prev;
  while(current != nullptr){
   if(current->value == before_value){
     auto node = create_node(value);
     node->next = current;
     prev->next = node;
   }
   prev = current;
   current = current->next;
  }
 }

 std::shared_ptr<Node<T>> create_node(T value){
   return std::make_shared<Node<T>>(value); 
  }
};

int main(){
 List<int> l; // initialize the linked list

 for(int i = 1; i <= 10; i++){
   l.add_node(i);
 }
  l.print();
  l.reverse();
  l.print();
  l.reverse();
  l.insert_after(1, 2);
  l.print(); 
  l.insert_before(8, 18);
  l.print(); 
  return 0;
}

Output:

g++ --std=c++17 linked_list.cpp -g -o linked_list && ./linked_list
-----------------------------------------------------------------------------------------------------
-1 1 2 3 4 5 6 7 8 9 10
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10 9 8 7 6 5 4 3 2 1 -1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-1 1 2 2 3 4 5 6 7 8 9 10
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-1 1 2 2 3 4 5 6 7 18 8 9 10
----------------------------------------------------------------------------------------------------

The basic framework for divide and conquer algorithm can be used for any operations like reverse, checking if array is sorted etc. The possible implementation of reversing a string/vector is given as follows which takes O(n) time where n is size of collection string/vector.

template<class BidirIt>
void reverse(BidirIt first, BidirIt last)
{
 while ((first != last) && (first != --last)) {
 std::iter_swap(first++, last);
 }
}

Better algorithm for this can be given as follows:

#include <iostream>
#include <algorithm>
#include <string>

template <typename T>
void reverse_rotate(T first, T last){
 if((first == last) || std::next(first) == last) return;
 T middle = first;
 std::advance(middle, std::distance(first, last)/2);
 reverse_rotate(first, middle);
 reverse_rotate(middle, last);
 std::rotate(first, middle, last);
}

int main(){
 std::string s = "This is super cool";
 reverse_rotate(s.begin(), s.end());
 std::cout << s << '\n';
}

Checking if array is sorted is simple, compare consecutive elements to check if next element is greater than the previous element. This takes O(n) time. The possible implementation of std::is_sorted is given as follows:

template <class ForwardIterator>
 bool is_sorted (ForwardIterator first, ForwardIterator last)
{
 if (first==last) return true;
 ForwardIterator next = first;
 while (++next!=last) {
 if (*next<*first) // or, if (comp(*next,*first)) for version (2)
 return false;
 ++first;
 }
 return true;
}

Here I came with an algorithm which is like quick sort and uses O(log n) time. Here is the implementation.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

template <typename T>
bool check_sorted(T start, T finish, bool sorted = true){
 if(start == finish) return true;

if(std::next(start) == finish) return *start <= *finish;

T middle = start;
 std::advance(middle, std::distance(start, finish)/2);

sorted &= check_sorted(start, middle);
 sorted &= check_sorted(middle, finish-1);
 return sorted;
}

int main(){
 std::vector<int> v(20);
 std::iota(v.begin(), v.end(), 1);
 bool sorted = check_sorted(v.begin(), v.end());
 std::cout << "v is sorted? : " << sorted << '\n';

std::vector<int> v2 {20, 1, 3, 5, 2, 1, 4, 19, 18, 10};
 sorted = check_sorted(v2.begin(), v2.end());
 std::cout << "v2 is sorted?: " << sorted << '\n';

std::vector<int> v3 {1,1,1,1,1,1,1,1,1,1,1,1,1,1};
 sorted = check_sorted(v3.begin(), v3.end());
 std::cout << "v3 is sorted?: " << sorted << '\n';

std::vector<int> v4 {10,1,1,1,1,1,1,1,1,1,1,1,1,1};
 sorted = check_sorted(v4.begin(), v4.end());
 std::cout << "v4 is sorted?: " << sorted << '\n';
}

To remove duplicates of an array, use a hash map and array elements as keys, then extract keys. This requires extra space for storing the hash and time. Following algorithm does not need any extra space and time.

The algorithm is uses 3 iterators and moves the duplicate elements at the start of vector and erases the rest of vector. Pseudo code given as follows:

1. take iterator ​`​start` that points to beginning of vector.
2. take another iterator `i` that points to next element to start.
3. move  i to next index until elements are duplicate.
4. replace start with next element and increase start pointer.
5. at the end erase elements from start+1 to end from vector.

#include <iostream>  // std::cout 
#include <vector>   
#include <cstdlib>  // std::srand
#include <ctime>    // std::time

int main(){
 std::vector<int> v(100);
 std::srand(std::time(nullptr)); // use current time as seed for random generator
 
// generate 1000 random numbers between 0 to 99
 for(int i = 0; i < 1000; i++){
   int random_variable = std::rand()%100;
   v.push_back(random_variable);
   std::cout << random_variable << ' ';
 }

// sort
std::sort(v.begin(), v.end());


std::vector<int>::iterator start = v.begin();
std::vector<int>::iterator end = v.end();
auto i = start+1; // std::vector<int>::iterator i = start+1;
 while(i != end-1){
   if(*start == *i){
     i++;
   }else{
     start++;
     *start = *i;
   }
 }

v.erase(start+1, end);
 for(const auto & i:v) std::cout << i << ' ';
}