Course Content
Java Data Structures
Java Data Structures
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
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
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
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 thedata
from the parameters of theappend()
method; - Next, we check if the list is empty, and if it is, we replace the first element of the list (
head
) withnewNode
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 theNode head
in this context; - Using a
while
loop, we iterate through the entire list untilcurrent.next
isnull
, 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
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 theNode head
; - Next, we set the condition for the while loop to
current != null
and print thedata
field on the screen; - For iterating through the list, we use the reference by reassigning
current
, which looks likecurrent = 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
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!
Thanks for your feedback!