Skip to content

Instantly share code, notes, and snippets.

@VegaFromLyra
Last active August 29, 2015 14:22
Show Gist options
  • Save VegaFromLyra/d277c89f577955264344 to your computer and use it in GitHub Desktop.
Save VegaFromLyra/d277c89f577955264344 to your computer and use it in GitHub Desktop.
Linked list implementation
using System;
namespace LinkedList
{
public class Program
{
public static void Main(string[] args)
{
LinkedList linkedList = new LinkedList();
Console.WriteLine("Add 1 to head");
linkedList.AddFirst(1);
Console.WriteLine("Add 2 to head");
linkedList.AddFirst(2);
Console.WriteLine("Display All");
linkedList.DisplayAll();
Console.WriteLine("Add 3 to tail");
linkedList.AddLast(3);
Console.WriteLine("Add 4 to tail");
linkedList.AddLast(4);
Console.WriteLine("Display All");
linkedList.DisplayAll();
Console.WriteLine("Found 3? {0}", linkedList.Find(3));
Console.WriteLine("Delete 3");
linkedList.Delete(3);
Console.WriteLine("Display All");
linkedList.DisplayAll();
Console.WriteLine("Found 3? {0}", linkedList.Find(3));
Console.WriteLine("Reverse linked list");
linkedList.Reverse();
Console.WriteLine("Display All");
linkedList.DisplayAll();
Console.WriteLine("Fetch 4");
var nodeToDelete = linkedList.Get(4);
if (nodeToDelete != null) {
Console.WriteLine("Found " + nodeToDelete.Data);
} else {
Console.WriteLine("Could not find node");
}
Console.WriteLine("Delete 4");
linkedList.Delete(nodeToDelete);
Console.WriteLine("Display all");
linkedList.DisplayAll();
Console.WriteLine("Is a cycle present? {0}", linkedList.IsCyclePresent());
}
}
class Node {
public Node(int data) {
this.Data = data;
}
public int Data { get; set; }
public Node Next { get; set; }
}
class LinkedList {
private Node head;
private Node tail;
public void AddFirst(int value)
{
if (head == null && tail == null)
{
head = new Node(value);
tail = head;
}
else
{
Node newNode = new Node(value);
newNode.Next = head;
head = newNode;
}
}
public void AddLast(int value)
{
if (head == null && tail == null)
{
head = new Node(value);
tail = head;
}
else
{
Node newNode = new Node(value);
tail.Next = newNode;
tail = newNode;
}
}
public bool Find(int value)
{
Node current = head;
while (current != null)
{
if (current.Data == value)
{
return true;
}
current = current.Next;
}
return false;
}
public bool Delete(int value)
{
if (head == null || tail == null)
{
return false;
}
bool hasValueBeenDeleted = false;
if (head.Data == value)
{
head = head.Next;
hasValueBeenDeleted = true;
}
else if (tail.Data == value)
{
Node current = head;
while (current != null)
{
if (current.Next == tail)
{
break;
}
}
current.Next = null;
hasValueBeenDeleted = true;
}
else
{
Node prev = head;
Node current = head.Next;
while (current != null)
{
if (current.Data == value)
{
prev.Next = current.Next;
hasValueBeenDeleted = true;
}
prev = current;
current = current.Next;
}
}
return hasValueBeenDeleted;
}
// Deleting a node using the node itself
public void Delete(Node n) {
if (n.Next != null) {
Node next = n.Next;
n.Data = next.Data;
n.Next = next.Next;
next.Next = null;
} else {
throw new Exception("Cannot delete last node");
}
}
public bool IsCyclePresent() {
if (head == null) {
return false;
}
Node slow = head;
Node fast = head;
while ((fast != null) && (fast.Next != null)) {
slow = slow.Next;
fast = fast.Next.Next;
if (slow == fast) {
return true;
}
}
return false;
}
public Node Get(int value) {
Node current = head;
while (current != null) {
if (current.Data == value) {
return current;
}
current = current.Next;
}
return current;
}
public void DisplayAll()
{
if (head == null)
{
Console.WriteLine("Please initialise linked list with some entries first");
}
Node current = head;
while (current != null)
{
Console.Write(current.Data + " ");
current = current.Next;
}
Console.WriteLine();
}
public Node Reverse() {
Node current = head;
Node prev = null;
Node next = null;
tail = head;
while (current != null) {
next = current.Next;
current.Next = prev;
prev = current;
current = next;
}
head = prev;
return head;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment