Circular Singly Linked List

-
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:-
  1. Node- It is an actual container that holds data along with the reference of the next node.
  2. Head Node- It is the starting node of a linked list, if somehow it's lost then the complete linked list will be lost.
  3. 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 data and reference to the next node.
#2 Create a Custom Circular Singly Linked List-O(1)
public class CustomCircularSinglyLinkedList<T> {
    Node<T> head, tail;
    int size = 0;
}
We need to initialize an empty reference of the head and tail variables of the Node class. Whenever we do any kind of manipulation in the linked list, we will update the head and tail reference based on the condition. We are using a size variable to get 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 && tail == null) {
        node.next = node;
        head = node;
        tail = head;
    } else {
        node.next= tail.next;
        tail.next = node;
        tail = tail.next;
    }
}
In the code above, we are initially creating a new linked list element using node class. We need to identify whether the linked list is empty or containing some elements. If the linked list is empty then we assign the reference of the newly created node to head and tail and tail's next will hold the reference of itself. If the linked list is containing some element then newly node's next will hold the reference of the tail's next and update tail's next will hold the new node then assign tail to tail's next which is a new node. So, every time tail's next is actually pointing to the head node only and the number of element increments by 1 and set it to the size variable.
#4 Adding node at the beginning-O(1)
/**
 * Insertion element at the first position
 * Time/Space Complexity - O(1)
 * @param value
 */
public void addFirst(T value) {
    Node<T> node = new Node<>(value);
    size++;
    if (head == null && tail == null) {
        node.next = node;
        head = node;
        tail = head;
    } else {
        node.next = head;
        head = node;
        tail.next = head;
    }
}
In the code above, we are checking the base condition and increment by 1 the size variable. If the linked list is containing an element then the new node's next will hold the reference of head and will update head to new node and tail's next will update to head.
#5 Adding node at desire index-O(n)
/**
 * Insertion node at the particular index.
 * Time Complexity - O(n)
 * Space Complexity - O(1)
 * @param index
 * @param value
 */
public void addElementAtDesireIndex(int index, T value) {
    if (index >= 0 && index <= size) {
        Node<T> node = new Node<>(value);
        if ((head == null && tail == null) || index == 0) {
            addFirst(value);
            return;
        } else {
            int count = 0;
            Node ref = head;
            while (count++ < index-1) {
                ref = ref.next;
            }
            Node tempRef = ref.next;
            ref.next = node;
            ref.next.next = tempRef;
            if (ref == tail)
                tail = ref.next;
        }
        size++;
    } else
        throw new ArrayIndexOutOfBoundsException(index);
}
In the code above, we are checking the base condition and index value shouldn't exceed the linked list size. We have to iterate the given index - 1 then hold the reference of index-1 node's next to some temporary node. We have to update the index-1 node's next to the new node and then update the new node's next to the temporary node.
Suppose we have 5 elements in the linked list 1->2->3->4->5 and the last node is pointing to the first element. We have to add an element 7 in the 1st index and the rest of the element will shift 1 position to the right. So we will iterate till index-1 position which is 0th in this case. Our current node value is 1 and will store the current node's next to some temporary storage. We will update the current node's next to the new node then it will become 1->7  and the temporary variable is holding 2->3->4->5. We will update the current node's next's next which is the new node's next to the temporary variable. After then our linked list will look like 1->7->2->3->4->5 and added into the specific position. If the given index is out of range then it will throw an exception.
#6 Printing node's element - O(n)
/**
 * We have to be very careful while looping in circular singly linked list.
 * We have check the condition ref node shouldn't be equal to head.
 * TimeComplexity - O(n) & SpaceComplexity - O(1)
 */
public void printMe() {
    if (head == null)
        return;
    Node ref = head;
    do {
        System.out.println(ref.data);
        ref = ref.next;
    } while (ref != head);
}
#7 Searching element - O(n) 
/**
 * We have to be very careful while looping in circular singly linked list.
 * We have check the condition ref node shouldn't be equal to head.
 * TimeComplexity - O(n) & SpaceComplexity - O(1)
 * @param value
 * @return
 */
