\documentclass[10pt,a4paper]{article}

% Packages
\usepackage{fancyhdr}           % For header and footer
\usepackage{multicol}           % Allows multicols in tables
\usepackage{tabularx}           % Intelligent column widths
\usepackage{tabulary}           % Used in header and footer
\usepackage{hhline}             % Border under tables
\usepackage{graphicx}           % For images
\usepackage{xcolor}             % For hex colours
%\usepackage[utf8x]{inputenc}    % For unicode character support
\usepackage[T1]{fontenc}        % Without this we get weird character replacements
\usepackage{colortbl}           % For coloured tables
\usepackage{setspace}           % For line height
\usepackage{lastpage}           % Needed for total page number
\usepackage{seqsplit}           % Splits long words.
%\usepackage{opensans}          % Can't make this work so far. Shame. Would be lovely.
\usepackage[normalem]{ulem}     % For underlining links
% Most of the following are not required for the majority
% of cheat sheets but are needed for some symbol support.
\usepackage{amsmath}            % Symbols
\usepackage{MnSymbol}           % Symbols
\usepackage{wasysym}            % Symbols
%\usepackage[english,german,french,spanish,italian]{babel}              % Languages

% Document Info
\author{Meliodas}
\pdfinfo{
  /Title (algorithms-and-datastructures-java.pdf)
  /Creator (Cheatography)
  /Author (Meliodas)
  /Subject (algorithms and datastructures java Cheat Sheet)
}

% Lengths and widths
\addtolength{\textwidth}{6cm}
\addtolength{\textheight}{-1cm}
\addtolength{\hoffset}{-3cm}
\addtolength{\voffset}{-2cm}
\setlength{\tabcolsep}{0.2cm} % Space between columns
\setlength{\headsep}{-12pt} % Reduce space between header and content
\setlength{\headheight}{85pt} % If less, LaTeX automatically increases it
\renewcommand{\footrulewidth}{0pt} % Remove footer line
\renewcommand{\headrulewidth}{0pt} % Remove header line
\renewcommand{\seqinsert}{\ifmmode\allowbreak\else\-\fi} % Hyphens in seqsplit
% This two commands together give roughly
% the right line height in the tables
\renewcommand{\arraystretch}{1.3}
\onehalfspacing

