Implementing Singly Linked Lists in Java
12/10/2020#java #algorithms #tutorial #programming
Linked lists are really important data structures, they let us store values in different parts of the memory and find them by their addresses. Today in this article I'm gonna go on how to implement a Singly Linked List in java.
lets create our first java file SinglyLinkedList.java
Inside lets start by making a class that will represent the Node
1package singlyLinkedList; 2 3class Node { 4 //thats the value(data) that is inside the Node 5 public int data; 6 //Thats the pointer inside the Node, every Node 7 //has a pointer that store the address of the next node 8 //Here we call this pointers "next" 9 public Node next; 10 11 public void displayNodeData() { 12 System.out.print( data + " -> "); 13 } 14 15}
This class will represent the Node, every Node in a liked list stores a value, represent by our public int data in code, and a pointer to the next Node that will be represented by our public Node next in our code. Inside this class we made a method that will just print the data so that in the end we can see our results.
Okay now inside our class SinglyLinkedList we are gonna start by defining a Node that represents the start of our list, a head node.
1public class SinglyLinkedList { 2 //Its private because we only need to reference head 3 //inside this class 4 private Node head; //here head == null
IMPORTANT: head = null even if we don't write it explicitly, java does that for us.
We are gonna use head in our methods to reference the beginning of our list (aka our first node) and for iterations, we will see this now.
Our first method is gonna be a simple insert,We are gonna use this method to insert a value at the beginning of the list
1 public void insertFirst(int data) { 2 Node newNode = new Node(); 3 newNode.data = data; 4 newNode.next = head; 5 head = newNode; 6 }
Here we first create a new Node called node Node node = new Node(); then we set the data of this node to the parameter data that we will pass as argument later when we call it. In the end we make the newNode point to the head (which is null) and then make head points to the newNode so now head is holding the address of this newNode and newNode is pointing to null, which is the end of the list.
IMPORTANT: Just to clear things out, if we insertFirst two times (like we are gonna do later) the second newNode is gonna start pointing to head which is the address of the first newNode and then head is gonna point to the second newNode making this:
1 head 2 ↓ 3newNode -> null
be this:
1 head 2 ↓ 3newNode2 -> newNode -> null
Now lets make our deleteFirst method
1 public void deleteFirst() { 2 //shifts the first node (head) to be where 3 //it was pointing (second node) 4 head = head.next; 5 }
This one is more simple and to the point, head points to what is next to the head. Basically shifts head to be the second node, making it the first node.
Before we continue with building our other methods lets make a printLinkedList method so you can see the results and have a better visualization of what the code is doing too.
Here is our printLinkedList method
1 public void printLinkedList() { 2 Node current = head; 3 while (current != null) { 4 current.displayNodeData(); 5 current = current.next; 6 7 } 8 System.out.print("NULL"); 9 10 }
We just make a Node called current that starts at head,which means that the node current starts pointing to the address of the first node. Then we loop the current node so that every loop we Displays our node data (with the displayNodeData() we made in our node class) and shifts the current node to the next node, passing through all the nodes in the linked list until we find null (which is the end), after the loop we just print "NULL" to indicate end of the list and make a nicer representation with the print.
Now lets create another java file called LinkedListMain.java . This is the file we will execute.
1package singlyLinkedList; 2 3public class LinkedListMain { 4 public static void main(String args[]) { 5 SinglyLinkedList linkedList = new SinglyLinkedList(); 6 linkedList.insertFirst(1); 7 linkedList.insertFirst(8); 8 linkedList.insertFirst(5); 9 linkedList.insertFirst(3); 10 linkedList.deleteFirst(); 11 //its gonna be 5 -> 8 -> 1 -> NULL 12 linkedList.printLinkedList(); 13 } 14}
Here we are gonna call our methods, when you run it the output should be be 5 -> 8 -> 1 -> NULL
Now you can test the methods the way you want! Lets get back to creating our other methods.
We created methods for inserting in the first place and deleting the first place, but if we want to put something at the last place? Well lets create methods for it, starting with insertLast
1 public void insertLast(int data) { 2 Node current = head; //start from the first node 3 //loop until current == null because you are looping 4 //all the nodes until you find the end (null) 5 while(current.next != null) { 6 current = current.next; 7 } 8 //insert the newNode next to current 9 //which now is the final node 10 Node newNode = new Node(); 11 newNode.data = data; 12 current.next = newNode; 13 }
Okay, here we start by doing something pretty similar to what we did in the printLinkedList method, we start by the head and loop, but here we loop until the current is pointing to null and not IS equal null. Because with this we will have current as the last node, because the last node is the one that points to null. Then we create a newNode and make the current point to the newNode so now it is the last node because the order changed from
current -> null
to
current -> newNode -> null .
After that we can create our deleteLast method
1 public void deleteLast() { 2 Node current = head; 3 Node temp = head; 4 while (current.next != null) { 5 temp = current; 6 current = current.next; 7 } 8 current = temp; 9 current.next = null; 10 }
Here we make like the insertLast method and make the exact same loop, but we have something different. That is the Node temp, so we can move current to the last position with our loop, but we also move the temp alongside so that in the end we have current in the last position current -> null but we have temp before that temp -> current -> null . Then we make current shift to temp position and make current point to null.
Okay, that`s great and all but... what if we want to put something in the middle for example? Or delete it? Well we can make a method to put a node anywhere AFTER another node.
Lets start with the insertAfter
1 public void insertAfter(Node after,int data) { 2 Node current = head; 3 Node temp = head; 4 while (temp.data != after.data ) { 5 temp = current; 6 current = current.next; 7 } 8 Node newNode = new Node(); 9 newNode.data = data; 10 temp.next = newNode; 11 newNode.next = current; 12 }
In the insertAfter we again use temp and we make a similar loop, but the condition is different. Now we want to match the temp.data that we are looping with the after.data that is a node we are gonna pass to our method. When the loop finishes we have temp in the place of our after node, which means we are gonna insert our newNode after the temp node where our current node is. After the loop we create the newNode and we make temp point to the newNode and make newNode point to the current node.
Now we have our last method, the deleteAfter method
1 public void deleteAfter(Node after) { 2 Node current = head; 3 while (current.data != after.data) { 4 current = current.next; 5 } 6 current.next = current.next.next; 7 }
Here we check if the current.data is != to after.data so we can have the position of the after node (the same way we made with temp in the last one). Then we just make the current point to what the it was pointing before was pointing to. Example:
current -> node1 -> node2
After the current.next = current.next.next:
current -> node2
And that`s all our methods implemented and explained. Now we can test all of them
1package singlyLinkedList; 2 3public class LinkedListMain { 4 public static void main(String args[]) { 5 SinglyLinkedList linkedList = new SinglyLinkedList(); 6 linkedList.insertFirst(1); 7 linkedList.insertFirst(8); 8 linkedList.insertFirst(5); 9 //its gonna be 5 -> 8 -> 1 -> NULL 10 11 linkedList.insertLast(3); 12 //now its gonna be 5 -> 8 -> 1 -> 3 -> NULL 13 Node node = new Node(); 14 node.data = 1; 15 linkedList.insertAfter(node, 10); 16 // now its gonna be 5 -> 8 -> 1 -> 10 -> 3 -> NULL 17 18 19 Node node2 = new Node(); 20 node2.data = 8; 21 linkedList.deleteAfter(node2); 22 // now its gonna be 5 -> 8 -> 10 -> 3 -> NULL 23 linkedList.deleteFirst(); 24 //now its gonna be 8 -> 10 -> 3 -> NULL 25 linkedList.insertFirst(14); 26 //now its gonna be 14 -> 8 -> 10 -> 3 -> NULL 27 linkedList.insertLast(40); 28 // now its gonna be 14 -> 8 -> 10 -> 3 -> 40 -> NULL 29 linkedList.deleteFirst(); 30 //now its gonna be 8 -> 10 -> 3 -> 40 -> NULL 31 linkedList.insertLast(56); 32 //now its gonna be 8 -> 10 -> 3 -> 40 -> 56 -> NULL 33 linkedList.deleteLast(); 34 // now its gonna be 8 -> 10 -> 3 -> 40 -> NULL 35 linkedList.printLinkedList(); 36 } 37}
I hope you understood or at least I could help just a little bit in your learning. This is my first article so I may or may not have explained or write in a good way but I will try to improve as I write more! If you want the source code you can check my repository in Github where I'm trying to make a list of Data Structures and Algorithms implemented in java (and maybe later in C ) with everything up to date or the source below that is the exact same code as above, I will let some links that you can check more about linked lists and that's it. Good studying and good luck!
SinglyLinkedList.java
1package singlyLinkedList; 2 3class Node { 4 //thats the value(data) that is inside the Node 5 public int data; 6 //Thats the pointer inside the Node, every Node 7 //has a pointer that store the address of the next node 8 //Here we call this pointers "next" 9 public Node next; 10 11 public void displayNodeData() { 12 System.out.print( data + " -> "); 13 } 14 15} 16 17public class SinglyLinkedList { 18 //Its private because we only need to reference head 19 //inside this class 20 private Node head; //here head == null 21 22 public void insertFirst(int data) { 23 Node newNode = new Node(); 24 newNode.data = data; 25 newNode.next = head; 26 head = newNode; 27 } 28 29 public void deleteFirst() { 30 //shifts the first node (head) to be where 31 //it was pointing (second node) 32 head = head.next; 33 } 34 35 public void insertLast(int data) { 36 Node current = head; //start from the first node 37 //loop until current == null because you are looping 38 //all the nodes until you find the end (null) 39 while(current.next != null) { 40 current = current.next; 41 } 42 //insert the newNode next to current 43 //which now is the final node 44 Node newNode = new Node(); 45 newNode.data = data; 46 current.next = newNode; 47 } 48 49 public void deleteLast() { 50 Node current = head; 51 Node temp = head; 52 while (current.next != null) { 53 temp = current; 54 current = current.next; 55 } 56 current = temp; 57 current.next = null; 58 } 59 60 public void insertAfter(Node after,int data) { 61 Node current = head; 62 Node temp = head; 63 while (temp.data != after.data ) { 64 temp = current; 65 current = current.next; 66 } 67 Node newNode = new Node(); 68 newNode.data = data; 69 temp.next = newNode; 70 newNode.next = current; 71 } 72 73 public void deleteAfter(Node after) { 74 Node current = head; 75 while (current.data != after.data) { 76 current = current.next; 77 } 78 current.next = current.next.next; 79 } 80 81 public void printLinkedList() { 82 Node current = head; 83 while (current != null) { 84 current.displayNodeData(); 85 current = current.next; 86 87 } 88 System.out.print("NULL"); 89 90 } 91}
LinkedListMain.java
1package singlyLinkedList; 2 3public class LinkedListMain { 4 public static void main(String args[]) { 5 SinglyLinkedList linkedList = new SinglyLinkedList(); 6 linkedList.insertFirst(1); 7 linkedList.insertFirst(8); 8 linkedList.insertFirst(5); 9 //its gonna be 5 -> 8 -> 1 -> NULL 10 11 linkedList.insertLast(3); 12 //now its gonna be 5 -> 8 -> 1 -> 3 -> NULL 13 Node node = new Node(); 14 node.data = 1; 15 linkedList.insertAfter(node, 10); 16 // now its gonna be 5 -> 8 -> 1 -> 10 -> 3 -> NULL 17 18 19 Node node2 = new Node(); 20 node2.data = 8; 21 linkedList.deleteAfter(node2); 22 // now its gonna be 5 -> 8 -> 10 -> 3 -> NULL 23 linkedList.deleteFirst(); 24 //now its gonna be 8 -> 10 -> 3 -> NULL 25 linkedList.insertFirst(14); 26 //now its gonna be 14 -> 8 -> 10 -> 3 -> NULL 27 linkedList.insertLast(40); 28 // now its gonna be 14 -> 8 -> 10 -> 3 -> 40 -> NULL 29 linkedList.deleteFirst(); 30 //now its gonna be 8 -> 10 -> 3 -> 40 -> NULL 31 linkedList.insertLast(56); 32 //now its gonna be 8 -> 10 -> 3 -> 40 -> 56 -> NULL 33 linkedList.deleteLast(); 34 // now its gonna be 8 -> 10 -> 3 -> 40 -> NULL 35 linkedList.printLinkedList(); 36 } 37}