Created
April 1, 2019 02:31
-
-
Save forkercat/7834d5af49d3d68979cf058599d63c1d to your computer and use it in GitHub Desktop.
Sentinel problem?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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
anddeleteFirst
, I can't get rid of special cases.E.g., in
getFirst
, I need to check whethersentinel.next
is null or not, otherwiseNullPointer
exception will be raised.Any idea?