Summary on Linked List, Hashing & BST

1. Single Linked List

A. Push Head

-Create a new node, name it newNode points to the newly created node.

-Link the newly created node with the head node, the newNode will now point to head node.

-Make the newNode as the head node, now head node will point to newNode.

B. Push Mid

-Create a new node.

-Traverse to the n-1th position of the linked list (Example: If we have 5 datas we will travel to the 4th node) and connect the new node with the n+1th node. (Example: We have 5 datas and we want to insert a data in between the 4th and the 5th data, so we will connect the data to both of them). Means the new node should also point to the same node that the n-1th node is pointing to. (newNode->next = temp->nextwhere temp is the n-1th node).

C. Push Tail

-Create a new node and make sure that the address part of the new node points to NULL. (Because we are inserting in the end we have to make sure that we point it to NULL because the last data's address is always NULL.

-Traverse to the last node of the linked list and connect the last node of the list with the new node, last node will now point to new node. (Connect the last node with the node we want to input in the end.) Example: If we have 5 datas and want to add a 6th data in the end we should connect the 5th and the 6th data and make sure the 5th data stores the address of the 6th data.)

2. Doubly Linked List

In Doubly Linked List each node apart from storing data has two links/two connection. 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 and the last node of the list has its next node pointing to NULL.

With just one pointer, we can look at the current node, the next node, and the previous node at the same time with just one variable of pointer used. At the same time it takes extra memory for pointer for the previous node. In Singly Linked List we just need 8 bytes but in Doubly Linked List here we are using 12 bytes.

3. Circular Single Linked List

In Singly Linked List we start from the first node. If we are in any node in the middle we cannot go back to the previous node from the node you are at. In Circular Single Linked List if we point the NULL to the first node we can make it happen.

4. Circular Doubly Linked List

This is similar with the previous one, the last node is connected with the first node and the first node is also connected with the last node.

5. What is Hashing?

- Hashing is the process of mapping large amount of data item to smaller table with the help of hashing function for faster access of elements. The efficiency of mapping depends of

the efficiency of the hash function used.

Example above, if we want to find Ada, Ada is at the 8th index and we can say that myData = Array[8]; but that's only possible if we know the exact position of Ada in the array. Well, what if we don't?

Using ASCII we get:

- Mia – M (77) i(105) a(97), 77+105+97=279, 279%11=4

We added all the ASCII value we got and then found the remainder by dividing it with the total amount of data. We do that for all the data we have in our list and we put them into their respective indexes. It will look like this:

Index Number = The sum of the ASCII codes % Size of Array

6. Binary Search Tree

-Binary Search Tree is a binary tree in which for each node, value of all the nodes in left subtree is lesser and value of all the nodes in right subtree is greater.

As we can see the root holds the value 15 and the left subtree has a value lesser than 15 (10, 8, 12), the right subtree has a value greater than 15(20, 17, 25). It goes same for the left side of 10 it is 8, it's lesser and the right side value is 12. So we call this a perfect Binary Search Tree.