Linked List Implementation in C#

CodeProject In this article I'll explain about linked list. What is pros and cons of using linked list and then implementation of linked list in C#. However microsoft provide strongly typed linked list LinkedList(T) in System.Collections.Generic namespace, I'll explain here core implementation of Linked List.

What is Linked List?
Linked list is a linear data structure. Its a collection of elements. Element called as Node.
Each element have value(data) and reference of next node.Very first node  called as Head and last element have reference to null value.

Types of Linked List

Basically there are 3 types of linked list.

1. Singly Linked List  : A singly linked list is a list which has a value(data) and a reference to next node.In this last node's next reference will be null.
2. Doubly Linked List : A doubly linked list is a list which has a data and 2 references, one for next node and another for previous node and last node's next reference will be null
3. Circular Linked List: In circular linked list last node's next reference will be head or first element. Circular linked list can be singly linked list or doubly linked list.

In this article I'll explain implementation of only singly linked list.

Pros and Cons

Main advantage of linked list is that Its a dynamic data structure.Unlike in array where length of array is predefined, we can add dynamic number of data in linked list without worrying about size of linked list. So linked list can be used where there is unknown number of data need to be stored at run time.

Disadvantage of linked list is that it takes more space than array. Because it stores reference of next/previous nodes.

Implementation of linked list

Node Class:

Here is the node class which have 2 properties.

 public class Node
 {
     public Node Next;
     public object Value;
 }

One property is 'Next', which will have reference of next node and another is 'Value', which will have data in this node.

LinkedList Class:
Now implement linked list class as follows:

public class LinkedList
{
   private Node head;
   private Node current;//This will have latest node
   public int Count;
}

'head' will have head node. 'current' will have latest node i.e. tail node and 'Count' will return total number of nodes in linked list.

Constructor: 
Initially head and current value will be same and will have empty node, so we will create constructor for that settings.

public LinkedList()
{
  head = new Node();
  current = head;
}

Operations in Linked list:
Now we will create  some operations on linked list.

1.Add node after last element

public void AddAtLast(object data)
{
   Node newNode = new Node();
   newNode.Value = data;
   current.Next = newNode;
   current = newNode;
   Count++;
}

This method will add node after tail node and it will increase count by one.Similarly you can add node as fist node.

2.Add node as fist element

 public void AddAtStart(object data)
 {
   Node newNode = new Node() { Value = data};
   newNode.Next = head.Next;//new node will have reference of head's next reference
   head.Next = newNode;//and now head will refer to new node
   Count++;
 }

3.Remove node from start:

public void RemoveFromStart()
{
   if (Count > 0)
   {
     head.Next = head.Next.Next;
     Count--;
   }
   else
   {
     Console.WriteLine("No element exist in this linked list.");
   }
}

Similarly you can write method to remove node from last or from any index.You have to do traverse from head to that particular index and remove node as above by changing the reference.

4.Traverse whole linked list

/// 

/// Traverse from head and print all nodes value
/// 
public void PrintAllNodes()
{
    //Traverse from head 
    Console.Write("Head ->");
    Node curr = head;
    while (curr.Next != null)
    {
        curr = curr.Next;
        Console.Write(curr.Value);
        Console.Write("->");
    }
    Console.Write("NULL");
}

Start from head and traverse until you get next node is null.

Note: Similarly you can write code for deleting node of specific index , inserting node on specific position etc.

Time to celebrate...
Now its time to test our code.To test our code we will write main method and call linked list and its operations in that.

class Program
{
    static void Main(string[] args)
    {
           
        LinkedList lnklist = new LinkedList();
        lnklist.PrintAllNodes();
        Console.WriteLine();

        lnklist.AddAtLast(12);
        lnklist.AddAtLast("John");
        lnklist.AddAtLast("Peter");
        lnklist.AddAtLast(34);
        lnklist.PrintAllNodes();
        Console.WriteLine();

        lnklist.AddAtStart(55);
        lnklist.PrintAllNodes();
        Console.WriteLine();

        lnklist.RemoveFromStart();
        lnklist.PrintAllNodes();


        Console.ReadKey();
    }
}

Guess what'll be output. Here it is..

You can download this project. To download CLICK HERE.


Did you like this article. Feel free to reach me by comments.

Max Number of indexes Per Table

In sql server 2005 
Clustered Index 1 + Non clustered index 249 = 250 index

 In sql server 2008/2008 R2/2012

 Clustered Index 1 + Non clustered index 999 = 1000 index

Reference: http://msdn.microsoft.com/en-us/library/ms143432(v=sql.110).aspx

Truncate can/can't be roll backed!!!!!!!!!!!!!

One major difference(its partially myth) between truncate and delete is that truncate can't be rolled back while delete can be rolled back.

