/**This class implements a doubly linked list of characters in Java.
* The instance variables head and tail are initially null.
* As elements are added head points to the first element on the
* list and tail points to the last element.
* Each node on the list is of type DoubleNode.
* Each DoubleNode holds a pointer to the previous
* node and a pointer to the next node in the list.
* @param head Keeps track of the first node of the list. Null if nothing.
* @param tail Keeps track of the last node of the list. Null if nothing.
*/
public class DoublyLinkedList {
//data field
DoubleNode head;
DoubleNode tail;
/**Constructor
* Precondition: The object to be created is casted as DoublyLinkedList
* Postcondition:Constructs a new DoublyLinkedList object with head and
tail as null
* Best case and worst case are the same: theta(1)
* Afterwards a new null list comes into existence
*/
public DoublyLinkedList(){
head = null;
tail = null;
}
/**Mutator
* @param c The character to be added
* Precondition: The character is an uppercase
* or lowercase letter (in the range 'A' ... 'Z' or 'a' ... 'z')
* Postcondition:A character node containing the character
* c will be added to the end
* Best case and worst case are the same: theta(1)
*/
public void addCharAtEnd(char c){
if(this.isEmpty()) {//When no node in list so far
head = new DoubleNode(null,null,c);
tail = head;
}
else{//More than one node exist(s)
DoubleNode endNode = new DoubleNode(tail,null,c);
tail.setNext(endNode);
tail = endNode;
}
}
/**Deletes the first occurence of the character c from the list
* @param c the character want to find and then deleted
* @return True if a deletion occurred and false otherwise
* Precondition: The character is an uppercase
* or lowercase letter (in the range 'A' ... 'Z' or 'a' ... 'z')
* Postcondition:Afterwards the list will abandon the first occurence of
* the character c from the list or won't change(if c not presented)
* Best case: O(1)(theta(1),when node containing c happens to be the head)
* Worst case: went over the whole list. Theta(n)
* Average: theta(n)
*/
public boolean deleteChar(char c){
if(isEmpty()) return false;
else {
for(DoubleNode current = head; current != null; current = `enter code here`current.getNext()){
if(current.getC() == c){
if(current == head && tail != null){//More than one `enter code here`node and the node to be deleted is the head
head = head.getNext();
head.setPrev(null);
}
if(current == head && tail == null){//There is only `enter code here`one node
head = tail = null;
}
if(current == tail){//More than one node and the `enter code here`node to be deleted is the tail
tail = tail.getPrev();
tail.setNext(null);
}
else{//The node is between two more nodes in the list
DoubleNode previous = current.getPrev();
current.getNext().setPrev(previous);
previous.setNext(current.getNext());
}
}
return true;
}
return false;//After looping still nothing found
}
}
/**Mutator
* Precondition: The character is an uppercase
* or lowercase letter (in the range 'A' ... 'Z' or 'a' ... 'z')
* Postconditions: a character node containing the
* character c will be added to the start
* @param c The character to be added
* Best case and worst case are the same: theta(1)
*/
public void addCharAtFront(char c){
if(this.isEmpty()) {
head = new DoubleNode(null,null,c);
tail = head;
}
else{
DoubleNode newHead = new DoubleNode(null,head,c);
head.setPrev(newHead);
head = newHead;
}
}
/**Count the nodes in the list
* Precondition: The instance used to invoke the method exists
* Postcondition: Return the int number of the node in that
* instance, leaving everything unchanged.
* @return the number of nodes
* Could be no cases(nothing in list)
* If there are node(s)Best and Worst case: theta(n)(go over the list)
*/
public int countNodes(){
int counter = 0;
for(DoubleNode current = this.head; current != null; current = `enter code here`current.getNext()){
counter++;
}
return counter;
}
/**Remove and return the character at the beginning of the doubly linked list.
* Precondition: The instance used to invoke the method exists and
* there is at least one node in the instance(if not, returning ']')
* Postcondition: Remove and return the character at the beginning
* of the doubly linked list
* @return the character stored in the deleted node
* Best and worst case: theta(1)
*/
public char removeCharFromFront(){
char c;
if(isEmpty()) {
System.out.println("Empty list, returning ']'");
return ']';
}
else {
if(head == tail){//There is only one node
c = head.getC();
head = null;
tail = null;
return c;
}
else{
c = head.getC();
head = head.getNext();
head.setPrev(null);// line 156?
return c;
}
}
}
/**Remove and return the character at the end of the doubly linked list
* Precondition: The instance used to invoke the method exists and
* there is node in the instance(if not, returning ']')
* Postcondition: Remove and return the character at the end of the
* doubly linked list.
* @return the character stored in the deleted node
* Best and worst case: theta(1)
*/
public char removeCharAtEnd(){
char c;
if(isEmpty()) {
System.out.println("Empty list, returning ']'");
return ']';
}
else {
if(head == tail){//There is only one node
c = head.getC();
head = null;
tail = null;
return c;
}
else{
c = tail.getC();
tail.getPrev().setNext(null);
tail = tail.getPrev();
return c;
}
}
}
/**Check if the list is empty
* Precondition: The instance used to invoke the method exists
* Postcondition: Returns true if the list is empty false otherwise,
* leaving everything unchanged
* @return true if the list is empty false otherwise
* Best and worst case: Theta(1)
*/
public boolean isEmpty(){
if(head == null)
return true;
else return false;
}
/**Reverse the whole list by changing the pointer
* Precondition: The instance used to invoke the method exists
* Postcondition: The whole list will be reversed
* Could be no cases
* Best and worst is theta(n)
*/
public void reverse(){
if(isEmpty())
System.out.println("No node in the list");
else{
DoubleNode newTail = head;
head = tail;
for (DoubleNode current = tail; current != null; current = `enter code here`current.getPrev()){
current.setNext(current.getPrev());
current.setPrev(current.getNext());
}
tail = newTail;
}
}
/**toString methods overriding the one in java.lang.object
* Precondition: The instance used to invoke the method exists
* Postcondition: return the characters in list as String, leaving
* everything else unchanged.
* @return the String expression of the characters stored in the list
* Best case and worst case are the same: theta(n)
*/
public String toString(){
StringBuffer sb = new StringBuffer();
if(isEmpty())
return new String("No node in the list");
DoubleNode current = new DoubleNode();
for(current = this.head; current != null; current = `enter code here`current.getNext()){
sb.append(String.valueOf(current.getC()));
System.out.println(sb);
}
System.out.println(sb);
return new String(sb);
}
/**Test the DoublyLinkedList class
* @param args command-line arguments
* Initiate two nodes using different constructor. Test the above
* method.
*/
public static void main(String a[]) {
DoublyLinkedList list = new DoublyLinkedList();
list.addCharAtEnd('H');
list.addCharAtEnd('e');
list.addCharAtEnd('l');
list.addCharAtEnd('l');
list.addCharAtEnd('o');
System.out.println(list);
System.out.println("Deleting l");
list.deleteChar('l');
System.out.println(list);
System.out.println("Deleting H");
list.deleteChar('H');
System.out.println(list);
System.out.println("Deleting o");
list.deleteChar('o');
System.out.println(list);
System.out.println("Deleting e");
list.deleteChar('e');
System.out.println(list);
System.out.println("Deleting l");
list.deleteChar('l');
System.out.println(list);
list.addCharAtFront('o');
list.addCharAtFront('l');
list.addCharAtFront('l');
list.addCharAtFront('e');
list.addCharAtFront('H');
System.out.println(list);
System.out.println(list.countNodes());
System.out.println("Popping everything");
while(!list.isEmpty()){
System.out.println(list.removeCharFromFront());//line 294?
}
list.addCharAtFront('o');
list.addCharAtFront('l');
list.addCharAtFront('l');
list.addCharAtFront('e');
list.addCharAtFront('H');
System.out.println("Popping everything from the end");
while(!list.isEmpty()){
System.out.println(list.removeCharAtEnd());
}
System.out.println(list.countNodes());
list.addCharAtEnd('o');
list.addCharAtEnd('l');
list.addCharAtEnd('l');
list.addCharAtEnd('e');
list.addCharAtEnd('H');
list.reverse();
System.out.println(list);
list.reverse();
System.out.println(list);
}
}
public class DoubleNode {
// data field
private DoubleNode p;
private DoubleNode n;
private char c;
/**
* Constructor with parameters to initialize instance variables with given p, c, n
* Preconditions: p, c, n should be casted correctly to be the right instances
* Postcondition: Afterwards generates a new node with double pointers
* Best case and worst case are the same: theta(1)
*/
public DoubleNode(DoubleNode initialp, DoubleNode initialn, char initialc) {
DoubleNode p = initialp;
DoubleNode n = initialn;
char c = initialc;
}
/**Constructor without parameters
* Precondition: Initialize instance variables with unspecified value
* So no pre.
* Postcondition: A new node with null pointers come into existence
* Best case and worst case are the same: theta(1)
*/
public DoubleNode() {
this.p = null;
this.n = null;
}
/**Access to get the reference to previous node in specific node
* @return the reference to the previous node. Null if nothing
* Precondition: the instance used to invoke the method does exist
* Postcondition: Return the previous pointer in current instance while doesn't change the node
* Best case and worst case are the same: theta(1)
*/
public DoubleNode getPrev() {
return p;
}
/**Mutator to change the pointer pointing the previous node
* @param p the value of new previous pointer of that node
* Precondition: the instance used to invoke the method does exist. n is `enter code here`created to be DoubleNode.
* Postcondition: Set the previous pointer in Node while leave other things `enter code here`the same.
* Best case and worst case are the same: theta(1)
*/
public void setPrev(DoubleNode p) {
this.p = p;
}
/**Access to get the reference to next node in specific node
* @return the reference to the next node. Null if nothing
* Precondition: the instance used to invoke the method does exist
* Postcondition: Return the next pointer in current instance while doesn't change the node
* Best case and worst case are the same: theta(1)
*/
public DoubleNode getNext() {
return n;
}
/**Mutator to change the pointer pointing the next node
* @param n the value of new next pointer of that node
* Precondition: the instance used to invoke the method does exist. n is `enter code here`created to be DoubleNode
* Postcondition: Set the next pointer in Node while leave other things the `enter code here`same.
* Best case and worst case are the same: theta(1)
*/
public void setNext(DoubleNode n) {
this.n = n;
}
/**Access to get the character in specific node
* @return the character in the node
* Precondition: the instance used to invoke the method does exist
* Postcondition: Return the character in current instance while doesn't `enter code here`change the node
* Best case and worst case are the same: theta(1)
*/
public char getC() {
return c;
}
/**Mutator to change the character in specific node
* @param c the value to be changed to
* Precondition: the instance used to invoke the method does exist. The `enter code here`character is an uppercase
* or lowercase letter (in the range 'A' ... 'Z' or 'a' ... 'z')
* Postcondition: Reset the character in the Node while leave pointers the `enter code here`same
* Best case and worst case are the same: theta(1)
*/
public void setC(char c) {
this.c = c;
}
/**toString methods overriding the one in java.lang.object
* @return the String expression of the character stored in the node
* Precondition: the instance used to invoke the method does exist
* Postcondition: return the character as String in the node while dosen't `enter code here`change anything else
* Best case and worst case are the same: theta(1)
*/
public String toString() {
return String.valueOf(c);
}
/**Test the DoubleNode class
* @param args command-line arguments
* Initiate two nodes using different constructor. Test the methods above
*/
public static void main(String[] args){
DoubleNode dllNode = new DoubleNode();
StringBuffer test = new StringBuffer();
System.out.println("Test: "+dllNode);
dllNode.setC('H');
dllNode.setNext(null);
dllNode.setPrev(null);
System.out.println("Test2: "+dllNode);
}
}
結果は次のようになります:
Hello
Deleting l
Helo
Deleting
He elo
Deleting o
el
Deleting e
l
Deleting l
リストにノードがありません
Hello 5 すべてをポップします Hello
5
すべてをポップします
H
e
l
l
o
最後からすべてをポップします
o
l
l
e
H
0
こんにちは
olleH
しかし、リンクされたリストを印刷できず、次のようなエラーもあります。
Exception in thread "main" java.lang.NullPointerException
at DoublyLinkedList.removeCharFromFront(DoublyLinkedList.java:156)
at DoublyLinkedList.main(DoublyLinkedList.java:294)