public boolean contains(T value) {
    if (head == null)
        return false;
    Node ref = head;
    do {
        if (ref.data == value)
            return true;
        ref = ref.next;
    } while (ref != head);
    return false;
}
#8 Remove node from beginning - O(1)
/**
 * Removing element from the beginning
 * Time complexity - O(1)
 */
public void remove() {
    if (size > 0) {
        if (size == 1)
            head = tail = null;
        else {
            head = head.next;
            tail.next = head;
        }
        size--;
    }else
        throw new ArrayIndexOutOfBoundsException();
}
#9 Remove node from last- O(n) 
/**
 * Removing element from the last
 * Time complexity - O(n)
 */
public void removeLast() {
    if (size > 0) {
        if (size == 1)
            head = tail = null;
        else {
            Node ref = head;
            while (ref.next != tail)
                ref = ref.next;
            ref.next = head;
        }
        size--;
    } else
        throw new ArrayIndexOutOfBoundsException();
}
#10 Remove node from desire location -O(n)
/**
 * Removing element from desire location
 * Time complexity - O(n) & Space Complexity - O(1)
 */
public void removeElementAtDesiredLocation(int index) {
    if (index >= 0  && index < size) {
        if (index == 0) {
            remove();
            return;
        } else {
            int count = 0;
            Node ref = head;
            while (count++ < index-1) {
                ref = ref.next;
            }
            ref.next = ref.next.next;
            if (index == size -1) {
                tail = ref;
            }
            size--;
        }
    } else
        throw new ArrayIndexOutOfBoundsException(index);
}
#11 Clear All Linked List - O(1)
public void clear(){
    head = tail = null;
    size = 0;
}
Location: Delhi, India

Comments

Post a Comment

Popular posts from this blog

Recursion

-
Image
The process in which a function calls itself and only works where we call the same operation multiple times with different inputs. In every call, we try to make the problem smaller. There must be a base case where the system will stop the recursion and give you a result back. It internally stores the recursion state in the method call stack. If there is no base condition in the recursion method then it will go into an infinite loop and you might face the StackOverflow Exception . There are several types of recursion:- Head Recursion Tail Recursion Tree Recursion Nested Recursion Head Recursion It will call recursively first then at the end do all the computation. private static int factorial( int number) { return (number== 1 )? number : number* factorial (number- 1 ) ; } factorial(5) (5* factorial(5-1)) (5* (4* factorial(4-1)) (5* (4* (3*factorial(3-1))) (5* (4* (3* (2*factorial(2-1)))) (5* (4* (3* (2* (1*1))))) output = 120 Tail Recur...
Read more

Stack

-
Image
The Stack  looks more like a container which holds the element, will insert element from the top and remove from the top only. It follows the Last in First out(LIFO)  or First In Last out (FILO)  approach. Java uses the method stack area to hold the state of the method if some method calls another method inside it.   public class Demo { public static void main(String[] args) { new Demo().firstCall(); System. out .println( "Main" ); } public void firstCall() { secondCall(); System. out .println( "First" ); } private void secondCall() { thirdCall(); System. out .println( "Second" ); } private void thirdCall() { System. out .println( "Third" ); } } This is how it maintains the method call in the method stack area. It will remove from the top every time and complete its method execution and remove next's top from the stack. This process will continue until th...
Read more

Data Structure & Algorithm

-
Image
I am going to start the complete data structure and algorithm blog series to help the developer community understand the basics and help them become more productive in their work environment. As we all are under lockdown until the next update from the government, I have decided to support my friends and colleague to understand the data structure and algorithm. Let's begin by separating the data structure and algorithm in two terms. When you hear about data structure,  what comes first to your mind. I believe most of you thought of storing any form of data in an efficient way. Yes, You are correct 👍. Now, Second and the most important term is an algorithm , It is a set of rules to be followed to solve a problem. To gain more understanding of the data structure and algorithm, let us take an example:- E.g., We are all going to attend the google conference and they have a single registration desk. If we all reach the registration counter together, to register ourselves. Such a ...
Read more