Design Singly Linked List

Think we have to design Singly Linked List :

What should come into our mind ???????????

 Linked List will have value field and reference to next node field.

Structure Definition of a node in a Singly Linked List :

// Definition for singly Linked List 

public class SinglyListNode {

    int val;

    SinglyListNode next;

    SinglyListNode(int x){

         val = x;

      }

}

Initiate a new Linked List : Represent a linked list using the head node.

class MyLinkedList {

       private SinglyListNode head;

       public MyLinkedList(){

       head = null;

       }

}

Traverse the linked list to get element by index.

private SinglyListNode getNode(int index){

 SinglyListNode cur = head;

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

 cur = cur.next;

 }

return cur;

}

//Function to return last element of the List.

private SinglyListNode getTail(){

SinglyListNode cur = head;

while(cur !=null && cur.next !=null){

cur = cur.next;

}

return cur;

}

// Function to return value of index-th node in the linked list.

private int get(int index){

SinglyListNode cur = head;

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

cur = cur.next;

}

return cur == null ? -1 : cur.val;

}

// Function to add a new Node.

// Here adding the node before the first element.

public void addAtHead (int val){

SinglyListNode cur = new SinglyListNode(val);

cur.next = head;

head = cur;

return;

}

// Here adding a node to the last element of the linked list.

public void addAtTail(int val){
SinglyListNode cur = new SinglyListNode(val);
if(head == null){
cur.next = head;
head = cur;
return;
}

SinglyLinkedNode dummy = head;
while(dummy.next !=null){
dummy = dummy.next;
}
dummy.next = cur;
}


// Add at particular index and the val.

public void addAtIndex(int val , int index){

SinglyListNode cur = new SinglyListNode(val);
if(index == 0){
cur.next = head;
head = cur;
return;
}

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

SinglyListNode next = prev.next;
cur.next = next;
prev.next = cur;

}


Delete a Node :

public void deleteIntIndex(int index){

SinglyListNode cur = getNode(index);
if(cur == null){
return;
}

SinglyListNode prev = getNode(index-1);
SinglyListNode next = cur.next;

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

Singly Linked List - Introduction

Each node in a Singly Linked List contains a value and a  reference to link to the next node.

Linked list organizes all the nodes in a sequence.

Example of an Singly Linked List :

Here the nodes are linked together.


// Definition for Singly Linked List

public class SinglyListNode {
int val;
SinglyListNode next;
SinglyListNode (int x){
val = x;
}
}

In most cases we use the head node to represent the whole list.

Operations :

In LinkedList we can't retrieve the element in constant time like arrays .

If we want to fetch ith element we have to traverse from the head node one by one .

It takes O(N) on average to visit an element where N is the length of the linked list.

For Example in above singly Linked List if we want to retrieve the element '1' we need to traverse one by one till it reaches element '1' from head node 5 using "next" .

So we may rise a Question what is the use of List when we can access elements in O(1) time using arrays ? (In Retrieval Lists are bad in performance compared to Arrays).

Linked List are useful and benefitted in insertion and deletion .


Add Operation :
https://techyield.blogspot.com/2019/06/singly-linked-list-add-operation.html


Delete Operation :
https://techyield.blogspot.com/2019/06/singly-linked-list-delete-operation.html

Singly Linked List - Delete Operation

Example :


         3 --------> 4 -------------> 5 ------------> 6


                      prev                 cur                   next


Suppose we want to delete element '5' here . 

1. We need to traverse the linked list first until we reach prev node .

2.  So once we reach prev node then we need to point prev reference to next .


         Prev.next = cur.next;
       

           After that :


     3 -----------> 4 -------------> 6

That's how we delete an element.

Anyway it takes O(n) to traverse entire list and space complexity O(1).


Delete the First Node

1. In general entire LinkedList is represented with head node.

2. Just point head to head.next

   This is how you will delete the head node.

Singly Linked List - Add Operation

Inserting an element in Middle of the Linked List :

Consider :

            3 ---> 4 ---> 5 ---> 7

                     prev    next

 Suppose we want to insert an element with value 8 after 4 .

     1. Initialize a new node cur with given value 8.

                    cur.value =  8;

     2.  Link the cur next node to prev next node next.

                   cur.next = prev.next;

     3.  Link the prev next node to current node.

                   prev.next = current;

So here we no need to move all the elements like arrays.  So we can insert the element in List in O(1) time complexity. Which is very efficient.

Inserting an element at the Beginning :

    In list we use the head node to represent the entire list. 

    So we should update the head when representing the entire list.

   1. First create a new node current with the value.

   2. Second point current node next to head node.

  3.  Update the head node by pointing to current node.

Word Search - LeetCode

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Java Solution :

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || word == null)
            return true;
        for(int i =0 ; i < board.length; i++){
            for(int j=0; j < board[i].length ; j++){
                if(board[i][j] == word.charAt(0) && dfs(i,j,0,word,board))
                    return true;
            }
        }
        return false;
    }
    
    public boolean dfs(int i ,int j , int count , String word, char[][] board){
        
        if(count == word.length())
            return true;
        
        if(i<0 || j<0 || i >= board.length || j >= board[i].length || board[i][j] != word.charAt(count))
              return false;
        
        char temp = board[i][j];
        board[i][j] = ' ';
        boolean found = dfs(i+1,j,count+1,word,board) || dfs(i-1,j,count+1,word,board) || dfs(i,j+1,count+1,word,board) ||           dfs(i,j-1,count+1,word,board);
        board[i][j] = temp;
        
        return found;
    }
}

Word Search - LeetCode

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Java Solution :

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || word == null)
            return true;
        for(int i =0 ; i < board.length; i++){
            for(int j=0; j < board[i].length ; j++){
                if(board[i][j] == word.charAt(0) && dfs(board,i,j,0,word))
                    return true;
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board,int i , int j, int count,String word){
        if(count == word.length())
            return true;
        
        if(i<0 || i >=board.length || j<0 || j>= board[i].length || board[i][j] != word.charAt(count) ){
            return false;
        }
        
        char temp = board[i][j];
        board[i][j] = ' ';
        boolean found = dfs(board,i+1,j,count+1,word) || dfs(board,i-1,j,count+1,word) || dfs(board,i,j+1,count+1,word) || dfs(board,i,j-1,count+1,word);
        board[i][j]= temp;
        
        return found;
    }
}

Convert Sorted Array to Binary Search Tree - LeetCode

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Java Solution :

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null || nums.length==0)
            return null;
       
        return constructarraytobst(nums,0,nums.length-1);  
    }
    
    public TreeNode constructarraytobst(int[] nums , int left , int right){
        if(left > right)
          return null;
        
        int mid = left + (right-left)/2;
        TreeNode current = new TreeNode(nums[mid]);
        current.left = constructarraytobst(nums,left,mid-1);
        current.right = constructarraytobst(nums,mid+1,right);
        return current;
    }
}