Learning Summary of 2019-2020 even Semester (Dimitri 2301870016)


A link to the programming assignment : here!


Singly Linked List

Singly Linked List is a type of linked list in which each node has a link to the next one. The first node in a linked list is called a Head and is used as a point to find the rest of the linked list.

Doubly Linked List
Doubly linked list (DLL) is a type of linked list in which each node apart from storing its data has two links. The first link points to the previous node in the list and the second link points to the next node in the list. The first node of the list has its previous link pointing to NULL similarly the last node of the list has its next node pointing to NULL.


Advantages vs singly linked list

  1. A DLL can be traversed in both forward and backward direction.
  2. The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
  3. We can quickly insert a new node before a given node. In singly linked list, to delete a node, a pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using the “previous” pointer.


Disadvantages vs singly linked list
  1. Every node of DLL require extra space for a previous pointer
  2. All operations require the “previous” pointer to be maintained. This means with each operation, both the “next” pointer and the “previous” pointer need to be altered.

Node Insertion

 There are 4 ways a new node can be added to a DLL:

1. At the front of the DLL:

          In this method, the new node is always added before the head of the given linked list. This node then becomes the new head of the linked list, replacing the previous head as the first node.


2. At the end of a DLL:

         In this method, the new node is always added after the tail of the given linked list. Similar to the previous method, the new node becomes the new tail of the linked list, replacing the previous tail as the last node.


 3. After a given node

           In this method, we will be given a pointer to a node as ‘prev_node’. The new node will later be inserted after the given node in the linked list.


4. Before a given node
          
           In this method, we will also be given a pointer to a node as ‘next_node’. The code will check whether ‘next_code’ is NULL. If it is, the code returns as new nodes can not be added before a NULL. If it isn’t, the code inserts the new node before ‘next node’.



Circular Linked List

          Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end or the front. A circular linked list can be both singly circular linked or doubly circular linked.


            In a circular linked list, any node can act as a head as there is no real definition of a 'head' if all nodes are connected in the same way. The only way to define a 'head' when traversing a circular linked list is to stop when the first node visited is reached again (i.e. made a full rotation of the circular linked list 'circle').


Stack

In Data Structure, a stack is defined as a linear structure in which certain order of operations are performed.
The aforementioned operators will most likely include:
  •       Push: The addition of an item to a stack. If the stack is full, an Overflow condition is ruled        should you use the push operator on it.
  •     Pop: The removal of an item from a stack. If the stack is empty, an Underflow condition is        ruled should you use the pop operator on it.
  •       Peek/Top: Returning the top element of a stack.
  •       isEmpty: Checking whether or not a stack is empty.




In a stack, this order can either be LIFO (Last In First Out) or FILO (First In Last Out) because they are basically the same things. LIFO or FILO basically means that, in a list of items, the last one to be added will be taken out first. An example of this would be a stack of plates you have just washed and placed in a dryer. To put it back to the cupboard, you would use the LIFO method in which the latest washed plate gets taken first out of the stack.

Queue

Similar to a Stack, a Queue is also defined as a linear structure with a certain order of operations performed on them. The difference between a Stack and a Queue are the operations done to each of them and the order in which they are performed.
Operations in a queue usually include:
·           Enqueue: The addition of an item to a queue. Similar to a stack, an Overflow condition will be ruled if you use enqueue while said queue is full.
·           Dequeue: The removal of an item from a queue. Also similar to a stack, an Underflow condition will be ruled if dequeue is used with an empty queue.
·           Front: Returning the front (first) item from a queue.
·           Rear: Returning the last item from a queue.


The Above operators, although also done in a certain order, the order in which a queue is done is FIFO (First in First Out). Example of such a phenomena is, like its name, a real life queue in which the first in line will be served first followed by the second, third, and so on.

 Hash Table

Hash table is a data structure which stores data in an associative manner. Data is stored in an array format in a hash table, where each data has a unique index value. Thus, the insertion and search of a data can be done in a very short period of time, provided we know the index beforehand. These indexes can be found using a technique dubbed Hashing.

Hashing

 Hashing is a technique to convert certain key values from a data to a range of indexes for an array. There are many ways to hash, the simplest ones include taking the value of key then divide them by the number of available addresses, and take the remainder.



            The above code does exactly what the example did. However, one can clearly see a problem with it. If 2 keys result in the same hash, then the first hash will be replaced by the second and so on. This phenomena is called Collisions. Collision resolution can be done in 2 ways: Open Addressing and Closed Addressing

            In an open addressing technique, a hash collision will be resolved by probing, or searching through alternate indexes of the array until a free address is found. The most well-known probe sequence include: Linear Probing (probe interval is fixed – often set to 1), Quadratic Probing (probe interval increases quadratically), and Double Hashing (another hash is performed to determine the interval).

            In a closed addressing technique, instead of directly putting the hash result into an index in the array, it puts it into a linked list pointed by the index of the array. This way, collisions will be handled by adding a new node to a linked list and to look up the key, you only need to do a standard linked list traversal.



Binary Tree
            Binary Tree is a data structure in a form of a tree with only 2 branches/children. Since there are only 2 of them, they are typically called the left child and the right child depending on where the child is to its parent. The end of a branch in a binary tree is called a leaf A binary tree node only contains 3 parts: Data, a pointer to left child, and a pointer to right child.
            Common example of binary trees include:

1.    Full Binary Tree

A binary tree is called full only if all of its nodes have either 0 or 2 children. Binary trees with only 1 node or a node with only 1 child can not be called a full binary tree.

2.    Complete Binary Tree

A binary tree is completed only if all levels, with exception to the last possible, has its nodes completely filled. If the last level is not completely filled, the elements should be as left as possible.

3.    Perfect Binary Tree

A perfect binary tree is one in which all nodes have 2 children and all leaves are at the same level.

4.    Degenerate/Pathological Binary Tree

A tree where each parent node only has 1 child. Identical in behavior to a linked list.
Source:

- https://www.youtube.com/watch?v=KyUTuwz_b7Q
- https://en.wikipedia.org/wiki/Open_addressing
- https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/
- https://en.wikipedia.org/wiki/Binary_tree

Comments

Post a Comment

Popular posts from this blog

Image
Heaps A Heap is a special Tree-based data structure in which the tree is a complete binary tree. In general, heaps are classified as: Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree. Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree. Tries A Trie is a special data structure used to store a group of strings letter by letter in the form of a tree with a maximum of 26 children on each node. the 26 pointers to children nodes represent the 26 letters on the alphabet. This data structure is usually used to represent the "Re trie val" of data, hence the name, Trie. Strings are stored in a top to bottom manner on the basis of their prefix in a trie. All prefix...
Read more

Linked List

Image
Doubly Linked List Doubly linked list (DLL) is a type of linked list in which each node apart from storing its data has two links. The first link points to the previous node in the list and the second link points to the next node in the list. The first node of the list has its previous link pointing to NULL similarly the last node of the list has its next node pointing to NULL. Advantages vs singly linked list A DLL can be traversed in both forward and backward direction. The delete operation in DLL is more efficient if pointer to the node to be deleted is given. We can quickly insert a new node before a given node. In singly linked list, to delete a node, a pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using the “ previous ” pointer. Disadvantages vs singly linked list Every node of DLL require extra space for a previous pointer All operations require the “previous”...
Read more