Data Structure
----------------------------------------------------------------------
Data Structure is a collection of data values, and the functions or operations that can affect the data values stored within in different ways. The most basic, well-known application of Data Structure is an Array. Some of the more complex ones include Linked List, Stack, Queue, Hash Table, Binary Tree and Binary Search Tree. This article aims to review and summarize what each of them looks like.
Linked List
----------------------------------------------------------------------
A Linked List is a Data Structure based around 'Nodes', a struct-like object containing one or more data records and an address pointing to the next address of the next node. A Linked List has the first node be referred to as a Head, and its last node be referred to as a Tail. Incidentally, the next address of a Tail node contains NULL. In addition, a Linked List often has its own functions for inserting or deleting nodes.
Linked Lists has multiple variations, the most basic of them being Singly Linked List. A Singly Linked List contains only the most necessary functions of a Linked List and nothing else. The second variation is Doubly Linked List, where each node not only contains an address pointing to the next node, but also a node pointing to the previous node. The third one is Circular Linked List, where the next address of the Tail node doesn't point to NULL, but rather to the Head node. The final variation is the Circular Doubly Linked List, which combines the Doubly Linked List and Circular Linked List together. In this case, the previous address of the Head node will point to the Tail node.
Stack
----------------------------------------------------------------------
Stack is a linear data structure where the order of reading the data values may differ. The order is "First In Last Out", meaning that the data that got inserted earlier will be read last. There exists three main functions in a Stack; Push, Pop and Peek. Push is the operation to add a new item onto the stack, Pop is the operation to remove an item, while Peek is the operation to read the last or topmost data item. If a stack is full, it is said to be in an Overflow condition, but if it's empty, then it is in an Underflow condition.
Queue
----------------------------------------------------------------------
Queue is very similar to a Stack, except the order in reading data values is "First In First Out", where the data that got inserted earlier will also be read earlier. There exists four main functions in a Queue; Enqueue, Dequeue, Front and Rear. Enqueue and Dequeue are exactly like Push and Pop of Stack, while Front is an operation to read the first item, and Rear is an operation to read the last item. Like a Stack, if the Queue is full then it is in Overflow condition, and if it's empty then it is in Underflow condition.
Hash Table
----------------------------------------------------------------------
Hashing is an operation to map keys onto certain values for the purpose of making access more efficient. Hashing is carried out via Hash Functions, and the keys are stored onto Hash Tables. The keys for each type of Hashing differs depending on the type of Hash Function. Some of the more famous types include Mid-square, Division, Folding, Digit Extraction and Rotating Hash.
Mid-square is a Hash Function that squares the value, then takes the middle part of the squared value as its key. Division has the value undergo a Modulus function, then takes the resulting value as key. Folding has the value split into multiple different numbers, then add all the split numbers together to form the key. Digit Extraction selects specific digits from the original value, which is then combined together to become the key. Rotating Hash takes a key from a different Hash Function, then takes the rightmost digit of the key as the leftmost digit of the key.
In Hashing, there are incidents where two different values will share the same key. This is called a Collision. The two most well-known methods of Collision Handling are Chaining and Open Addressing. Chaining fixes collision by having the Hash Table in a Linked List format, while Open Addressing simply adds 1 to the key until a collision no longer occurs.
Tree
----------------------------------------------------------------------
A Tree is a hierarchical Data Structure type, allowing for faster and easier access. A tree has its data values stored within 'Nodes', and these nodes connected by Edges. A tree also has a Root, which describes the topmost Node of a Tree, a Child which is a Node that branches from another Node, a Leaf is a Node that doesn't have any child and a Forest is a set of disjointed trees. A Node also has Height/Depth and Degree. Height/Depth describes the number of edges towards/from the deepest leaf. The Height/Depth for a Root Node is also the Height/Depth for the Tree. Degree describes the number of branches in the Node.
Binary Tree
----------------------------------------------------------------------
Binary Tree is a Tree where each Node has a maximum of two Children. Each Node contains a data, a left pointer and a right pointer. In a Binary Tree, it is possible to count the maximum possible amount of Nodes at the level "l" with the formula 2l-1 and the maximum possible amount of Nodes at height "h" with 2h – 1.
There are multiple variations of a Binary Tree. These include Perfect Binary Tree, where every node except for the leaves has two children, Complete Binary Tree, where every level of the tree, except for maybe the last level, has the maximum amount of Nodes. Skewed Binary Tree, where every Node has at maximum one child, and Balanced Binary Tree, where none of the leaves are shorter or further than any other leaves from the root.
Binary Search Tree
----------------------------------------------------------------------
A Binary Search Tree is a variation of Binary Tree, being essentially a sorted version of Binary Tree. A Binary Search Tree has these following properties;- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree.
A Binary Search Tree has a search time of 0(log(n)). A Binary Search Tree has the advantages of having quick searching, insertion and deletion due to being sorted. A Binary Search Tree, similar to Linked Lists, has their own functions for search, insert, and delete operations.
References:
https://www.geeksforgeeks.org/data-structures/linked-list/
https://www.programiz.com/dsa/linked-list
https://www.geeksforgeeks.org/stack-data-structure/
https://www.geeksforgeeks.org/queue-data-structure/
https://www.geeksforgeeks.org/hashing-data-structure/
https://www.geeksforgeeks.org/mid-square-hashing/
https://www.baeldung.com/folding-hashing-technique
http://blog4preps.blogspot.com/2011/07/hashing-methods.html
https://eternallyconfuzzled.com/hashing-c-introduction-to-hashing
https://www.programiz.com/dsa/trees
https://www.geeksforgeeks.org/binary-tree-data-structure/
https://www.geeksforgeeks.org/threaded-binary-tree/
https://www.geeksforgeeks.org/binary-search-tree-data-structure/
https://www.programiz.com/dsa/binary-search-tree
