Posted by Abhishek on December 15, 2019
Linked Lists are one of the most commonly used Linear Data Structures after arrays. They solve many problems of arrays and are used for building complex data structures. Unlike arrays, Linked Lists can grow and shrink automatically.
LinkedList numbersList = new LinkedList();
numbersList.AddLast(10);
numbersList.AddLast(20);
numbersList.AddLast(30);
numbersList.AddFirst(5);
numbersList.RemoveLast();
numbersList.RemoveFirst();
Console.WriteLine(numbersList.IndexOf(20));
Console.WriteLine(numbersList.Contains(20));
Console.WriteLine(numbersList.Count);
foreach (var number in numbersList.ToArray())
{
Console.WriteLine(number);
}
Spend some time thinking about the strategy and then start coding. Don’t copy-paste the code.
public class LinkedList
{
private Node First;
private Node Last;
private int size;
public int Count
{
get { return size; }
}
public class Node
{
public int Value;
public Node Next;
public Node(int value)
{
Value = value;
}
}
public void AddLast(int number)
{
var newNode = new Node(number);
if (IsEmpty())
{
First = Last = newNode;
}
else
{
Last.Next = newNode;
Last = Last.Next;
}
size++;
}
public void AddFirst(int number)
{
var newNode = new Node(number);
if (IsEmpty())
{
First = Last = newNode;
}
else
{
newNode.Next = First;
First = newNode;
}
size++;
}
private bool IsEmpty()
{
return First == null;
}
public void RemoveFirst()
{
if (IsEmpty())
throw new System.Exception("No Such Element to Remove");
if (First == Last)
{
First = Last = null;
}
else
{
var nodeToDelete = First;
First = First.Next;
nodeToDelete.Next = null;
}
size--;
}
public void RemoveLast()
{
if (IsEmpty())
throw new System.Exception("No Such Element to Remove");
if (First == Last)
{
First = Last = null;
}
else
{
var previous = GetPrevious(Last);
Last = previous;
Last.Next = null;
}
size--;
}
private Node GetPrevious(Node node)
{
var currentNode = First;
while (currentNode != null)
{
if (currentNode.Next == node)
return currentNode;
else
currentNode = currentNode.Next;
}
return null;
}
public bool Contains(int number)
{
return IndexOf(number) != -1;
}
public int IndexOf(int number)
{
int index = 0;
var currentNode = First;
while (currentNode != null)
{
if (currentNode.Value == number)
{
return index;
}
else
{
currentNode = currentNode.Next;
index++;
}
}
return -1;
}
public int[] ToArray()
{
int[] array = new int[size];
var current = First;
var index = 0;
while (current != null)
{
array[index++] = current.Value;
current = current.Next;
}
return array;
}
}
Spend some time thinking about the strategy and then start coding. Don’t copy-paste the code.
public void Reverse()
{
if (IsEmpty())
return;
var prev = First;
var current = First.Next;
while (current != null)
{
var next = current.Next;
current.Next = prev;
prev = current;
current = next;
}
Last = First;
Last.Next = null;
First = prev;
}
Spend some time thinking about the strategy and then start coding. Don’t copy-paste the code.
public int GetKthFromTheEnd(int k)
{
if (IsEmpty())
throw new System.Exception("List is already empty");
var n1 = First;
var n2 = First;
for (int i = 0; i < k - 1; i++)
{
n2 = n2.Next;
if (n2 == null)
throw new System.Exception("K is greater than the size of the list");
}
while (n2 != Last)
{
n1 = n1.Next;
n2 = n2.Next;
}
return n1.Value;
}