But its  a myth .Truncate can also be rolled back but only if it is in Transaction statement.I will try to explain with some example .

 Lets a table users.

Case 1:

BEGIN TRAN

  TRUNCATE TABLE users    

  ROLLBACK

END TRAN

Now execute -

SELECT * FROM Users ; will return all data .

Obviously DELETE will return same result means all data will be returned.

Case 2:

Now execute 

TRUNCATE TABLE users    

and then execute immediately 

ROLLBACK  (here rollback without begin transaction)

Then execute 

SELECT * FROM Users ; NO DATA will be returned,means here table is not rolled back

But DELETE can be rolled back in this situation

Now execute 

DELETE TABLE users    

and then execute immediately 

ROLLBACK  (here rollback without begin transaction)

Then execute 

SELECT * FROM Users ;  All data will be returned i.e. table rolled back successfully.

Conclusion:

TRUNCATE can be rolled back when used with in TRANSACTION,while DELETE can be rolled back either used within transaction or outside transaction block.

Find nth Highest salary(value) from table

Presume: Let there is a table name Employee and it has a field name salary(bigint).
Problem: I want to get 5th(nth) highest salary.
Solution:Here is the query to retrieve 5th highest salary from employee table


                      SELECT TOP 1 Salary FROM Employee WHERE Salary IN
                              (SELECT TOP 5 DISTINCT( Salary) FROM Employee ORDER BY  Salary DESC )
                                ORDER BY Salary ASC

Note: Above query can be generalized to retrieve nth highest or lowest record from any table.

Delete duplicate row from table

To delete duplicate row from table execute this query.

DELETE FROM MyTable WHERE AUTOID NOT IN 

(SELECT MIN(AUTOID) 
 FROM MyTable  GROUP BY col1,col2) 

Where autoId is  auto increment id.

Static polymorphism Vs. Dynamic polymorphism

Static polymorphism Vs. Dynamic polymorphism

What is polymorphism? Poly means many. So how can we take this definition in .NET context. Well we can apply this to class’s ability to share the same methods (actions) but implement them differently.

Suppose we have a method in a class to add numbers,

public class calculation

{

public int add(int x, int y)

{

return x+y;

}

}

So to perform addition of three numbers, we need similar add method but with different parameter

public class calculation

{

public int add(int x, int y)

{

return x+y;

}

public int add(int x, int y,int z)

{

return x+y+z;

}

}

So we can that class is sharing the same methods (actions) but implement them differently.

Now this is an example when we are sharing method name and implementing them differently, let’s take a scenario where implementation is in some derived class.

For instance, say we create a class called Shape and this class has a method called .Area () which calculates area. Then we create two subclasses, using inheritance, of this Shape class. One called Square, the other called Circle. Now obviously a square and circle are two entirely different shapes, yet both classes have the .Area() method. When the Square.Area() method is called it will calculate area of  a square. When the Circle.Area() method is called, it will calculate area of a circle. So both classes can use the same methods but implement them differently.

Now let’s dive little deeper and understand what we discussed above in more technical terms.

Types of Polymorphism

1) Static or Compile time Polymorphism

Which method is to be called is decided at compile-time only. Method Overloading is an example of this. Method overloading is a concept where we use the same method name many times in the same class, but different parameters. Depending on the parameters we pass, it is decided at compile-time only. The same method name with the same parameters is an error and it is a case of duplication of methods which c# does not permit. In Static Polymorphism decision is taken at compile time.

public Class StaticDemo

{

public void display(int x)

{

Console.WriteLine(“Area of a Square:”+x*x);

}

public void display(int x, int y)

{

Console.WriteLine(“Area of a Square:”+x*y);

}

public static void main(String args[])

{

StaticDemo spd=new StaticDemo();

Spd.display(5);

Spd.display(10,3);

}

}

2) Dynamic or Runtime Polymorphism.

Run time Polymorphism also known as method overriding. In this Mechanism by which a call to an overridden function is resolved at a Run-Time (not at Compile-time) if a base Class contains a method that is overridden. Method overriding means having two or more methods with the same name, same signature but with different implementation. In this process, an overridden method is called through the reference variable of a superclass, the determination of the method to be called is based on the object being referred to by reference variable.

Class BaseClass

{

Public void show ()

{

Console.WriteLine(“From base class show method”);

}

}

Public Class DynamicDemo : BaseClass

{

Public void show()

{

Console.WriteLine(“From Derived Class show method”);

}

Public static void main(String args[])

{

DynamicDemo dpd=new DynamicDemo ();

Dpd.show();

}

}
Here memory allocation will be at the run time for that particular method.

