Tuesday, July 10, 2012

Reverse a Linked-list. Write code in C.

There are multiple ways to go about this. Let’s first look at a recursive solution.

Recursive Method:

Node * reverse( Node * ptr , Node * previous)
{
    Node * temp;
    if(ptr->next == NULL) {
        ptr->next = previous;
        return ptr;
    } else {
        temp = reverse(ptr->next, ptr);
        ptr->next = previous;
        return temp;
    }
}
reversedHead = reverse(head, NULL);
 
Non-Recursive Method
 
Node * reverse( Node * ptr )
{
    Node * temp;
    Node * previous = NULL;
    while(ptr != NULL) {
        temp = ptr->next;
        ptr->next = previous;
        previous = ptr;
        ptr = temp;
    }
    return previous;
}

Sunday, July 8, 2012

What is thread safe code?

Thread safety is a programming concept applicable in the context of multi-threaded programs. A method or piece of code is thread-safe if it only manipulates shared data structures in a manner that guarantees safe execution by multiple threads at the same time.

Example: Methods used in Logger, to write a log file, should be threading safe for an application that runs under multi-threading environment.

Difference between Managed code and Native code

Native Code: Native code is computer programming (code) which generally written in C, C++ language and after compilation its IL is specific to the Processor Architecture. With respect to .net programming, Native code is the code is not managed code. The code takes care of allocation and de-allocation of every bit of memory to object. There is no garbage collection, reference counting kind of memory management for the Native code. For example C++ code. C++ code is not a managed code. To dereference the unused object we have to explicitly call Delete. There is no Garbage collector for C++ code. Unfortunately, I haven’t work on C++ language.

Managed Code: Managed code is executed by .Net Framework Common Language Runtime (CLR). It refers the contract of co-operation between natively executing code and the run-time. The memory allocation and de-allocation to an object is done by .Net Framework. User doesn’t have control on it. Dereferencing the unused memory/object has been taken care by Garbage Collector (GC).  Example: we use Finalize() and Dispose() method in our Managed Code implementation.  Garbage Collection runs Finalize() method before an object that is eligible for collection is reclaimed. Dispose() cleans unmanaged resources, like network connections, files etc.

Cheers!

Difference between Singly Linked List and Doubly Linked List

Friends!
We all know how to deal with Singly and Doubly linked list.
Now here I tried to put some differences which will help you to take decisions on the choice of using linked list type in your implementation.
Your inputs are welcome to make this increase the number of differences.


S.No. Singly Linked List Doubly Linked List
1 Singly linked list allows you to go one way direction Doubly linked list has two way directions next and previous
2 Singly linked list uses less memory per node (one pointer) Doubly linked list uses More memory per node than Singly Linked list (two pointers)
3 There is a little-known trick that lets you delete from a singly-linked list in O(1), but the list must be circular for it to work (move the content of next into the current, and delete next). Doubly-linked lists can be used in places where singly-linked lists would not work (a doubly-ended queue), but they require slightly more "housekeeping", and are slightly less efficient on insertions as the result
4 Complexity of Insertion and Deletion at known position is O (n). Complexity of Insertion and Deletion at known position is O (1).
5 If we need to save memory in need to update node values frequently and searching is not required, we can use Singly Linked list. If we need faster performance in searching and memory is not a limitation we use Doubly Linked List
6
For B-Tree, Heap we need doubly linked list. .Net Framework only provides the LinkedList<T> class which is double-linked.
7 If we know in advance that element to be searched is found near the end of the list(for example name 'Yogesh' in a telephone directory), even then singly linked list is traversed sequentially from beginning. In doubly linked list If we know in advance that element to be searched is found near the end of the list(for example name 'Yogesh' in a telephone directory), then the list can traversed from the end thereby saving time
8 In single list Each node contains at least two parts:
a) info
b) link
In doubly linked list Each node contains at least three parts:
a) info
b) link to next node
c) link to previous node

Cheers!