This is the Main
class with main
method for generating a double-ended list, remove and display its elements.
public class Main {
Link first, last;
public static void main(String args[]) {
Main ob = new Main();
Link arr[] = {
new Link(1), new Link(2), new Link(3)
};
int len = 3;
for(int i=0;i<len;i )
ob.insertFirst(arr[i]);
System.out.print("Data in the list: ");
while(ob.first!=null)
System.out.print(ob.removeAndReturn() ", ");
for(int i=0;i<len;i )
ob.insertLast(arr[i]);
System.out.print("\nData in the list: ");
while(ob.first!=null)
System.out.print(ob.removeAndReturn() ", ");
}
void insertFirst(Link arg) {
if(isEmpty())
last = arg;
arg.next = first;
first = arg;
}
// This removeAndReturn() method returns the Object data the link is holding and removes that Link from the list
Object removeAndReturn() {
Object ret = null;
try {
ret = first.data;
if(first.next==null)
last = null;
first = first.next;
}catch(NullPointerException NPe) {
System.out.println("You are referring to a null.\nLinked List is empty.");
}
return ret;
}
void insertLast(Link arg) {
if(isEmpty())
first = arg;
else
last.next = arg;
last = arg;
}
boolean isEmpty() {
return first==null;
}
}
class Link {
Object data;
Link next;
Link(Object data) {
this.data = data;
}
}
When executing, it gives the following output:
Data in the list: 3, 2, 1,
Data in the list: 1, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, ... {truncated}
Here the last two elements gets repeated in the output. I tried nullifying both the Link
variables first
and last
before calling ob.insertLast(arr[i])
but it gives the same output.
Update:
- private keywords are removed from the complete method signature for methods in the
Main
class other thanmain(String args[])
method andrmF()
method is changed toremoveAndReturn()
.
CodePudding user response:
The main problem in your code lies in the fact that you're using the exact same nodes (the ones within the arr
) to fill your list with head and tail insertions.
In fact, once you perform your first head insertion, those nodes have been linked to each other like this:
(3) => (2) => (1) => null
So, when you're performing your second insertion, you have that node 1 points to node 2, node 2 points to node 3, and theoretically node 3 should point to null since it's supposed to be the last element. However, node 3's next field is still pointing to node 2 from the previous insertion. This creates a loop where node 2 and node 3 keep pointing at each other; thus yielding the infinite loop you're experiencing.
(1) => (2) => <= (3)
To fix your problem you could either reset the next
field of your nodes before re-using them (poor solution) or work with the actual data you need to structure rather than the nodes. In fact, the user of your class shouldn't be bothered with the details of your implementation and should only care about the info to be stored/represented (in your case int
numbers).
This is a possible solution to your problem:
public class Main {
Link first, last;
public static void main(String args[]) {
Main ob = new Main();
//Array of int not of links
int[] arr = {1, 2, 3};
int len = 3;
for (int i = 0; i < len; i )
ob.insertFirst(arr[i]);
System.out.print("Data in the list: ");
while (ob.first != null)
System.out.print(ob.removeAndReturn() ", ");
for (int i = 0; i < len; i )
ob.insertLast(arr[i]);
System.out.print("\nData in the list: ");
while (ob.first != null)
System.out.print(ob.removeAndReturn() ", ");
}
//------ CORRECTION ------
//The method should receive the info the user needs to store.
//It will then be up to you to represent it as a Link or whatever
//internal structure you're going to use tomorrow. Don't bind the
//user to your internal implementation.
//------------------------
void insertFirst(int arg) {
//Generating a new node (or link) based on the given info
Link l = new Link(arg);
if (isEmpty())
last = l;
l.next = first;
first = l;
}
// This removeAndReturn() method returns the Object data the link is holding and removes that Link from the list
Object removeAndReturn() {
Object ret = null;
try {
ret = first.data;
if (first.next == null)
last = null;
first = first.next;
} catch (NullPointerException NPe) {
System.out.println("You are referring to a null.\nLinked List is empty.");
}
return ret;
}
//-------- CORRECTION --------
//same explanation given above
//----------------------------
void insertLast(int arg) {
//Generating a new node (or link) based on the given info
Link l = new Link(arg);
if (isEmpty())
first = l;
else
last.next = l;
last = l;
}
boolean isEmpty() {
return first == null;
}
}
Lastly, Do not capture RuntimeException
. These are unchecked exceptions, not checked. You should investigate on their origin rather than simply catching them. What you've written is a bad practice.
https://docs.oracle.com/javase/tutorial/essential/exceptions/runtime.html
As @JayC667 has already said, you could improve some designing and naming of your class, methods and variables. There are some conventions, especially when talking about data structures. For example:
Your class is called
Main
but it describes aList
, a name likeMyList
would have been better.Your utility class,
Link
, could have been placed withinMyList
as a static nested class and probably namedNode
(it's a better fit).Some of your methods' names were a bit too cryptic. Self-explanatory names will better help the users of your class.
Avoid accessing the internal state of another object from outside (
list.first != null
). Methods should be your way to go to interrogate an object's state.Using generic types could have been a better implementation than just
Object
as generics provide: strict checks at compile time, avoid casting a more type safety, the ability to re-use the same code for different data types.
https://docs.oracle.com/javase/tutorial/java/generics/why.html
Here is a link to an implementation with the suggestions made above:
https://www.jdoodle.com/iembed/v0/s7C
CodePudding user response:
This is really really bad code.
- Keywords like
private
should be used. rmF
is a really bad method name.- The whole thing should be generic, not targeting
Object
. - The class name
Main
is really bad too, especially for a Linked List. - And the worst of all: it addresses the elements in reverse order with member variables
first
andlast
- when removing Links, the last pointer gets set to
null
, no matter how many items there are in the list.
Basically what you get is a single(ly) linked list that starts at the wrong end and removal is lethal.
Simply wrong.