Coders become profound debaters when it comes to coding with the best programming language. Python, C++ and Java top the list when it comes to competitive programming, their lovers often lure others to join their bandwagon. Though there is no clear winner, yet I personally feel Java should get a little more love when it comes to data structures, specially Linked Lists.
Linked lists are beautiful data structures. They can be imagined like a train with various compartments, separate, yet linked together.The direction of engine can be interpreted as the direction of traversal. Since elements are not stored at contiguous memory locations and connected with pointers, working with linked lists is slightly different from arrays.
Firstly and most importantly, with Java, we do not need to care about the de-allocation of memory when we delete something from the linked list. This is a great advantage over C++, where you have to de-allocate items every time you delete something from a linked list, which becomes very complex when it comes to circular doubly linked lists with a large number of nodes.
While implementing linked lists with Java, you do not need to learn anything extra — simply a concoction of classes, their objects and references. A lot of people anticipate that since Java does not support pointers, the very element of linked lists, it might be very difficult writing code with Java. However, Java uses references instead of pointers, which makes it even easier for beginners to understand.
The following code shows implementation of singly linked lists, with Java.
import java.util.*;
import java.io.*; import java.lang.*; //importing libraries
class Node{ //creation of node of linked list
int data; //data type of linked list
Node head; //head of the linked list
Node(int x){//constructor to add data
data =x; head = null;}}
class Test{
public static void main(String args[]){
Node head = new Node(1); //use of object
head.next = new Node(12); //use of references instead of pointers
head.next.next = new Node (13);}}
For a person acquainted with the basics of Java, implementing Linked Lists is basically understanding when and how to use references to create the ‘links’. We create node by using node class. This method helps us easier to create and store objects i.e. the elements of the linked list. In the node class, we declare the data type of the linked list. Then, in the constructor node, we assign values to data and next. Node next is assigned as null in the beginning because this is how a linked list is identified. In the class Test, we actually implement the linked list with data values we want to input. For this we use objects and references to the head node. Here ‘next’ is used to point towards the value of the next node.
For other operations, Java performs like C++ but when it comes to deletion of a node of a linked list, Java comes with an advantage — no need to de-allocate the memory. The same is shown below:
import java.util.*;
import java.io.*;
import java.lang.*;
class Node{
int data;
Node prev;
Node next;
Node(int d){
data=d;
prev=null;
next=null;
}
}
class Test {
public static void main(String args[])
{
Node head=new Node(10);
Node temp1=new Node(20);
Node temp2=new Node(30);
head.next=temp1;
temp1.prev=head;
temp1.next=temp2;
temp2.prev=temp1;
head=delLast(head);
printlist(head);
}
static Node delLast(Node head){
if(head==null)return null;
if(head.next==null){
return null;
}
Node curr=head;
while(curr.next!=null)
curr=curr.next;
curr.prev.next=null;
return head; // no need to de-allocate memory
}
public static void printlist(Node head){
Node curr=head;
while(curr!=null){
System.out.print(curr.data+” “);
curr=curr.next;
}System.out.println();
}
}
For the same program in C++, the code somewhat looks like:
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* next;
Node(int x){
data=x;
next=NULL;
}
};
void printlist(Node *head){
Node *curr=head;
while(curr!=NULL){
cout<<curr->data<<” “;
curr=curr->next;
}cout<<endl;
}
Node *delTail(Node *head){
if(head==NULL)return NULL;
if(head->next==NULL){
delete head; //de-allocate memory
return NULL;
}
Node *curr=head;
while(curr->next->next!=NULL)
curr=curr->next;
delete (curr->next);
curr->next=NULL;
return head;
}
int main()
{
Node *head=new Node(10);
head->next=new Node(20);
head->next->next=new Node(30);
printlist(head);
head=delTail(head);
printlist(head);
return 0;
}
Though the above example is very simple and does not show how de-allocation of memory can be a bit complicated , while operating with doubly linked lists and circular linked lists with large data, Java comes as a handy and suitable option. Python too, does not require to de-allocate memory.
