Introduction: Linked List is a linear collection of data
elements, called nodes, each pointing to next node. Each node has value (data)
and reference to next node. The first head is called head.
Advantages
Unlike array it is dynamic in nature as it can grow by
allocating more memory and can shrink or reduce by deallocating the memory while
the application is running.
Insertion & deletion are easily implemented. Item can be
added or removed from anywhere in the sequence.
Disadvantages
It consumes more memory compared to array. Sequential access
of the nodes.
Types
Singly Linked List: It contains nodes which have a data
field and a next field which points to the next node in line of nodes. Last
node point to the null.
Doubly Linked List: Apart from data & next field, its
node has one additional field which point to the previous node.
Circular Linked List: Last node, instead of pointing to
null, points to first node.
using System;
namespace DataStructure
{
public interface ILinkedList<T>
{
void AddLast(Node<T> element);
void Print();
void AddAfter(Node<T> element, T value);
void Delete(T value);
}
public class Node<T>
{
public Node<T> Next;
public T Value;
}
public class SinglyLinkedList<T> : ILinkedList<T>
{
private Node<T> _head;
private Node<T> _current;
/// <summary>
/// Add the element at the last
/// </summary>
/// <param name="element"></param>
public void AddLast(Node<T> element)
{
if (_head == null) //LinkedList is empty so made it head
{
_head = element;
}
else
{
_current.Next = element;
}
_current = element;
}
/// <summary>
/// Display the linkedlist
/// </summary>
public void Print()
{
var tmpNode = _head;
while (tmpNode != null)
{
Console.WriteLine("Value stored:{0}",tmpNode.Value);
tmpNode = tmpNode.Next;
}
}
/// <summary>
/// Add the node after the given value
/// </summary>
/// <param name="element"></param>
/// <param name="data"></param>
public void AddAfter(Node<T> element, T data)
{
var tmpNode = _head;
while (tmpNode != null)
{
if(data.Equals(tmpNode.Value)) break;
tmpNode = tmpNode.Next;
}
if(tmpNode==null) throw new Exception("data does not exist in the Linked List");
element.Next = tmpNode.Next;
tmpNode.Next = element;
}
public void Delete(T data)
{
var tmpNode = _head;
if (tmpNode.Value.Equals(data))
{
_head = _head.Next;
return;
}
while (tmpNode.Next != null)
{
if (data.Equals(tmpNode.Next.Value)) break;
tmpNode = tmpNode.Next;
}
if(tmpNode.Next != null && tmpNode.Next.Next != null)
tmpNode.Next = tmpNode.Next.Next;
else //Last Node updatae _current position
{
tmpNode.Next = null;
_current = tmpNode;
}
}
}
public class Program
{
public static void Main(string[] args)
{
Console.WriteLine("XXXX------Creating Linked List------XXX");
var linkedList = new SinglyLinkedList<int>();
linkedList.AddLast(new Node<int>() { Next = null, Value = 100 });
linkedList.AddLast(new Node<int>() { Next = null, Value = 101 });
linkedList.AddLast(new Node<int>() { Next = null, Value = 102 });
linkedList.Print();
Console.WriteLine("XXXX------Adding at the end------XXX");
linkedList.AddLast(new Node<int>() { Next = null, Value = 103 });
linkedList.AddLast(new Node<int>() { Next = null, Value = 105 });
linkedList.AddLast(new Node<int>() { Next = null, Value = 109});
linkedList.Print();
Console.WriteLine("XXXX------Add after------XXX");
linkedList.AddAfter(new Node<int>() { Next = null, Value = 106 },105);
linkedList.Print();
Console.WriteLine("XXXX------Deleting First Node------XXX");
linkedList.Delete(100);
linkedList.Print();
Console.WriteLine("XXXX------Deleting Middle Node------XXX");
linkedList.Delete(103);
linkedList.Print();
Console.WriteLine("XXXX------Deleting Last Node------XXX");
linkedList.Delete(109);
linkedList.Print();
Console.WriteLine("XXXX------Adding after 105------XXX");
linkedList.AddAfter(new Node<int>() { Next = null, Value = 111 }, 105);
linkedList.Print();
Console.WriteLine("XXXX------Adding at the Last------XXX");
linkedList.AddLast(new Node<int>() { Next = null, Value = 120 });
linkedList.Print();
Console.WriteLine("XXXX------Adding at the Last------XXX");
linkedList.AddLast(new Node<int>() { Next = null, Value = 121 });
linkedList.Print();
Console.ReadKey();
}
}
}
No comments:
Post a Comment