Mid - Sem 2 - Summary

Linked List

Linked List is a linear data structure, list of elements are stored randomly at a contagious memory location. Which the elements are accessible using pointers. Unlike array, data's are stored linearly or side by side in a memory and size of memory are limited.

A Linked List consist of node, we can insert data inside the node. The node also consist of a 'next' pointer which will point to the next node in the linked list. This next pointer are what connects the linked list together. We also have 'head' this is to mark the beginning or the first node. we can also use 'tail' to mark the last node. The last node will not point anything or pointer a 'NULL'. There are 2 ways of linked list, namely, single linked list and doubly linked list. In doubly linked list, the only different is that, they have a 'prev' pointer. This pointer is use to point the previous node in the linked list.

A linked list has a couple important function, push, insert after, append, delete and print.

Here is a simple single linked list program:

Here is a simple doubly linked list program:

Stack

A stack is the way of storing data by Last in First Out (LIFO). The last data will be the first one to remove. We can use stack in an array but using an array, the size are limited. So we use linked list. 

The easiest way to understand stack is when we stack our clothes in wardrobe. Lets say we have 3 clothes, clothe x, clothe y and clothe z, we first put clothe z, then clothe y above z, then clothe x above y. Making the clothe x the most top. When you want to use a clothe you will take out the most top, in this case clothe x. This is what stack means by Last in First Out.

Stack have 3 main function: push, pop, peek. push is inserting data, pop is removing data and peek is returning or take a look of the top data in the stack. We use also use top pointer to mark the most top in stack.

Here is a simple stack program:

Queue

A queue is the way of storing data by First in First Out (FIFO). The first data will be the first one to remove. Same we can use queue in an array but using an array, the size are limited. So we use linked list. 

Queue is like queuing in a drink shop for example, the first to be in line will be the first to be able to order.

Queue have 2 main function: in stack we use push and pop, but in queue we use enqueue and dequeue. We also use front and rear pointer. front pointer to make the first in the queue and rear pointer are the last in the queue, like head or tail in linked list.

Here is a simple queue program:

Hash Tables

Hash is a way of storing data at a fastest time complexity O(1). A good Hash function can find any data at a time complexity of O(1) but if there are lots of traversal happening it's worst time complexity is O(n). A hash function process the key of the data and convert it to a hashed key code that will points where our data is stored in the memory. It is widely use to be efficient in finding our data by just making one search to find the data at a O(1) time complexity. There are many hash function such as: mid-square, digit extraction, folding, division and rotating hash. Using has is all good and fast but, a problem will rise if 2 different data has a same hash key code. This are called collision, there are 2 ways to handle this problem: linear probing and chaining. Further explanation and examples can be seen on my blog entitled "Hash Tables and Binary Tree". Today we can see hash code using a combination of integers, characters and symbols.

Here is a simple hash program using simple hash function and chaining for collision:

Binary Search Tree

Binary search tree (BST) is a data structure that have a sub tree of a pointer 'left' and 'right' and they must not contain any duplicate. Principle of BST is having a root as for the first data to be inputted and it will branch out left and right pointer. Left and right pointer works like 'next' in linked list but for data to go left and right is determine by it's root. if the data is less than or smaller than root it will be place on the left sub-tree, and greater data will be place on the right sub-tree. 

Binary search tree has a time complexity of at least O(log n). Hash seems to beat Binary Search Tree in terms of time complexity. But there are time BST is more preferred due to its ability to get all keys in sorted order by just doing Inorder Traversal of BST. Which requires extra effort in Hash. BST use doesn't rely much on library and its operation will work on time complexity of O(log n) which beats Hash when there are lots to traverse and become to costly.

BST has 3 primary operation which are: insert, search and delete and 3 unique way of printing by: inorder, preorder, postorder. Unlike linked list or hash, operation in BST are mostly done recursively. 

Here is a simple BST program implementing the 3 primary function and printings: