I have created a class SLList
where I take in a doubly linked list SLList
and make some adaptations to it.
Now, I'm trying to remove the first node in the doubly linked list and the last node in the doubly linked list via two functions known as public T firstout()
and public T lastout()
and I think the purpose of each function is pretty self-explanatory.
Based on the recommendation of StackOverflow user, I have decided to use just one sentinel to aid in my task. However, I'm struggling to rightfully implement sentinels to my advantage.
Here is my code so far:
public class SLList<T>{ // Add Generics here
private class IntNode {
private T data;
private IntNode previous;
private IntNode next;
public IntNode (T data, IntNode previous, IntNode next) {
this.data = data;
this.previous = previous;
this.next = next;
}
public IntNode () { // Self-referencing node
next = previous = this;
}
}
IntNode sentinel; // One sentinel can serve both purposes
private int length = 0;
public SLList(){
sentinel = new IntNode(); // Self referencing previous/next
}
public void addFirst(T data) {
IntNode node = new IntNode(data, sentinel, sentinel.next);
sentinel.next = node;
node.next.previous = node;
}
public boolean isempty() {
return length == 0;
}
public T firstout() {
return sentinel.previous == null;
}
public T lastout() {
return sentinel.next == null;
}
Based on what I've tried to find, I thought .previous
points to the start of the list and setting it to null would effectively remove the first one and .next
points to the next node, and setting it to null would also remove the last one.
Where has my understanding gone wrong here? Any tips or code improvements would be greatly appreciated
First of all, you don't need length
to know whether the list is empty. You could also define the isEmpty
method like this:
public boolean isEmpty() {
return sentinel.next == sentinel;
}
NB: I prefer camelCase instead of all lowercased method names, so isEmpty
instead of isempty
, and firstOut
instead of firstout
.
For the firstOut
and lastOut
methods, I would first define a private method that removes a given node from the list (assuming it is in the list):
private T removeNode(IntNode node) {
// Link neighbors to eachother, skipping over given node
node.previous.next = node.next;
node.next.previous = node.previous;
return node.data;
}
This can then be used as follows:
public T firstOut() {
return removeNode(sentinel.next);
}
public T lastOut() {
return removeNode(sentinel.previous);
}
In this version, if the list is empty and firstOut
or lastOut
is called, the removeNode
call will not change anything to the list, because the node it gets will be the sentinel node which links to itself, and so both assignments just confirm what is already the case. firstOut
or lastOut
will return the value of the sentinel node in that case.
You could alternatively throw an exception when the list is empty when removeNode
is called. But exception handling is a topic on itself, so I will not dive into that here.