DSA Arrays, Bubble sort and linked list

Array

a data structure used to store multiple elements.

Bubble Sort

an algorithm that sorts an array from the lowest value to the highest value.

Bubble up

The word 'Bubble' comes from how this algorithm works, it makes the highest values '______’.

Linked list

consists of nodes with some sort of data, and a pointer, or link, to the next node.

Singly linked lists, Doubly liked lists and Circular linked lists

what are the three basic forms of linked lists

Singly linked list

the simplest kind of linked lists. It takes up less space in memory because each node has only one address to the next node

Doubly linked list

has nodes with addresses to both the previous and the next node, like in the image below, and therefore takes up more memory.

Circular linked list

its like a singly or doubly linked list with the first node, the "head", and the last node, the "tail", connected.

Singly linked list

Doubly linked list

Circular singly linked list

Circular doubly linked list

What are the basic implementation of linked list

Traversal

Remove a node

Insert a node

Sort

what are the basic things we can do with linked lists

Traversing

a linked list means to go through the linked list by following the links from one node to the next.

Inserting a node

a linked list is very similar to deleting a node, because in both cases we need to take care of the next pointers to make sure we do not break the linked list.

Linear search

linked lists works the same as for arrays. A list of unsorted values are traversed from the head node until the node with the specific value is found. Time complexity is O(n)

Binary search

not possible for linked lists because the algorithm is based on jumping directly to different array elements, and that is not possible with linked lists.

Tree data structure

similar to Linked Lists in that each node contains data and can be linked to other nodes.

Hierarchical Data

File systems, organizational models, etc.

Databases

Used for quick data retrieval.

Routing Tables

Used for routing data in network algorithms.

Sorting/Searching

Used for sorting data and searching for data.

Priority Queues

Priority queue data structures are commonly implemented using trees, such as binary heaps.

Binary Trees

Each node has up to two children, the left child node and the right child node. This structure is the foundation for more complex tree types like Binay Search Trees and AVL Trees.

Binary Search Trees

A type of Binary Tree where for each node, the left child node has a lower value, and the right child node has a higher value.

AVL Trees

A type of Binary Search Tree that self-balances so that for every node, the difference in height between the left and right subtrees is at most one. This balance is maintained through rotations when nodes are inserted or deleted.

Binary Tree

a type of tree data structure where each node can have a maximum of two child nodes, a left child node and a right child node.

Array

Linked lists

Binary trees

Benefits of Binary Trees over Arrays and Linked Lists:

• _____are fast when you want to access an element directly, like element number 700 in an array of 1000 elements for example. But inserting and deleting elements require other elements to shift in memory to make place for the new element, or to take the deleted elements place, and that is time consuming.

• ______ are fast when inserting or deleting nodes, no memory shifting needed, but to access an element inside the list, the list must be traversed, and that takes time.

• ______ such as Binary Search Trees and AVL Trees, are great compared to Arrays and Linked Lists because they are BOTH fast at accessing a node, AND fast when it comes to deleting or inserting a node, with no shifts in memory needed.

balanced binary tree

It has at most 1 in difference between its left and right subtree heights, for each node in the tree.

complete binary tree

It has all levels full of nodes, except the last level, which is can also be full, or filled from left to right.

full binary tree

its a kind of tree where each node has either 0 or 2 child nodes

Perfect binary tree

It has all leaf nodes on the same level, which means that all levels are full of nodes, and all internal nodes have two child nodes.

Breadth First Search

when the nodes on the same level are visited before going to the next level in the tree. This means that the tree is explored in a more sideways direction.

Depth First Search

is when the traversal moves down the tree all the way to the leaf nodes, exploring the tree branch by branch in a downwards direction.

pre-order

in-order

post-order

three different types of DFS traversals

Binary Search Tree

a Binary Tree where every node's left child has a lower value, and every node's right child has a higher value.

Binary Search Tree

a type of Binary Tree data structure, where the following properties must be true for any node "X" in the tree:

• The X node's left child and all of its descendants (children, children's children, and so on) have lower values than X's value.

• The right child, and all its descendants have higher values than X's value.

• Left and right subtrees must also be Binary Search Trees.

subtree

A ______starts with one of the nodes in the tree as a local root, and consists of that node and all its descendants.

descendants

The _________of a node are all the child nodes of that node, and all their child nodes, and so on.

node's in-order successor

A is the node that comes after it if we were to do in-order traversal.