Declaring an Edge Adjacency List Graph

The 3 types of Graph representations are: 1. Edge List 2. Adjacency Edge List 3. Edge Matrix The heart of the simplest representation of Edge List is the following:

LinkedList [ ] AdjLists = new LinkedList [numberOfVertices];

This implies that we are declaring an Array called AdjLists. No matter what, the Graph at the end is just an Array!!! This Array called AdjLists will hold elements of the type LinkedList which are in turn containers of type 'Edge'. Whatever Edge means... So basically, we are implementing a 3 level structure, at the end the edge objects are elements that are stored in Linked Lists, which are themselves stored in an Array! How beautiful!!!!!!!!!!!!

MaximallyBalanced or Complete Binary Tree

// Queue version -- only version totally working so far!
    public boolean isMaximallyBalanced (TreeNode x){ 

            boolean scanningNulls = false;

            Deque q = new LinkedList ();
            q.addFirst(x);

            while (q.size() != 0) {
                TreeNode n = q.remove();

                if (scanningNulls) {
                    if (n != null) 
                        return false;
                }
                else {
                    if (n == null) {
                        scanningNulls = true;
                    }
                    else {
                        q.add(n.myLeft);
                        q.add(n.myRight);
                        
                    }
                    }
                }
            
            return true;
        }

// Adopted from: www.boyet.com/Articles/CheckingForHeap.html 

Calculating the Height of a Tree

//Increase the height only when the recursive call generates a new Iterator!!!
private static int height (T x) {
     if (x.myChildren.isEmpty ( )) {
         return 1;
     } else {
         int bestSoFar = 0;
         Iterator iter = x.myChildren.iterator ( );
         while (iter.hasNext ( )) {
             T child = iter.next ( );
             bestSoFar = Math.max (height(child) + 1, bestSoFar);
         }
         return bestSoFar;
     }
 }

Adding to a Circular Doubly Linked List

public void add (Object to_Add) {
    if (isEmpty ( )) {
      myHead = new DListNode (to_Add);
    } else {
      // Insert to_Add between myHead and myHead.myPrev.
      DListNode newNode = new DListNode (to_Add, myHead.myPrev, myHead);
      // Link the new node into the list.
      myHead.myPrev.myNext = newNode; // This is the circular link stuff.
      myHead.myPrev = newNode;
    }
    mySize++;
  }

3 ways to REVERSE a list (singly linked)

There are 50 ways to leave your lover (P.Simon) but fundamentally 3 ways
 to reverse a list
1. Recursively Non-Destructive
2. Recursively Destructive
3. Iteratively

Recursively Non-Destructive:

public ListNode reverse (ListNode list) {
  ListNode sofar = new EmptyListNode();
        return reverseHelper (this, sofar);

 }


 private static ListNode reverseHelper (ListNode list1, ListNode sofar) {

        if (list1.isEmpty()) {

                return sofar;

        } else {

                return reverseHelper (list1.rest() ,  new NonemptyListNode (list1.first(), sofar) );

        }

 }
 


Recursively Destructive:




public void reverse2 () {
  myHead = reverse2Helper (myHead, null);
 }
 
 public static ListNode reverse2Helper (ListNode L, ListNode soFar){
  if (L == null){
   return soFar;
  } else {
   ListNode temp = L.myRest;
   L.myRest = soFar;
   return reverse2Helper (temp, L) ;
  }
 }




Iteratively:



public void reverse3 () {
  myHead = reverse3Helper (myHead);
 }

public static ListNode reverse3Helper (ListNode head){
  ListNode p, soFar;
  for (p = head, soFar = null; p != null;){
   ListNode temp = p.myRest;
   p.myRest = soFar;
   
   soFar = p;
   p = temp;
   
  }
  return soFar;
 
}

Reversing a List Iteratively!

public void reverse3 () {
  myHead = reverse3Helper (myHead);
 }

public static ListNode reverse3Helper (ListNode head){
  ListNode p, soFar;
  for (p = head, soFar = null; p != null;){
   ListNode temp = p.myRest;
   p.myRest = soFar;
   soFar = p;
   p = temp;
   
  }
  return soFar;
 
}

Doubling a Linked List

//couldn't find a better way to do this...

public void double2 ( ) {
  /* Invariant is L with 2 first ones and rest*/
  ListNode q, w;
  w = q = new ListNode (null);
  
  for (ListNode p = myHead; p != null; p = p.myRest) {
       
       q.myRest = new ListNode(p.myFirst, p);
       q = q.myRest.myRest;
       
               
     }
  myHead = w.myRest;
   /*ListNode p = myHead;
  ListNode p1 = myHead.myRest;
  ListNode p2 = myHead.myRest.myRest;
  
  myHead = new ListNode (p.myFirst, p);
  myHead.myRest.myRest = new ListNode (p1.myFirst, p1);
  myHead.myRest.myRest.myRest.myRest = new ListNode (p2.myFirst, p2);
   */
 }
 
 public void double3 ( ) {
  ListNode w;
  w = new ListNode (myHead.myFirst);
  for (ListNode p = myHead; p != null; p = p.myRest) {
   w.myRest= new ListNode(p.myFirst, p);
   w = w.myRest.myRest;
   System.out.println(this.toString());
  }
  myHead = new ListNode (myHead.myFirst, myHead);
 }