% Commands
\newcommand{\SetRowColor}[1]{\noalign{\gdef\RowColorName{#1}}\rowcolor{\RowColorName}} % Shortcut for row colour
\newcommand{\mymulticolumn}[3]{\multicolumn{#1}{>{\columncolor{\RowColorName}}#2}{#3}} % For coloured multi-cols
\newcolumntype{x}[1]{>{\raggedright}p{#1}} % New column types for ragged-right paragraph columns
\newcommand{\tn}{\tabularnewline} % Required as custom column type in use

% Font and Colours
\definecolor{HeadBackground}{HTML}{333333}
\definecolor{FootBackground}{HTML}{666666}
\definecolor{TextColor}{HTML}{333333}
\definecolor{DarkBackground}{HTML}{A3A3A3}
\definecolor{LightBackground}{HTML}{F3F3F3}
\renewcommand{\familydefault}{\sfdefault}
\color{TextColor}

% Header and Footer
\pagestyle{fancy}
\fancyhead{} % Set header to blank
\fancyfoot{} % Set footer to blank
\fancyhead[L]{
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{C}
    \SetRowColor{DarkBackground}
    \vspace{-7pt}
    {\parbox{\dimexpr\textwidth-2\fboxsep\relax}{\noindent
        \hspace*{-6pt}\includegraphics[width=5.8cm]{/web/www.cheatography.com/public/images/cheatography_logo.pdf}}
    }
\end{tabulary}
\columnbreak
\begin{tabulary}{11cm}{L}
    \vspace{-2pt}\large{\bf{\textcolor{DarkBackground}{\textrm{algorithms and datastructures java Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{Meliodas} via \textcolor{DarkBackground}{\uline{cheatography.com/61459/cs/15877/}}}
\end{tabulary}
\end{multicols}}

\fancyfoot[L]{ \footnotesize
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{LL}
  \SetRowColor{FootBackground}
  \mymulticolumn{2}{p{5.377cm}}{\bf\textcolor{white}{Cheatographer}}  \\
  \vspace{-2pt}Meliodas \\
  \uline{cheatography.com/meliodas} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Not Yet Published.\\
   Updated 23rd May, 2018.\\
   Page {\thepage} of \pageref{LastPage}.
\end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Sponsor}}  \\
  \SetRowColor{white}
  \vspace{-5pt}
  %\includegraphics[width=48px,height=48px]{dave.jpeg}
  Measure your website readability!\\
  www.readability-score.com
\end{tabulary}
\end{multicols}}




\begin{document}
\raggedright
\raggedcolumns

% Set font size to small. Switch to any value
% from this page to resize cheat sheet text:
% www.emerson.emory.edu/services/latex/latex_169.html
\footnotesize % Small font.

\begin{multicols*}{2}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{DATASTRUCTURES}}}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{Linked List}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{DEFINATION: A linked list is a data structure composed of a group of nodes, each node linking to the next node in the sequence. Each node consist of two elements, \#.data storing the contents of the node and \#.next a reference to the next node. \newline ADDING:(To add data from a LL:) \newline To add a new node with data to t startof LL:   \newline 1. Create a new node containing data  \newline 2. Point the .next of the new node to the current first node  \newline 3. Point the start of the list to the new node \newline REMOVING: (To remove data from a LL:) \newline 1. If the first node \#.data is equal to data: \newline      a. Point the start of the list to the node after the first node \newline 2. Otherwise: \newline     a. Find a node {\emph{prev just before a node with \#.data equal to data \newline     b. Point }}prev.next to *prev.next.next skipping the node being removed} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{ARRAY}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{Definition- Stores data elements based on an sequential, most commonly 0 based,index.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{Stack (abstract data type) {\bf{LIFO}}}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{A stack is a abstract collection data type where the primary operations are {\bf{push}} which adds an element and {\bf{pop}} which removes. It is a Last-In-First-Out (LIFO) data structure, the last element pushed must be the first one popped. \newline {\bf{Array Based}} \newline An array implementation uses an simple array and items are added and removed from the end of the array. In a language without dynamic arrays, the stack would keep track of the number of items and the available space, when the stack runs out of space the array would be reallocated to provide more space. In Javas the {\bf{array}}data structure is dynamically resized and the stack implementation is very simple. Arrays in Java provide native push and pop functions, for this visualisation these are reimplemented. \newline {\bf{Linked List Based}}   \newline The Linked List based implementation is also simple. A {\bf{push}} adds a new node onto the front of a list, and pop removes the front of the list.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{Queue (abstract data type)}} FIFO}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{A queue is a abstract collection data type where the primary operations are enqueue which adds an element and dequeue which removes. It is a First-In-First-Out (FIFO) data structure, the first element pushed must be the first one removed. \newline {\bf{Linked List Based}} \newline The {\emph{Linked List based implementation works by keeping a pointer to the start and end of the list. Dequeueing removes the first element of the list, much like the linked list }}stack, enqueueing utilises the pointer to the end of the list to add an item at the end of the list in constant time. \newline {\bf{Array Based}} \newline The array based implementation works by keeping a two arrays {\bf{left}} and {\bf{right}}. Dequeue is O(1) even though it includes a O(n) reverse operation. This is because the reverse happens at a 1/n frequency.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{Hash table}}}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{A hash table is a data structure that maps keys to values. The keys are distributed across a number of buckets by hashing the key to produce a bucket index. \newline A good hash function produces an even distribution across all the buckets so that no bucket is overloaded. \newline Even with a good hash function collisions happen, where two keys are hashed to the same slot. Therefore most hash tables have some collision resolution strategy to handle this case. \newline {\bf{Separate chaining}} \newline In separate chaining (also called open hashing or closed addressing) each bucket has its own list of entries. A good hash table only has very few items in each bucket, and so data structures like a linked list are popular. \newline This example is hash set, as it only stores {\bf{a key}}. However all the main logic is the same, a hash table stores {\bf{a (key, value)}} pair instead of just a key, but all the hashing and equality checks are still performed on the key.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{SEARCHING}}}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{LinearSearch}} {\emph{(sequential search) }}}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{Linear search (sequential search) is the most simple approach to find out, whether the array (or a different data structure) contains some element. The principle of linear search is trivial – iterate over all elements stored in the structure and compare them with the searched one. In the worst case – the last element is equal to the searched one or the structure does not contain the element at all – linear search has to perform n comparisons, hence the asymptotic complexity of the algorithm is O(n).} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{Binary search}} {\emph{(half-interval search)}}}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{A binary search algorithm finds the {\bf{position/index}} of inp {\bf{input element}} in a sorted array. With each iteration it halves the number of items to check. \newline // {\bf{searches the sorted array myArray}} for {\bf{an item inp}} \newline // {\bf{returns the {\emph{index}} of {\emph{inp}} or -1 if not found}}} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{SORTING}} Comparison sorting}}  \tn
\SetRowColor{white}
\mymulticolumn{1}{x{8.4cm}}{} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{Bubble sort}}}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Description}}  \newline In every step it compares two adjacent elements and if the lower value is on the left side of the higher, bubble sort swaps them (lighter value ascends to the end of the array) and with the same logic algorithm proceeds to the next item. \newline After one iteration the lowest value is located at the end of the array. Algorithm now repeats the procedure with reduced array (the last element is already sorted). After n-1 iterations is the array completely sorted, because the last bubble is sorted trivially.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{Insertion sort}}}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Description}} \newline 1.One element is sorted trivially \newline 2. Pick element next to the already sorted sequence and insert it to the correct place - move every element of the already sorted sequence, which has a higher value than the element being sorted, one place right, than put the element into the gap (correct place within the sequence). \newline 3. While array contains any unsorted elements GOTO: 2.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{Selection sort}}}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{The algorithm sorts the list building the sorted section front to back. Each pass through the list finds the minimum element in the unsorted range and swaps the element so that it is at the end of the sorted portion of the list.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{Bucket sort}} (Other sorting)}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an {\emph{array}} into a number of {\bf{buckets}}. Each bucket is then sorted individually, either using a different {\emph{sorting algorithm}}, or by {\bf{recursively applying}} the bucket sorting algorithm.  \newline {\emph{Bucket sort works as follows:}} \newline  a. Set up an array of initially empty "buckets". \newline  b. Scatter: Go over the original array, putting each object in its bucket. \newline  c. Sort each non-empty bucket. \newline  d. Gather: Visit the buckets in order and put all elements back into the original array.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{RADIX SORT}}}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{{\bf{Description}}  \newline The fundamental principle of radix sort stems from the definition of the stable sort – sorting algorithm is stable, if it maintains the order of keys, which are equal. \newline Radix sort iteratively orders all the strings by their n-th character – in the first iteration, the strings are ordered by their last character. In the second run, the strings are ordered in respect to their penultimate character. And because the sort is stable, the strings, which have the same penultimate character, are still sorted in accordance to their last characters. After n-th run the strings are sorted in respect to all character positions.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{TREES}}}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{A binary search tree is a binary tree data structure where each node is greater than all the nodes in its left sub-tree and smaller than all the nodes in its right sub-tree. Each child is another binary search tree. \newline  \newline The shape of a binary search tree depends on the order of insertions and it can be degenerate. More complex data structures like AVL-trees or red-black trees are self balancing binary search trees and ensure that the shape does not become degenerate leading to worst case run times. \newline  \newline Binary search trees have very fast insertion and deletion when balanced, and the code is a lot simpler than other self balancing binary search trees.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{8.4cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{8.4cm}}{\bf\textcolor{white}{{\bf{HEAP SORT}}}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{8.4cm}}{Heapsort is based on usage of the {\bf{binary heap – data structure}} which acts as a  {\bf{priority queue.}} If we insert all elements of the array into the priority queue, the operation poll will always return (and remove) the element of the heap, which has the highest priority. If we use poll operation n times, we will obtain list of sorted elements. \newline  \newline {\bf{The heapsort algorithm consists of these steps:}} \newline 1.Build the heap using all elements of the array. \newline 2.Poll the highest element of the heap. \newline 3.Swap it with the last element of the heap (in array). \newline 4.Reduce the heap size by 1 (elements at the end of the heap are already sorted). \newline 5.Repair the heap (move element swapped in 3 to its correct place in the structure). \newline 6.If there are any elements remaining in the heap {\bf{GOTO: 2}}. \newline 7.Array is sorted according to the priority of the elements in reverse order.} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


% That's all folks
\end{multicols*}

\end{document}