What is Virtual Function: They implement the concept of polymorphism are the same as in C#, except that you use the override keyword with the virtual function implementation in the child class. The parent class uses the same virtual keyword. Every class that overrides the virtual method will use the override keyword.

Why to use them:

1)    It is not compulsory to mark the derived/child class function with Override KeyWord while base/parent class contains a virtual method

2)    Virtual methods allow subclasses to provide their own implementation of that method using the override keyword

3)    Virtual methods can’t be declared as private.

4)    You are not required to declare a method as virtual. But, if you don’t, and you derive from the class, and your derived class has a method by the same name and signature, you’ll get a warning that you are hiding a parent’s method

5)    A virtual property or method has an implementation in the base class, and can be overriden in the derived classes.

6)    We will get a warning if we won’t use Virtual/New keyword.

7)    Instead of Virtual we can use New Keyword

class A 
{
public void M()
{
Console.WriteLine(“A.M() being called”);
}

public virtual void N()
{
Console.WriteLine(“A.N() being called”);
}
}

class B : A
{
public new void M()
{
Console.WriteLine(“B.M() being called”);
}

public override void N()
{
Console.WriteLine(“B.N() being called”);
}
}

say

A a = new B();

a.M();
a.N();

The results would be

A.M() being called
B.N() being called

Override Keyword: method overriding is modifying or replacing the implementation of the parent class with a new one. Parent classes with virtual or abstract members allow derived classes to override them.
class Shape
{
    public virtual void Draw()
    {
        Console.WriteLine(“Shape.Draw”)    ;
    }
}

class Rectangle : Shape

{
    public override void Draw()
    {
        Console.WriteLine(“Rectangle.Draw”);
    }
}

 चीयर्स जय हो.............

Script for swapping gender in sql server through CASE (Without Using Cursor)

I want to share you my experience about an interview where i was asked to write script for swapping gender using cursor and without using cursor.
   In my previous post I mentioned "Script for swapping gender through CURSOR" .Here I am sharing swapping gender using CASE .

Step 1: First of all create a table ,here "genderTest"

            CREATE TABLE  genderTest (id nvarchar(20) PRIMARY KEY,empname nvarchar(20),gender           nvarchar(1))

Step 2:Now insert some values in table

       INSERT INTO gendertest VALUES ('1','ashish','m')
       INSERT INTO gendertest VALUES ('2','nandani','f')
       INSERT INTO gendertest VALUES ('3','chandrasen','m')
       INSERT INTO gendertest VALUES ('4','priynka','f')
       INSERT INTO gendertest VALUES ('5','sonam','f')
       INSERT INTO gendertest VALUES ('6','guru','m')
       INSERT INTO gendertest VALUES ('7','faisal','m')
       INSERT INTO gendertest VALUES ('8','priti','f')

Step 3: Execute following query


           UPDATE genderTest 
           SET gender=
          CASE gender
          WHEN 'f' THEN 'm'
          ELSE 'f'
      END
   Above script will swap gender.
    

Technology Improver: Script for swapping gender in sql server through Cursor

Technology Improver: Script for swapping gender in sql server through Cursor

Script for swapping gender in sql server through Cursor

Step 1:Create table ,here GenderConvert

--create table GenderConvert(name nvarchar(20),gender nvarchar(1))

Step 2:Insert some Values in table

--insert into genderconvert values('ashish', 'm' )

--insert into genderconvert values('sonam', 'f' )

--insert into genderconvert values('priya', 'f' )

--insert into genderconvert values('sonu', 'm' )

--insert into genderconvert values('anshu', 'f' )

--insert into genderconvert values('vinod', 'm' )

--insert into genderconvert values('pappu ', 'm' )

--insert into genderconvert values('pavan', 'm' )

--insert into genderconvert values('priynka', 'f' )

--insert into genderconvert values('sonali', 'f' )

--insert into genderconvert values('guru', 'm' )

STEP 3:Execute this script (cursor)

DECLARE @name nvarchar(20)

DECLARE @gender nvarchar(1)

DECLARE @MyCursor CURSOR

--Assign table to cursor variable

SET @MyCursor = CURSOR FOR 

SELECT name,gender FROM genderconvert

--Open cursor

OPEN @MyCursor

--Fetch cursor row on by one

FETCH NEXT 

FROM @MyCursor INTO @name , @gender

WHILE @@FETCH_STATUS = 0

BEGIN

if(@gender = 'm' )

BEGIN 

UPDATE  genderconvert set gender='f' where name=@name

END

else

BEGIN 

UPDATE  genderconvert set gender='m' where name=@name

END

FETCH NEXT FROM @MyCursor into  @name,@gender

END

           After executing this script gender will be swap.Please give your valuable review if this post helpful for you.