Linked List vs Array

 

Key Differences Between Array and Linked List

1. An array is the data structure that contains a collection of similar type data elements whereas the Linked list is considered as non-primitive data structure contains a collection of unordered linked elements known as nodes.
2. In the array the elements belong to indexes, i.e., if you want to get into the fourth element you have to write the variable name with its index or location within the square bracket.
3. In a linked list though, you have to start from the head and work your way through until you get to the fourth element.
4. Accessing an element in an array is fast, while Linked list takes linear time, so it is quite a bit slower.
5. Operations like insertion and deletion in arrays consume a lot of time. On the other hand, the performance of these operations in Linked lists is fast.
6. Arrays are of fixed size. In contrast, Linked lists are dynamic and flexible and can expand and contract its size.
7. In an array, memory is assigned during compile time while in a Linked list it is allocated during execution or runtime.
9. Elements are stored consecutively in arrays whereas it is stored randomly in Linked lists.
10. The requirement of memory is less due to actual data being stored within the index in the array. As against, there is a need for more memory in Linked Lists due to storage of additional next and previous referencing elements.
11. In addition memory utilization is inefficient in the array. Conversely, memory utilization is efficient in the linked list.

 

Following are the points in favor of Linked Lists:

(1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage, and in practical uses, the upper limit is rarely reached.

(2) Inserting a new element in an array of elements is expensive because a room has to be created for the new elements and to create room existing elements have to be shifted.

 

For example, suppose we maintain a sorted list of IDs in an array id[].

id[] = [1000, 1010, 1050, 2000, 2040, …..].

And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).

Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

 

So Linked list provides the following two advantages over arrays

1) Dynamic size
2) Ease of insertion/deletion

 

Linked lists have following drawbacks:

1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
3) Arrays have better cache locality that can make a pretty big difference in performance.

Share:

Read More

Infix to postfix converstion

  Infix to postfix conversion

 

                            /* C++ implementation to convert infix expression to postfix*/
#include<iostream>
using namespace std;
const int size = 5;
class Stack{          // Stack Class...
char arr[size];
int top;
public:
Stack()
{
top = -1;
}
void push(char x)
{
top++;
arr[top] = x;
}
char pop()
{
return arr[top--];
}
int peek()
{
return arr[top];
}
bool isfull()
{
if(top>size)
return true;

return false;
}
bool isempty()
{
if(top<-1)
return true;

return false;
}

};
int prec(char c)        //Function to return precedence of operators....
{

    if(c == '^' || c=='$')
    return 3;
    else if(c == '*' || c == '/')
    return 2;
    else if(c == '+' || c == '-')
    return 1;
    else
    return -1;
}

int main()              // Main Driven....
{
Stack s;
string exp="(m*n/o/q^(a+b-d/q))";
string copy_string;    // for Storing converstion....
int l = exp.length();
for(int i =0; i<l;i++)
{
if(exp[i] >= 'a' && exp[i] <= 'z')       // If the scanned character is an operand, add it to output string....
copy_string+=exp[i];

else if(exp[i]=='(') // If the scanned character is an ‘(‘, push it to the stack....
s.push('(');

// If the scanned character is an ‘)’, pop and to output string from the stack
        // until an ‘(‘ is encountered.
else if(exp[i]==')')
{
while(s.peek()!='\0' && s.peek() != '(' )
{
char c = s.peek();
s.pop();
copy_string+=c;
}
if(s.peek()=='(' )
{
char c= s.peek();
s.pop();
}
}
//If an operator is scanned....
else{
            while(s.peek() != '\0' && prec(exp[i]) <= prec(s.peek()))
            {
                char c = s.peek();
                s.pop();
                copy_string+= c;
            }
            s.push(exp[i]);
        }
}
//Pop all the remaining elements from the stack....
while(s.peek() != '\0')
    {
        char c = s.peek();
        s.pop();
        copy_string+= c;
    }
   
    cout << copy_string << endl;

return 0;
}

Share:

Read More