Data Structures and Algorithms in Dart

This is a repository inspired by Data Structures & Algorithms in Java by Robert Lafore.

There you can find all code-example rewritten on Dart and all solved tasks

Table of Contents

01. Arrays.

• low_array - very simple example with arrays.
• high_array - rewritten low_array.dart using more OOP way. Describes LinerSearch in Arrays.
• ordered_array - Describes BinarySearch in sorted Arrays.
• class_data - Using Arrays with Object.

02. Simple Sorting.

• bubble_sort - Bubble Sort Example
• select_sort
• insert_sort
• object_sort - Object sort example using insert sort and Lexicographical Comparisons

03. Stacks and Queues.

• stack
  • stack - simple stack with array of integer
  • reverse - reversing a word eq: artem -> metra
  • brackets - Delimiter Matching - a program that checks the delimiters in a line of text typed by the user eq: a{b(c]d}e -> Error ] at 5
• queue - simple queue.
• priority_queue
• infix - Convert Infix to Postfix eq A+B*C -> ABC*+
• postfix - Evaluate Postfix Expressions eq 57+ -> Evaluates to 12

04. Linked Lists.

• linked_list
  • simple_linked_list - simple linked list implemintation with deleteFirst and insertFirst methods
  • linked_list - adding delete and find methods.
• first_last_list - linked list with link to first and last object
• link_stack - Stack implementation using linked list
• link_queue - Queue implementation using first_last_list
• sorted_list - sorted linked list
• list_insertion_sort - insertion sort array using linked list
• double_linked_list - linked list where each element contain next and previous link
• list_iterator - implementation linked list with iterator

05. Recursion.

• triangle - simple example of recursion - calculate triangle number. E.g Triangle number 3 -> 6 (1, 3, 6, 10, 15, 21...)
• anagram - simple program, which can do anagrams. E.g Input: cat Output:

  1  c a t
  2  c t a
  3  a t c
  4  a c t
  5  t c a
  6  t a c
  

• binary_search - binary search implemented with recursion (binary search see 01_array/ordered_array)
• towers - Tower of Hanoi algorithms using recursion
• merge - very simple implementation merge 2 pre-sorted arrays.
• merge_sort - Merge sorting array
• stack_triangle - calculate triangle number with recursion and stack
• stack_triangle2 - calculate triangle number using stack instead of recension
• power - X power Y using optimizing recursion method

06. Sorting.

• shell_sorting - sorting used Shell's Method
• partion
• quick_sort1 - Quick sort based on last element of array
• quick_sort2 - QuickSort based on median

07. Binary Tree.

• binary-tree - Binary Search tree

                                50
              25                              75
      12              37              --              87
  --      --      30      43      --      --      --      93
--  --  --  --  --  33  --  --  --  --  --  --  --  --  --  97

08. Red-Black Tree.

Unfortunately there no code.

09. Tree 2 3 4.

• tree_2_3_4 - Tree 2 3 4

Enter first letter of show, insert, find: s
Level = 0 child = 0 /50
Level = 1 child = 0 /30/40
Level = 1 child = 1 /60/70

10. Hash.

• hash - simple hash

Enter size of hash table: 10
Enter initial number of items: 8
Enter first leter of show, insert, delete, find: 
s
HashTable: 120 151 150 193 173 118 ** ** 148 99 
Enter first leter of show, insert, delete, find: 
i
Enter key value to insert: 100
Enter first leter of show, insert, delete, find: 
s
HashTable: 120 151 150 193 173 118 100 ** 148 99 
Enter first leter of show, insert, delete, find: 

• hash_double - Double Hash. It use two hashFunction:
  • hashFunc - for find first index;
  • secondHashFunc - for find the step (offset);

Enter size of hash table: 10
Enter initial number of items: 4
Enter first leter of show, insert, delete, find: 
s
HashTable: ** 121 ** ** ** ** 196 137 138 ** 
Enter first leter of show, insert, delete, find: 
i
Enter key value to insert: 100
Enter first leter of show, insert, delete, find: 
s
HashTable: 100 121 ** ** ** ** 196 137 138 ** 

• hash_chain - Chain method which use SortedLinkedList

Enter size of hash table: 5
Enter initial number of items: 5
Enter first leter of show, insert, delete, find
s
0. List (first -> last):
1. List (first -> last): 56 86
2. List (first -> last): 12
3. List (first -> last): 13 48
4. List (first -> last):
Enter first leter of show, insert, delete, find

11. Heap.

• heap - heap implementation

Enter first letter of show, insert, remove, change:
s
Heap Array: 100 90 80 30 60 50 70 20 10 40
........................................................
                                100
                90                              80
        30              60              50              70
    20      10      40
 ........................................................

• heap_sort - heap sorting - O(N*logN)

Enter number of items: 10
Random Array: 58 42 87 29 14 53 39 79 9 64
Heap: 87 79 58 42 64 53 39 29 9 14
........................................................
                                87
                79                              58
        42              64              53              39
    29      9      14
 ........................................................
Sorted: 9 14 29 39 42 53 58 64 79 87

12 Graph.

• dfs - Depth-first search

Visits: ABCDE

• bfs - Breadth-first search

Visits: ABDCE

• mst - Minimum spanning tree

Minimum spanning tree: AB BC CD DE 

• topo - Topology sorting

Topologically sorted order: BAEDGCFH

13. Weighted Graph.

• mstw- Minimum Spanning Tree with Weighted Graphs

Minimum spanning tree: AD AB BE EC CF 

• path - Find Shortest Path (Dijkstra's algorithm)

Shortest Path: 
A = inf(A) B = 50(A) C = 100(D) D = 80(A) E = 140(C) 

How to Run Code?

• Be sure you have installed dart
• Open folder with project
• Run into you terminal dart path/to/file.dart e.q dart chap_02/low_array.dart

What IDE have support dart language?

I prefer use JetBrains

But you can use VsCode + DartCode Plugin

How to test tasks?

All tasks have a unit test, which located in 0N_name/tasks/test.

So you need:

• copy and past that test to your project
• change path to you solution
• run pub run test path/to_test.dart

Contributing

If you want to contribute or you find a issue/mistake feel free to create an issue and pull-request

TODO:

• Add tests for implementations
• Add task for each data structure
• Add test for each task