Below there is a C# implementation of a singly-linked list data structure.

The following operations are trivial on the singly-linked list:

• Inserting a node at the beginning.
• Removing a node from the beginning.
• Adding a node at the end.

The following operations are not trivial and not implemented in the single-linked list:

• Removing a given node.
• Inserting a node before a given node.
• Removing the last node.

The standard solution to implement arbitrary insertions and deletions is to use a doubly-linked list.

// singly-linked list

using System;

namespace ConsoleTest
{
class Program
{
// A nested class that defines the node.
// The purpose of this class is to structure data.
private class Node
{
public T Item { get; set; }
public Node Next { get; set; }

public override string ToString() { return (Item == null ? "null" : Item.ToString()); }
}

static void Main(string[] args)
{
var first = new Node();
first.Item = "A";

var second = new Node();
second.Item = "B";
first.Next = second;

var third = new Node();
third.Item = "C";
second.Next = third;

var fourth = new Node();
fourth.Item = "D";
third.Next = fourth;

// Insert a node at the beginning.
Node oldFirst = first; // we need to know the first element in the list
first = new Node(); // (*)
first.Item = "BEGIN";
first.Next = oldFirst;

// Remove the node from the beginning.
// The node created at (*) becomes an orphan.
first = first.Next; // we need to know the first element in the list

// Remove a node immediately following 'second' i.e. the node 'third'.
second.Next = second.Next.Next;

// Insert a new node immediately after 'second'.
var newNode = new Node();
newNode.Item = "NEW";
newNode.Next = second.Next;
second.Next = newNode;

// Traverse the items in the linked list 'first'.
for (Node n = first; n != null; n = n.Next)
{
Console.WriteLine(n.Item.ToString());
}


A