Memory Management and OutofMemoryException Handling

n this article, I have tried to analyze the various causes which may lead to Memory Exception.
Once an ‘OutOfMemoryException’ is thrown, how best can it be handled has been discussed in this artilce.
OutOfMemoryException is thrown when there is not sufficient available memory to carry out a requested activity. In this article, I have tried to illustrate the different methods by which memory leaks can be handled in Web Applications.

Memory Management

When a program is loaded into memory, it is organized into three areas of memory, called segments: the text segment, stack segment, and heap segment. The text segment (sometimes also called the code segment) is where the compiled code of the program itself resides. This is the machine language representation of the program steps to be carried out, including all functions making up the program, both user defined and system.
The remaining two areas of system memory are where storage may be allocated by the compiler for data storage. The stack is where memory is allocated for automatic variables within functions. A stack is a Last In First Out (LIFO) storage device where new storage is allocated and deallocated at only one “end”, called the top of the stack.
When a program begins executing in the function main(), space is allocated on the stack for all variables declared within main(). If main() calls a function, func(), additional storage is allocated for the variables in func() at the top of the stack. It should be clear that memory allocated in this area will contain garbage values left over from previous usage.
The heap segment provides more stable storage of data for a program; memory allocated in the heap remains in existence for the duration of a program. Therefore, global variables (storage class external), and static variables are allocated on the heap. The memory allocated in the heap area, if initialized to zero at program start, remains zero until the program makes use of it. Thus, the heap area need not contain garbage.

OutofMemoryException Handling

Once an OutOfMemoryException has been thrown, the following checks should be carried out:
Handling Connection Objects: Check whether all objects pertaining to Connection, ResultSet, Statement and PreparedStatement have been properly closed in the finally block. Since the Connection objects are drawn from a Connection pool (the pool size depends on Server Configuration), if multiple Connection objects are created without closing them, it would result in reduction of the connection pool size and may throw an OutOfMemoryException if the pool is exhausted. Hence, even though there might be unused connection objects, the pool may be exhausted resulting in exception being thrown.
Handling OutputStream Objects: Check whether all OutputStream objects have been properly closed in the finally block. Streams are usually resource intensive objects and thus should be handled in a point-to-point manner. Hence it is imperative to close the streams individually to prevent memory leaks.
Checking for Static Variables: Static variables are stored in the heap and only one instance of variable is available throughout the lifetime of the application. Since static variables are not garbage collected till the class is unloaded or the variables are explicitly set to NULL, it needs to be checked whether all static variables are being used or some are unnecessarily occupying heap space.
Checking Third Party APIs: It is necessary to check the memory utilization of third party APIs. If the memory utilization is high (for example, if many static variables have been used), it may lead to OutOfMemoryException.
Usage of Singleton Classes: Adoption of the Singleton pattern results in creation of classes for which memory is allocated on the heap and not freed anywhere which may result in memory leaks. Hence, it is necessary to check the design pattern being followed, and in case of singleton pattern, check the number of classes which may be holding up space in the heap. Singleton pattern should not be used unless imperative.
Size of Session Objects: Since, it is possible to put large objects in a session, it is necessary to check the session size. Hence, it is important to check during memory leaks, the size of the session as well as the objects that might have been put in the session. To avoid memory leaks, only those objects should be put in the session which need to be put and should be removed when not required anymore.
If the above suggested checks do not throw a cause for memory leaks, the below mentioned methods may be carried out to determine the cause for memory leaks:
Using verbose:gc: The verbose:gc utility can be configured in startWebLogic.cmd to obtain information about the Java Object Heap in real time while running the Java application.
To activate the utility, Java must be run with -verbose:gc option.
For using verbose:gc; set the JVM size to 64 MB so that we may reach the maximum without load on the server. If the used memory does not drop to initial levels after full GC, then it would indicate a memory leak.

linked list in java and Operations on a singly-linked list

Singly-linked list

Linked list is a very important dynamic data structure. Basically, there are two types of linked list, singly-linked list and doubly-linked list. In a singly-linked list every element contains some data and a link to the next element, which allows keeping the structure. On the other hand, every node in a doubly-linked list also contains a link to the previous node. Linked list can be an underlying data structure to implement stack, queue or sorted list.

Example

Sketchy, singly-linked list can be shown like this:

Each cell is called a node of a singly-linked list. First node is called head and it's a dedicated node. By knowing it, we can access every other node in the list. Sometimes, last node, called tail, is also stored in order to speed up add operation.

Operations on a singly-linked list

Concrete implementation of operations on the singly-linked list depends on the purpose, it is used for. Following the links below, you can find descriptions of the common concepts, proper for every implementation.

LinkedList :

http://www.technicalypto.com/2010/01/java-program-to-reverse-singly-linked.html

class SinglyLinkedListNode {

      public int value;

      public SinglyLinkedListNode next;

      public SinglyLinkedListNode(int value) {

            this.value = value;

            next = null;

      }

}

public class SinglyLinkedList {

      private SinglyLinkedListNode head;

      private SinglyLinkedListNode tail;

      public SinglyLinkedList() {

            head = null;

            tail = null;

      }

