Implementing our LinkedList

It's time to challenge yourself with some truly complex tasks. In this chapter, we will implement our simplified data structure - specifically, the SinglyLinkedList.

Let's start by implementing the Node class, which will store a value and a reference to the next Node.

Node


              123456789
            
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

In the previous chapter, I already demonstrated the implementation of the Node class in SinglyLinkedList, so we won't dwell on it for long.

Next, let's create the SinglyLinkedList class, where we will define all the logic for our data structure:

SinglyLinkedList


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

We created the Node head field, which will store the first element of our data structure. In a regular LinkedList, there is also a head and tail that store the first and last elements of the data structure. Since the data structure should be empty during initialization, we initialize this field as null in the constructor.

We need our data structure to have all CRUD operations.

Create

So, let's go step by step and write a method to add an element to the end of the list, representing the Create operation:

SinglyLinkedList


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }
}

Above, you can see the implementation of the method to add an element to the end of the list. Let's break down how this method works:

We create an object of the Node class, newNode, and initialize it through the constructor, passing the data from the parameters of the append() method;
Next, we check if the list is empty, and if it is, we replace the first element of the list (head) with newNode by reassignment;
Then, we add a return statement to exit the method;
If the list is not empty, in this method, we create a new object, current, which represents the Node head in this context;
Using a while loop, we iterate through the entire list until current.next is null, meaning until we determine that the next element in the list is empty;
Once we find the last non-null element in the list, we set its link to newNode, thereby adding the element to our list.

In other words, the goal of the append method was to set the link of the last element to the new element. This way, we add a new element to the list.

Read

Let's move on; now we need to implement the Read operation.

SinglyLinkedList


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

Read operation is quite simple. We need to iterate through each element of the list and print them on the screen. In our case, we also use the placeholder current, which we initialize with the Node head;
Next, we set the condition for the while loop to current != null and print the data field on the screen;
For iterating through the list, we use the reference by reassigning current, which looks like current = current.next;;
We do this until the Node current becomes empty. After this, we exit the loop and move on to the next line.

By the way, think about how to replace this while loop with a do-while loop. Can it be done at all?

Update

Now, let's move on to the update method, which is more interesting in its implementation:

SinglyLinkedList


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

Note

In this method, we use the size method, which you will implement yourself in the next chapter. So, for now, it's important to understand that this method returns the length of the list.

First, we check if this index is in our list using an if statement. If not, we print the message "Invalid index" and end the method. This is done to avoid errors.

If the index is within the bounds of our list, we proceed with the familiar algorithm. First, we create an object of the Node class called current, which we initialize as the head.

Instead of using a while loop, we use a for loop, which is more suitable here since we know the exact number of iterations we need. The number of iterations is equal to the value of the index parameter.

Our loop looks like this:
for (int i = 0; i < index; i++). In this loop, we find the desired element using the familiar operation: current = current.next.

Once we've found the desired element, we assign its data attribute a new value, performing the operation
current.data = newData. We take newData from the parameters of this method.

It looks quite simple, doesn't it? I leave it to you as a self-task to implement two methods in this class: the delete method and the size method. I'm confident you'll handle this task. See you in the next chapter!

Все було зрозуміло?

Дякуємо за ваш відгук!

Секція 1. Розділ 6