Array vs linked list

A few reasons why Array is better

• In array, we the provision of random access. But in linked list, the nodes can only be sequentially accessed. 
• Better locality - Whenever the OS brings data into memory, it loads a whole page. Hence less page fault occurs. With linked list, different parts of the linked list are stored at different parts of memory. Hence branch Prediction doesn't work as well with linked list. This causes the pipeline to be flushed more often which result in poor performance.
• In linked list, the extra storage needed for references, which often makes them impractical for lists of small data items such as characters or boolean values. It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element.

A few reasons why Linked List is better

• It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size.
• It's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow.
• Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory.
• As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.

new instead of malloc

While searching I found a very naive, but useful thing about new/malloc.

Why should we use new instead of malloc ?

1. New and Delete makes sure that constructors and sestructors are called but not the case with malloc and free functions of C. 
2. Pointer conversion safety: malloc() returns a void* which isn't safe. new returns a pointer of the right type. 
3. new is a Operator: new is an operator that can be overloaded for better memory management by a class, while malloc() is not an operaotor. 
4. new operator computes the size of object automatically whereas malloc cannot.
5. It is possible to initialize the object while allocating memory with new. 
6. Its possible to construct an object over an already allocated memory using another version of 'new' operator known as 'placement new' operator. While with malloc() it is not possible.

Nth last element in Linked List (C++)

The following code shows how to get nth last element in a linked list. It uses a queue to hold the temporary elements.

Algorithm:-
1>Make a queue of length N
2>Traverse the linked list from root
3>While traversing, en-queue first N elements
4>After this for en-queuing every element, de-queue another element.
5>When we reach the end of linked list, the last de-queued element will be the Nth last element.

/* 
 * File:   main.cpp
 * Author: Asit
 *
 * Created on 16 September, 2011, 12:25 AM
 */

#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;

struct node
{
    int data;
    node *next;
};

class LinkedList
{
    node *root;
public:
    LinkedList():root(NULL){}
    void add(int x)
    {
        node *temp = NULL;
                
        if(root==NULL)
        {
            root = new node;
            root->data = x;
            root->next = NULL;
        }
        else
        {
            temp = root;
            while(temp->next != NULL)
            {
                temp = temp->next;
            }
            
            temp->next = new node;
            temp = temp->next;
            temp->data = x;
            temp->next = NULL;
        }
    }
    
    void show()
    {
        node *temp = root;
        
        while(temp != NULL)
        {
            cout<<temp->data<<"  ";
            temp = temp->next;
        }
        cout<<endl;
    }
    
    int nthLast(int n)
    {
        queue<node*> t_queue;
        int i=1, t_data = -1;
        node *temp = root;
        
        while(temp != NULL)
        {
            t_queue.push(temp);
            if(i>=n)
            {
                t_data = (t_queue.front())->data; 
                t_queue.pop();
            }
            i++;
            temp = temp->next;
        }
        
        i--;
        if(i<n)
            cout<<"Linked list contains less than "<<n<<" elements"<<endl;
        
        return t_data;
    }
};

int main(int argc, char** argv) 
{
    LinkedList list;
    
    for(int i=0; i<20; i++)
        list.add(i*7+90);
    
    cout<<"Created linked list is .. "<<endl;
    list.show();
    
    cout<<"3rd last element : ";
    
    cout<<list.nthLast(3)<<endl;
    
    return 0;
}

Output:-

Created linked list is .. 
90  97  104  111  118  125  132  139  146  153  160  167  174  181  188  195  202  209  216  223  
3rd last element : 209