      public void addLast(SinglyLinkedListNode newNode) {

            if (newNode == null)

                  return;

            else {

                  newNode.next = null;

                  if (head == null) {

                        head = newNode;

                        tail = newNode;

                  } else {

                        tail.next = newNode;

                        tail = newNode;

                  }

            }

      }

      public void addFirst(SinglyLinkedListNode newNode) {

            if (newNode == null)

                  return;

            else {

                  if (head == null) {

                        newNode.next = null;

                        head = newNode;

                        tail = newNode;

                  } else {

                        newNode.next = head;

                        head = newNode;

                  }

            }

      }

      public void insertAfter(SinglyLinkedListNode previous,

                  SinglyLinkedListNode newNode) {

            if (newNode == null)

                  return;

            else {

                  if (previous == null)

                        addFirst(newNode);

                  else if (previous == tail)

                        addLast(newNode);

                  else {

                        SinglyLinkedListNode next = previous.next;

                        previous.next = newNode;

                        newNode.next = next;

                  }

            }

      }

      public void removeFirst() {

            if (head == null)

                  return;

            else {

                  if (head == tail) {

                        head = null;

                        tail = null;

                  } else {

                        head = head.next;

                  }

            }

      }

      public void removeLast() {

            if (tail == null)

                  return;

            else {

                  if (head == tail) {

                        head = null;

                        tail = null;

                  } else {

                        SinglyLinkedListNode previousToTail = head;

                        while (previousToTail.next != tail)

                              previousToTail = previousToTail.next;

                        tail = previousToTail;

                        tail.next = null;

                  }

            }

      }

     

public void removeNext(SinglyLinkedListNode previous) {

            if (previous == null)

                  removeFirst();

            else if (previous.next == tail) {

                  tail = previous;

                  tail.next = null;

            } else if (previous == tail)

                  return;

            else {

previous.next = previous.next.next;

            }

      }

      public int traverse() {

        int sum = 0;

        SinglyLinkedListNode current = head;

        SinglyLinkedListNode previous = null;

        while (current != null) {

              sum += current.value;

              previous = current;

              current = current.next;

        }

        return sum;

  }

}

Java Program to reverse a Singly Linked List

I have written an efficient way to reverse a Singly Linked List using three pointers/nodes for traversal/temporary purposes. I have given a pictorial representation of what happens with near, mid and far pointer. The program is mostly self explanatory. Remember, we are using our implementation of Singly Linked List. You may visit this link if you need that class.

Note : You may click on the above image to get a clearer picture.

Now, for the source code.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

package dsa.linkedlist; /**  * Reverse a singly linked list  * @author Braga  */ public class ReverseAList {     public static void main(String args[]){   ReverseAList reverser = new ReverseAList();   SinglyLinkedList<Integer> originalList = reverser.getLabRatList(10);   System.out.println("Original List : "+originalList.toString());   reverser.reverseList(originalList);   System.out.println("Reversed List : "+originalList.toString());  }     public void reverseList(SinglyLinkedList<Integer> sourceList){   if(sourceList.size<=1){    return;   }   Node<Integer> nearNode = sourceList.start;   Node<Integer> midNode, farNode;       midNode = nearNode.next;   farNode = midNode.next;       nearNode.next = null;       while(farNode!=null){    midNode.next = nearNode;         nearNode = midNode;    midNode = farNode;    farNode = farNode.next;   }   midNode.next = nearNode;   sourceList.start = midNode;  }     private SinglyLinkedList<Integer> getLabRatList(int count){   SinglyLinkedList<Integer> sampleList = new SinglyLinkedList<Integer>();   for(int i=0;i<count;i++){    sampleList.add(i);   }   return sampleList;  } } //-----------------OUTPUT--------------------- //Original List : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 //Reversed List : 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

 

 

Loop in a Singly-Linked List

Question: How would you find a loop in a singly-linked list?
Answer: This is a very typical tech interview question that has a very elegant solution that runs in O(n) time and O(1) space. Also referred to as the “Tortoise and Hare Algorithm”,  the solution uses a fast pointer (traversing the list two items at a time) and a slow pointer (traversing the list one item at a time). If there is a loop, then the fast pointer will go around the loop twice as fast as the slow pointer. At one point, these two pointers will point to the same item. Here’s some code to make this clearer.

bool hasLoop( Node *startNode )

{

    Node *slowNode, *fastNode;

    slowNode = fastNode = startNode;

    while( slowNode && fastNode && fastNode->next )

    {

        if( slowNode == fastNode->next || slowNode == fastNode->next->next )

        {

            return true;

        }

        slowNode = slowNode->next;

        fastNode = fastNode->next->next;

    }

    return false;

}

Update: Thanks to RiderOfGiraffes for this solution.
The time complexity of this solution is still O(n), same as the solution provided above but this solution takes less number of steps at each point.

bool hasLoop( Node *startNode )

{

    Node *tortoise, *hare;

    int test_size = 2, steps_taken = 0;

    tortoise = hare = startNode;

    while( tortoise && hare->next )

    {

        hare = hare->next, steps_taken++;

        if( tortoise == hare )

        {

            return true;

        }

        if ( steps_taken>=test_size )

        {

            steps_taken = 0, test_size *= 2;

            tortoise = hare;

        }

    }

    return false;

}