DS4Fun

Now, We have a good understanding of the Linked list and its internal working of it. In a Doubly linked list, we have next and previous pointer but the head's previous and tail's next are null. If we reach the end of the linked list then it will terminate. This might be a drawback in some of the use cases, to overcome this situation we will use the circular doubly linked list. Suppose, We have sent data into the network, data is divided into the packet and each packet has its own ordered unique identification number. If the packet is coming late then it will search the position by traversing forward and backward and placed the packet in an accurate position. This could be one of the real-time examples of using the Circular Doubly linked list. NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it  as an  Object. #1 Custom Doubly Linked List Class class Node< T > { T data ; Node< T > next ; No...

Given N size node in the Singly Linked list and you have to find the kth node's value from the end.  Suppose, You have been provided the above Singly Linked List and the interviewer asks you to return 2nd last element from the linked list. Your response will be 7 and if the kth element is greater than the size of the Linked list then return -1. -1 will represent that the kth element is not present. This problem is repeatedly asked by many of the product based companies and the interviewer will grill you on it. He will add some constraint on the fly and asks you to solve it optimize way. Suppose, If we are going to solve this problem what would be the solution that comes into our mind. A Singly linked list holds the count of the node in the size variable, We will iterate from the head node to size - kth node and return the kth node's value. Once you give this solution to the interviewer, he/she will directly tell you that there is no size variable available in this custom Singl...

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below. Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list. Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] Output: [1,2,3,7,8,11,12,9,10,4,5,6] Explanation: The multilevel linked list in the input is as follows: After flattening the multilevel linked list it becomes: We have already covered the Doubly Linked List in our previous  blog.  If you look into the above problem then you will realize that the Doubly linked list class contains three references (next, previous, and child). It is clear in the flatten Doubly Linked list whenever a child exists, It fi...

A Doubly Linked list looks like a similar to Singly Linked list but there is one extra pointer that holds the previous node information also. It holds the information of the previous as well as the next node. It gives us the flexibility to iterate backward and forward direction. Let moving forward and implement a doubly linked list. NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it  as an  Object. #1 Custom Doubly Linked List Class class Node< T > { T data ; Node< T > next ; Node< T > previous ; public Node() { } public Node( T data) { this . data = data; } public Node( T data, Node< T > next, Node< T > previous) { this . data = data; this . next = next; this . previous = previous; } } The below diagram will really helpful whenever you are going to create a doubly linked list on your own. You can easily gue...

As we have already covered the singly linked list in our previous blog . Now, It's the right time to discuss the circular singly linked list which is nothing but our tail node is pointing to the head node. Here we are using a few buzz words like:- Node- It is an actual container that holds data along with the reference of the next node. Head Node- It is the starting node of a linked list, if somehow it's lost then the complete linked list will be lost. Tail Node- It represents the linked list last node. Now, let us understand the implementation of the circular singly linked list with the help of code. NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it  as an  Object. #1 Create a Custom Linked List  class Node< T > { T data ; Node next ; public Node( T data) { this . data = data; } } It's our generic implementation of a class, which can hold any type of ...

Let's do the implementation and understand the singly linked list in a deep-dive. NOTE: - Generic <T> type can accept any data type, If you have not passed explicitly then it will consider it  as an  Object. #1 Create a Custom Node class Node< T > { T data ; Node next ; public Node( T data) { this . data = data; } } It is our generic custom linked list implementation, which holds the value of any type and the address of the next node. #2 Create Custom Singly Linked List-O(1) public class CustomLinkedList< T > { Node< T > head , tail ; int size = 0 ; } Here, we will store the start and last address reference along with the number of elements in the Linked List. #3 Adding Node at the end-O(1) /** * Inserting element at the last position * Time/Space Complexity - O(1) * @param value */ public void add( T value) { Node< T > node = new Node<>(value); size ++; if ( head == null ) { ...