Skip to content

Instantly share code, notes, and snippets.

@forkercat
Created April 1, 2019 02:31
Show Gist options
  • Save forkercat/7834d5af49d3d68979cf058599d63c1d to your computer and use it in GitHub Desktop.
Save forkercat/7834d5af49d3d68979cf058599d63c1d to your computer and use it in GitHub Desktop.
Sentinel problem?
/**
* Created by JunhaoW on 03/31/2019
*/
public class SLList_Sentinel {
private int size;
private IntNode sentinel; /* The first item (if it exists) is at sentinel.next */
/* sentinel should not be changed later (after init) */
public SLList_Sentinel() {
sentinel = new IntNode(63, null); /* whatever item is */
size = 0;
}
public SLList_Sentinel(int x) {
sentinel = new IntNode(63, null);
sentinel.next = new IntNode(x, null);
size = 1;
}
public static void main(String[] args) {
SLList L = new SLList();
System.out.println(L.getFirst()); /* getFirst bug */
}
/** Adds x to the front of the list */
public void addFirst(int x) {
sentinel.next = new IntNode(x, sentinel.next);
size += 1;
}
/** Return the first item in the list */
public int getFirst() {
return sentinel.next.item; /* BUT could be NullPointer still */
/* solution */
// if (sentinel.next == null) {
// return -1;
// } else {
// return sentinel.next.item;
// }
}
/** Delete the first element in the SLList */
/**
* With sentinel
*/
public int deleteFirst() {
/* sentinel.next could be null when size == 0 */
if (sentinel.next == null) {
return -1;
}
IntNode deletedNode = sentinel.next;
sentinel.next = sentinel.next.next;
/* .next.next could be null if size == 1, but it's okay */
return deletedNode.item;
}
/** .addLast (should be considered when using empty list) */
public void addLast(int x) {
size += 1;
/* Code for special case */
/*if (first == null) {
first = new IntNode(x, null);
return;
}*/
IntNode p = sentinel; /* absolutely not null */
/* p.next == null, if there is an empty list*/
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
@forkercat
Copy link
Author

Check the constructors and the data structure first. The reason why we use the sentinel here is to get rid of special cases (like the code for special case in addLast).

However, when I write code for getFirst and deleteFirst, I can't get rid of special cases.
E.g., in getFirst, I need to check whether sentinel.next is null or not, otherwise NullPointer exception will be raised.

Any idea?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment