Implementing
generic linked list and performing basic operation on them with O(1) time
complexity is easier than what the developers think. It's just the hype of Data
Structures and the word Time Complexity.
Linked list
is basically a object which holds of another object of same type and so on for
every other object until the reference to next object becomes null. What is
this reference? It’s just a reference variable which has an object.
To
understand this better let’s take an example.
How many of
you have seen Naruto? Well specific for this answer I’m going to get little
less views :-D
Do you understand
the word Izanmi
In this every instance which Kabuto experience is an object which hold a reference to another instance and so on until null is reached
In this every instance which Kabuto experience is an object which hold a reference to another instance and so on until null is reached
Getting it.
Now lets
move to coding example-
using System;
using System.Collections.Generic;
namespace Stucts.ADT.GenericLinkedList
{
public class Node<T>
{
public T data;
public Node<T> next = null;
}
}
It’s a simple
class which have one variable to hold data and one to hold the reference of same
type of object
using System;
using System.Collections.Generic;
namespace Stucts.ADT.GenericLinkedList
{
public class SimpleGenericLinkedList<T>
{
Node<T> head = null;
Node<T> tail = null;
private Node<T> CreateNode(T data, Node<T> next)
{
Node<T> newItem = new Node<T>();
newItem.data = data;
newItem.next = next;
return newItem;
}
public void Add(T
data)
{
if (head == null)
{
head = CreateNode(data, null);
tail = head;
}
else {
tail.next = CreateNode(data,null);
tail = tail.next;
}
}
public void
RemoveNode(T data)
{
if (head.data.Equals(data))
{
head = head.next;
}
else
{
head.next = Remove(data,
head.next);
}
}
public Node<T> Remove(T data, Node<T> current)
{
if (current != null)
{
if (current.data.Equals(data))
{
current = current.next;
}
else
{
current.next = Remove(data,
current.next);
}
}
return current;
}
public void
ReadAll()
{
Node<T> current = head;
while (current.next != null)
{
Console.WriteLine(current.data); ;
current = current.next;
}
Console.WriteLine(current.data); ;
}
}
}
Here I have performed
some vary basic operation like adding, removing from head and traversing the
entire list
Now to
insert every new node in linked list we need to traverse through all the nodes
and then add the node in the last.
Due to this
traversal adding new node in linked list becomes time consuming and less
effective with Time Complexity of O(n). This is clearly an issue. We can solve
this by performing one very basic step while adding every node
In your Generic
Linked list class add Tail node just like Head and when you add new node make
it tail and keep adding new elements to tail.
SimpleGenericLinkedList<int> lnkList = new SimpleGenericLinkedList<int>();
lnkList.Add(1);
lnkList.Add(2);
lnkList.Add(3);
lnkList.Add(4);
lnkList.Add(5);
lnkList.Add(6);
lnkList.Add(7);
lnkList.Add(8);
lnkList.Add(9);
lnkList.Add(10);
lnkList.RemoveNode(6);
lnkList.ReadAll();
This is how
the linked list object looks like
Just look at
the object lnkList for
every new node it has next and that next has another next and goes on until the
lnkList.next.next….next == null;
Well that’s how
linked list works and with just an easy step you can perform addition in linked
list cost effective i.e. O(1)
For more
content like this follow and share the blog
Thanks.
how can implements a cantainsKey() method in the custom Dictionary class
ReplyDelete