Linked List Part 2: Implementation in Java

Overview of the Linked List Implementation

We will be using Java to implement a linked list. To achieve this, we need to create two classes: one to manage the linked list itself, including operations on the list, and another to handle the nodes (elements) within the list. Below, we provide a detailed explanation of each component of the linked list implementation.

Node Class

Each Node in the linked list contains the following components:

  • data: The value stored in the node. In our implementation, we use the integer data type, but it can be replaced with any other data type as needed.
  • next: A reference to the next node in the list, which allows traversal from one node to the next.

LinkedList Class

This class defines a singly linked list where each node contains a value and a reference to the next node in the sequence.

Fields

  • private Node head; : This is a reference to the first node in the linked list. It is null if the list is empty.
  • private Node tail; : This is a reference to the last node in the linked list. It is null if the list is empty. If size is one, head and tail will be the same.
  • private int size; : This integer keeps track of the number of nodes in the list.

Constructor

  • LinkedList(): Initializes an empty linked list with head and tail set to null, and size set to 0.

Methods

  • public int size(): Returns the current number of nodes in the linked list.
  • public Boolean isEmpty(): Returns true if the list is empty (i.e., size is 0), otherwise returns false.
  • public int get(int index): Retrieves the value of the node at the specified index.
    • Throws an IndexOutOfBoundsException if the index is out of bounds or if the list is empty.
    • Traverses the list to find the node at the given index and returns its data.
  • public Node getTail(): Returns the tail node of the list.
  • public Node getHead(): Returns the head node of the list.
  • public int[] toArray(): Converts the linked list to an array of integers.
    • Creates an integer array of size size.
    • Iterates through the linked list, copying each node's data into the array.
    • Returns the array.
  • public void addAtHead(int val): Adds a new node with the given value to the beginning of the list.
    • Creates a new node with the value val.
    • Sets the new node's next reference to the current head.
    • Updates head to point to the new node.
    • Increments size by 1.
    • Updates tail if the list was previously empty (i.e., head.next was null).
  • public void addAtTail(int val): Appends a new node with the given value to the end of the list.
    • Creates a new node with the value val.
    • If the list is empty, sets head to the new node.
    • Otherwise, sets the next reference of the current tail to the new node.
    • Updates tail to the new node.
    • Increments size by 1.
  • public void addAtIndex(int index, int val): Inserts a new node with the given value at the specified index.
    • Adds the node at the head if index is 0.
    • Adds the node at the tail if index is equal to size.
    • Throws an IndexOutOfBoundsException if the index is out of bounds.
    • Otherwise, traverses the list to find the node just before the specified index and inserts the new node at that position.
    • Increments size by 1.

Code:

```java

public class LinkedList{

    private Node head;
    private Node tail;
    private int size;

     /* Initiate empty LinkedList */
    LinkedList(){
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

     /* Return the size of this linked list */
    public int size (){
        return this.size;
    }

     /* Check if the linked list is empty */
     public Boolean isEmpty (){
        return (this.size == 0);
    }

    /* Get the value of the indexth node in the linked list. */
    public int get(int index) {

        if(index >= size || index < 0 || this.head == null){
            throw new IndexOutOfBoundsException();
        }

        Node currentHead = head;

        for(int i = 0; i < index; i++){
            currentHead = currentHead.next;
        }

        return currentHead.data;
       
    }


    /* Retreive value in the tail */
    public Node getTail() {
        return this.tail;
    }

    public Node getHead(){
        return this.head;
    }

    /* Convert linked list to an array  */
    public int[] toArray(){
       
        int[] arr = new int[this.size];

        Node currentNode = this.head;
        int index = 0;

        while(currentNode != null){
            arr[index] = currentNode.data;
            currentNode = currentNode.next;
            index++;
        }

        return arr;
    }

    /*  Add a node of value val before the first element of the linked list */
    public void addAtHead(int val){

        Node newNode = new Node(val);
        newNode.next = this.head;
        this.head = newNode;
        this.size++; //increament size

        //update tail
        if(this.head.next == null){
            this.tail = this.head;
        }

    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val){

        Node newNode = new Node (val);
        if(this.head == null){
            this.head = newNode;
        }else{
            this.tail.next = newNode;
        }
       
        this.tail = newNode;
        this.size++;

    }

    /** Append a node of value val to a given index of the linked list. */
    public void addAtIndex(int index, int val){

        if(this.size > 0 && index == 0){
            this.addAtHead(val);
            return;
        }

        if(this.size == index){
            this.addAtTail(val);
            return;
        }
       
        if(index > size || index < 0){
            throw new IndexOutOfBoundsException();
        }
       
        Node newNode = new Node (val);
        Node currentNode = this.head;
        Node prev = this.head;
        currentNode = currentNode.next;
        int count = 1;

        while(currentNode != null){

            if(count == index){
                newNode.next = currentNode;
                prev.next = newNode;
                break;

            }
            prev = currentNode;
            currentNode = currentNode.next;
            count++;
        }

        this.size++;

    }
}

What is next?

Additional operations that you can do with linked list: Deleting a Node at a Specific Index, Reversing the Linked List, and Merging Two Linked Lists. 


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