Skip to content

Instantly share code, notes, and snippets.

@basavesh
Created November 9, 2012 08:35
Show Gist options
  • Save basavesh/4044475 to your computer and use it in GitHub Desktop.
Save basavesh/4044475 to your computer and use it in GitHub Desktop.
DoublyLinkedList.java
package edu.cmu.cs771.hw1;
/**
* 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.
* @author songluo
*
*/
public class DoublyLinkedList {
private DoubleNode head;
private DoubleNode tail;
/**
* Constructs a new DoublyLinkedList object with head and tail as null.
*/
public DoublyLinkedList() {
head = null;
tail = null;
}
/**
* Returns true if the list is empty false otherwise
* @return true if the list empty false otherwise
*/
public boolean isEmpty(){
return head == null;
}
/**
* Add a character node containing the character c to the end of the linked list. This routine does not require a search.
* @param c a single character
*/
public void addCharAtEnd(char c){
DoubleNode n = new DoubleNode(tail, c, null);
if(isEmpty()){
head = tail = n;
}else{
tail.setNext(n);
tail = n;
}
}
/**
* Add a character node containing the character c to the front of the linked list. No search is required.
* @param c a single character
*/
public void addCharAtFront(char c){
DoubleNode n = new DoubleNode(null, c, head);
if(isEmpty()){
head = tail = n;
}else{
head.setPrev(n);
head = n;
}
}
/**
* Remove and return the character at the front of the doubly linked list.
* @return the character at the front precondition: the list is not empty
*/
public char removeCharFromFront(){
char ch = head.getC();
if(!isEmpty()){
if(head == tail){
head = tail = null;
}else{
head = head.getNext();
head.setPrev(null);
}
}
return ch;
}
/**
* Remove and return the character at the end of the doubly linked list. No searching is required.
* @return the character at the end precondition: the list is not empty
*/
public char removeCharAtEnd(){
char ch = tail.getC();
if(!isEmpty()){
if(head == tail){
head = tail = null;
}else{
tail = tail.getPrev();
tail.setNext(null);
}
}
return ch;
}
/**
* Counts the number of nodes in the list. We are not maintaining a counter so a search is required.
* @return the number of nodes in the doubly linked list between head and tail inclusive
*/
public int countNodes(){
DoubleNode cn = head;
int count = 0;
while(cn != null){
count++;
cn = cn.getNext();
}
return count;
}
/**
* Deletes the first occurence of the character c from the list. If the character c is not in the list then no modifications are made. This method needs to search the list.
* @param c the character to be searched for.
* @return true if a deletion occurred and false otherwise
*/
public boolean deleteChar(char c){
DoubleNode cn = head;
while(cn.getC() != c){
cn = cn.getNext();
}
if(cn != null){
if(cn.getPrev() == null){
head = cn.getNext();
if(!isEmpty()){
head.setPrev(null);
}
}else if(cn.getNext() == null){
tail = cn.getPrev();
if(!isEmpty()){
tail.setNext(null);
}
}else{
cn.getPrev().setNext(cn.getNext());
cn.getNext().setPrev(cn.getPrev());
}
}
return cn != null;
}
/**
* Returns the list as a String. The class DoubleNode has a toString that will be called from this toString. The String returned must be presented clearly. Null pointers must be represented differently than non-null pointers.
* @see java.lang.Object#toString()
* @return a String containing the characters in the list
*/
public String toString(){
DoubleNode cn = head;
String str = "";
while(cn != null){
str += cn.getC();
//System.out.print(cn.getC());
cn = cn.getNext();
}
return str;
}
/**
*Reverse the list. a -> b -> c becomes c -> b -> a
*/
public void reverse(){
DoubleNode cn = head;
DoubleNode tmp = null;
while(cn != null){
tmp = cn.getNext();
cn.setNext(cn.getPrev());
cn.setPrev(tmp);
cn = cn.getPrev();
}
tmp = head;
head = tail;
tail = tmp;
head.setPrev(null);
tail.setNext(null);
}
/**
* Test driver for DoublyLinkedList
*/
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());
}
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment