Hash Table Introduction

Hash Table is a data structure which organizes the data using hash functions in order to support quick insertion and search.


We have two different types of hash tables :

1. HashSet

2. HashMap

-> HashSet is one of the implementation of Set Data Structure with no repeated values.

-> HashMap is one of the implementation of Map Data Structure to store (Key , Value ) pairs.

By using proper hash function the hash table can achieve wonderful performance in both insertion and search.


Principle Behind the Hash Table :

Hash Table is a data structure which supports quick insertion and search using hash functions.

The Key idea of the hash function is to map keys to buckets .

1. When we insert a new key the hash function will decide which bucket the key should be assigned and the key will be inserted into the corresponding bucket.

2. When we want to search for a key , the hash table  will use the same hash function to find the corresponding bucket and search only in the specified bucket.



For Example consider Y = X % 5 is our hash function .


Consider the elements ->  3 . 5 . 6  7  10


All the elements will go through the hash function and will get mapped to the corresponding buckets.

Insertion :

So . 3 will be assigned to bucket with index 3.

       5 . will be assigned to bucket with index 0.

      6   will be assigned to bucket with index 1.
   
      7 will be assigned to bucket with index 2.
 
     10 will be assigned to bucket with index 0.

Search:

We parse the elements through the same hash function and search in the specified bucket.

 If we want to search 23 we will search in bucket 3 as 23%5 is 3.

If we want to search 34 we will search in bucket 4 as 34%5 is 4.

Summary Of LinkedList

Review of SinglyLinkedList and DoublyLinkedList :

1. Both of them not able to access the data at random position in constant time.

2. Both of them are able to add a node at the beginning of the list or add a node after a given node in O(1) time.

3. Both of them are able to delete first node in O(1) time.

But it is little different in deleting the given node (Including the last node).

-> In a singly linked list , it is not able to get the previous node in constant time , we have to spend O(N) time to find out the previous node before deleting the given node.

-> In a doubly linked list , it is much easier because we delete a node using the prev reference field in O(1) time.


Time comparison

Conclusion :

If you want to delete or add a node in a linked list will be the better choice.

If you want to access an element in an array in constant time then array will be best.

Design Doubly Linked List - Solution

// Definition of Doubly Linked List

class DoublyListNode {
int val;
DoublyListNode prev, next;
DoublyListNode(int x){
val = x;
}
}

// Initiate a new Linked List

class MyLinkedList {

private DoublyListNode head;

public MyLinkedList(){
head = null;
}
}

// Traversing the Linked List to get element by index.

private DoublyListNode getNode(int index){
DoublyListNode cur = head;

for(int i=0 ; i < index && cur != null ; i++){
cur = cur.next;
}
return cur;
}


// Function to return last Node of the linked list

private DoublyLinkedList getTail(){

DoublyListNode cur = head;

while(cur !=null && cur.next !=null){
cur = cur.next;
}
return cur;
}


// To fetch the value of the index-th node in the linked list

private int get(int index){

DoublyListNode cur = getNode(index);
return cur == null ? -1 : cur.val;
}


// Add a new Node

// Add a Node if the DoublyListNode is null and add at Head.
public void addAtHead(int val){
DoublyListNode cur = new DoublyListNode(val);
cur.next = head;
if(head != null){
head.prev = cur;
}
head = cur;
return;
}

// Add a Node at Tail 

public void addAtTail (int val){
DoublyListNode prev = getTail();
DoublyListNode cur = new DoublyListNode(val);
if(head == null){
addAtHead(cur);
return;
}
prev.next = cur;
cur.prev = prev;
}

// public void addAtIndex (int index , int val){
if(index == 0){
addAtHead(val);
return;
}

DoublyListNode prev = getNode(index-1);
if(prev == null){
return;
}

DoublyListNode cur = new DoublyListNode(val);
DoublyListNode next = prev.next;

cur.prev = prev;
cur.next = next;
prev.next = cur;
if(next !=null)
next.prev = cur;
}

}

Similar to the SinglyLinkedList it takes O(N) time to get a node by index. where N is the length of the linked list.


// Delete a Node

public void deleteAtIndex (int index){

DoublyListNode cur = get(index);
DoublyListNode prev = cur.prev;
DoublyListNode next = cur.next;

if(cur == null)
return;

if(prev != null){
prev.next = next;
} else {
head = next;
}

if(next != null){
next.prev = prev;
}

}

Introduction To Doubly Linked List

In previous article we learned about SinglyLinkedList.

https://techyield.blogspot.com/2019/06/singly-linked-list-introduction.html

Here we are going to discuss about DoublyLinkedList.

In SinglyLinkedList we have a value field and a reference field to the next node.

In DoublyLinkedList we have one extra field called prev node which points to the prev node. With this field we are able to know the previous node of the current node.


Node Structure :

class DoublyListNode {

int val;
DoublyListNode prev , next;

DoublyListNode(int x){
val = x;
}

}

The entire list is represented with the head node as in SinglyLinkedList.


Operations :

Add Operation :

If we want to insert cur after an existing node prev  .

We can add in two steps :

1. Link cur with prev and next , where next is the original next node of prev.

2. Re link the prev and next with cur.

Similar to the singly Linked List the space and time complexity is O(1).

Delete Operation :

If we want to delete an existing node cur from the doubly linked list we can simply link its prev node prev with the next node next.

Unlike the singly linked list it is easy to get the prev field in constant time O(1).

Here the space and time complexity both are O(1).

Tips For Linked List Problems

1 . Always go through some test cases or examples before you implement a problem using Linked List.

2. Always feel free to use several pointers at the same time.

3. In most of the cases you need to keep track of the previous node for the current node.

Reverse Linked List - LeetCode

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)
            return null;
        
        ListNode curHead = head;
        while(head.next != null){
            ListNode p = head.next;
            head.next = p.next;
            p.next = curHead;
            curHead = p;
        }
        return curHead;
    }
}

Remove Linked List Elements - LeetCode

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode helper = new ListNode(0);
        ListNode p = helper;
        helper.next = head;
        
        while(p.next !=null){
            if(p.next.val == val){
                p.next = p.next.next;
            }else{
                p = p.next;
            }
        }
        return helper.next;
    }
}