Summary

-


Linked List

Linked lists can be thought of as dynamic arrays which means that the size does not need to be specified and can keep growing as long as we still have memory in our RAM.

 A linked list consist of a node, which is just like a single block of memory in an array, and in the node we can store data. The node also consist of a 'next' pointer which points to the next node in the linked list. The next pointers are essentially what connects the linked list together. In a doubly linked list, we have an extra 'prev' pointer which points to the previous node in the linked list. We also need a head pointer which points to the first node of the linked list. We can also use a tail pointer which points to the last node of the linked list, but this is optional.

 A linked list contains of several operations such as, push head, push tail, insert after, delete, print and many more. Here is a program which contains several of those operations:

Stack

A stack is the a way of storing data with the principle of First In Last Out. This means that the last data which gets in the stack will be the first one the get removed. Stacks have 3 main operations which are: push, pop, and peek. Push is the same as inserting data while pop is removing data. Peek is return the top data in the stack. We can implement the principle of stacks both using arrays and linked list. If we use arrays, our stack size is limited. If we use linked list, we do not have a limit in the size of the stack we will use memory due to the presence of pointers.

A program that implement stacks using Arrays:



A program that implement stacks using Linked List:



 We can use stacks for converting infix to postfix notation or prefix notation, and also evaluating prefix and postfix notations. Stacks are also used for Depth First Search algorithms.

Queue

Queue is similar to stacks but only with a different principle: First In First Out. So the first data that enters the queue will be the first one to be removed. Instead of push and pop, queues' operations is called enqueue and dequeue. We can also implement queues in arrays and linked list.

A program that implement queues using Arrays:



A program that implement queues using Linked List:



 Queues can be used for Breadth First Search algorithms.

Hash Tables

Hash tables is a way to store and search data with a very fast time complexity. If we have a very good hash function, we can get a search time complexity close to O(1). A hash function processes the key of the data from the input and turn it into a hashed key which points to the index in the hash table array. This way, if we want to search for the data, we use the same hash function to output the same hashed key index and immediately find the data in O(1). There are many hash functions such as: mid-square, division, folding, digit extraction and rotating hash. However, a problem arises when there is collision or when 2 different data has the same hashed key from the hash function. There are 2 ways to handle collision: linear probing and chaining. Linear probing will basically place the item with the same hashed key in the next empty slot in the hash table array. Chaining is a much better collision handler which uses linked list. If there an item with the same hash key, just point the old item to the new item with the same hashed key, creating a linked list. Therefore, chaining will require us to use an array of linked list.

Here is a program which implements hash table, a simple hash function, and chaining:



Binary Search Tree

Binary Search Tree is a data structure which has an average search complexity of O(log n). This average time complexity is usually very accurate unlike hash tables which can diverge greatly from O(1) to O(n). The principle of binary tree is: every element smaller than the current node of the tree goes to the left subtree, whereas elements greater will go the right subtree. BST uses the concept of linked list but instead of a 'next' pointer, we have a 'left' and right' pointer.  BST has 3 main operations which are: insert, delete, search. Printing a binary search tree can be done in preorder, postorder, or in order. Operations of BST is mostly done recursively, that is why most functions have a struct Node* return type.

 This is a program which implements the primary functions of BST:





Comments

Post a Comment

Popular posts from this blog

Hash Tables and Trees

-
Image
Hash Tables and Hashing Hashing Hashing is a technique used to store and allocate data (in a hash table array for example) by obtaining a key from the inputted data and processing it to its respective index. This hashing process through a Hash Function which has many different forms and each will spit out different results even from one key. For example, we may have a series of string such as "apple", "dog" and "cat" and we want to place this is an array of strings. Sure, we can just insert them using a For-loop and the resulting array will be : { "apple", "dog","cat"}.  Now assume we have hundreds of different strings and we one to search for the string "cat" in the array. We now have to do a linear search through the array which has the time complexity of O(n). This wouldn't be an effective method of storing and searching data if we have a large amount of data stored. A way to make the time...
Read more

AVL TREES & B-TREES

-
Image
AVL TREE DEFINITION AVL trees is a self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes. To ensure that this property is fulfilled, each node will have a variable called the balance factor  which is calculated by (height of left subtree - height of right subtree). The node is said to be balanced  if and only if the balance factor is = {-1,0,1}. With this condition, the property of the AVL tree will be fulfilled. BENEFITS The obvious benefit of an AVL tree when compared with a BST is the worst case time complexity of a search in an AVL tree is O(log n) compared to the O(n) worst case time complexity of a BST. This is simply because an AVL tree will always have the height of O(log n) due to its property. BALANCING What happens if we insert a new node or delete a current node (NOTE: insertion and deletion follows the same algorithm as BST's, but is only added with the balancing a...
Read more

Binary Search Tree

-
Image
Binary Search Tree Theory Why do we use BST (Binary Search Tree) for storing data? Well, BST allows for faster searching and sorting, insertion and deletion of data. This can happen because of the fundemental rules of Binary Search Trees, which are:  For every node in a BST, the left subtree of the node must contain elements which are smaller than the element stored in the node. For every node in a BST. the right subtree of the node must contain elements which are greater than the element stored in the node Therefore, traversing through a binary search will just be a matter of asking the question of greater or smaller.  Basic BST Operations Search This search algorithm will return a struct Node* datatype, this is just something that we need to keep in mind when applying this algorithm in our main function Insert Delete This deletion operation requires some sort of visualisation to fully understand, especially on line 28. Howev...
Read more