Linked List Part 3: Deleting, Reversing, and Merging Additional List

In this section, we'll cover additional methods that enhance the functionality of the linked list. These methods include deleting nodes, reversing the order, and merging lists. Each of these operations introduces new ways to manipulate and manage the linked list. We'll also discuss the time and space complexity of each method.

  1. Deleting a Node at a Specific Index
  2. Reversing the Linked List
  3. Merging Two Linked Lists

1. Deleting a Node at a Specific Index

Method: deleteAtIndex(int index)

The deleteAtIndex method removes the node at a specified index from the linked list, provided the index is valid.

Implementation:

 
/*  Delete the indexth node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
       
        if( index < 0 || index >= this.size || this.head == null){
            throw new IndexOutOfBoundsException();
        }

        int count = 0;
        Node currentNode = this.head;
        Node prev = null;

        if(index == 0){
            this.head = this.head.next;
            if(this.head.next == null){
                this.tail = this.head;
            }
            this.size--;
            return;
        }

        while(currentNode != null){
           
            if(count == index && prev != null){
                prev.next = currentNode.next; //2 -> 1 -> 3
                currentNode = prev;
                if(currentNode.next == null){
                    this.tail = currentNode;
                }  
                break;
            }
           
            prev = currentNode;
            currentNode = currentNode.next;
            count++;  
        }

        this.size--;
    }

Time Complexity:

  • Best Case: O(1) if deleting the head node.
  • Average Case: O(n) due to traversal.
  • Worst Case: O(n) where n is the number of nodes in the list.

Space Complexity:

  • O(1): The method uses a constant amount of space regardless of the size of the list.

2. Reversing the Linked List

Method: reverse()

The reverse method reverses the order of the nodes in the linked list.

Implementation:


     /* Reverse order of the Linked list */
    public void reverse(){

        Node currentNode = this.head;
        Node prev = null;

        while(currentNode != null){
       
            Node temp = currentNode.next;
            currentNode.next = prev;
            prev = currentNode;
            currentNode = temp;

        }

        currentNode = this.tail;
        this.tail = this.head;
        this.head = currentNode;

    }

Time Complexity:

  • O(n): The method requires a single pass through the list to reverse it.

Space Complexity:

  • O(1): The method uses a constant amount of extra space regardless of the size of the list.

3. Merging Two Linked Lists

Method: merge(LinkedList list)

The merge method combines two linked lists into one.

Implementation:

public void merge (LinkedList list){

        if(list.getHead() == null){
            return;
        }

        if(this.head == null){
            this.head = list.getHead();
            this.size = list.size();
            return;
        }
       
        this.tail.next = list.getHead();
        this.size += list.size();
        this.tail = list.getTail();
       
    }

Time Complexity:

  • O(1): The merge operation is constant time when appending to the end of the list.

Space Complexity:

  • O(1): The method uses a constant amount of space regardless of the size of the lists being merged.

Space Complexity:

  • O(1): The method uses a constant amount of space, with k being handled by the helper function.

What is next?

Sorting the linked list using divide and conquer algorithm. 


Top Posts

Popular Methods for Machine Learning

Image
Machine Learning involves the programmatic training of applications to predict outcomes. Numerous algorithms and techniques are available for addressing prediction challenges in machine learning. In this discussion, we will explore three popular methods: Logistic Regression, Decision Tree, Random Forests, and Neural Networks. Logistic Regression Logistic Regression, a supervised machine learning algorithm, employs a binary classification approach, yielding a result based on two possible values while outputting only one, such as a Boolean (true or false). Despite its historical roots dating back to the 19th century, this method remains popular in machine learning. The resulting function displays an "S"-shaped graph, utilizing the logit function to constrain probabilities between 0 and 1. For instance, consider the scenario where we are trying to predict the likelihood of a person being approved for a mortgage based on their credit score and income. In the provided colored data...
Read more

Big Data Characteristics Explained

Image
Big Data is a hot topic in business, and it's not just a buzzword – it's a part of our daily lives everywhere. It goes beyond just having heaps of data; it includes how the data is structured, how fast we can process it, and, most importantly, what we can achieve with it. Two major factors driving the surge in data are improved computer capacity and increased data generation. Nowadays, our hard drives are not only bigger but also faster, allowing us to handle more data at lightning speed. This has led to a significant rise in data from various sources over the past decade. The value of Big Data for businesses today is immense, as it allows for improvements in various departments by recognizing common patterns, analyzing data, and delving into artificial intelligence and machine learning. Big data has four key characteristics, known as the 4 Vs: Volume: Receiving large amounts of data from various sources, often posing challenges when processed on personal compu...
Read more

Planning a Data Warehouse

Image
Setting up a data warehouse is a strategic move for businesses aiming to leverage historical data for informed decision-making. In this blog post, we'll dive into the essential planning phase, emphasizing the need for efficient data extraction, transformation, and loading processes to ensure optimal functionality. Let's explore the key steps to plan a data warehouse successfully. 1. Defining and Documenting Requirements for Data Warehouse During the planning phase, it's imperative to define and document requirements meticulously. This not only sets clear expectations for stakeholders but also facilitates seamless onboarding for new team members. The documentation should encompass various aspects, with a focus on the sources of data.  Key details include: Historical Data : Identify the duration of available historical data, spanning from months to years, providing valuable insights into the business's evolution. Data Sources : Specify diverse sources, such as websites, m...
Read more