The following program implements a doubly-linked list, where each node contains a reference to the item preceding it and the item following it. The following methods are provided:

  • Inserting a node at the beginning: InsertFirst(DoubleNode<string> node)
  • Inserting a node at the end: InsertLast(DoubleNode<string> node)
  • Removing a node from the beginning: RemoveFirst()
  • Removing a node from the end: RemoveLast()
  • Inserting before a given node: InsertBefore(DoubleNode<string> node, DoubleNode<string> newNode)
  • Inserting after a given node: InsertAfter(DoubleNode<string> node, DoubleNode<string> newNode)
  • Removing a given node: Remove(DoubleNode<string> node)
using System;

namespace ConsoleTest
{
    class Program
    {
        private static DoubleNode first;

        static void Main(string[] args)
        {
            PopulateList();
            ShowItems();

            Console.WriteLine("InsertFirst(\"X\")");
            var n1 = new DoubleNode();
            n1.Item = "X";
            InsertFirst(n1);
            ShowItems();

            Console.WriteLine("InsertLast(\"Y\")");
            var n2 = new DoubleNode();
            n2.Item = "Y";
            InsertLast(n2);
            ShowItems();

            Console.WriteLine("RemoveFirst()");
            RemoveFirst();
            ShowItems();

            Console.WriteLine("RemoveLast()");
            RemoveLast();
            ShowItems();

            Console.WriteLine("InsertBefore(\"C\", \"*\")");
            var n3 = new DoubleNode();
            n3.Item = "*";
            InsertBefore(first.Next.Next, n3); // first.Next.Next is "C"
            ShowItems();

            Console.WriteLine("InsertAfter(\"C\", \"#\")");
            var n4 = new DoubleNode();
            n4.Item = "#";
            InsertAfter(first.Next.Next.Next, n4); // first.Next.Next.Next is "C" because we have inserted one node
            ShowItems();

            Console.WriteLine("Remove(\"C\")");
            Remove(first.Next.Next.Next); // first.Next.Next.Next is "C" because we have inserted one node
            ShowItems();

            Console.ReadKey();
        }

        // Insert a node at the beginning.
        static private void InsertFirst(DoubleNode node)
        {
            if (first == null)
            {
                first = node;
                return;
            }

            DoubleNode oldFirst = first; 
            first = node;
            first.Next = oldFirst;
            oldFirst.Prev = first;
        }

        // Insert a node at the end.
        static private void InsertLast(DoubleNode node)
        {
            if (first == null)
            {
                first = node;
                return;
            }

            // Determine the last node.
            DoubleNode last = first;
            while (last.Next != null)
                last = last.Next;

            node.Prev = last;
            last.Next = node;
        }

        // Remove a node from the beginning.
        static private void RemoveFirst()
        {
            if (first == null)
                return;

            // Does the list have only one element?
            if (first.Next == null)
            {
                first = null;
                return;
            }

            first = first.Next;
            first.Prev = null;
        }

        // Remove a node from the end.
        static private void RemoveLast()
        {
            if (first == null)
                return;

            // Does the list have only one element?
            if (first.Next == null)
            {
                first = null;
                return;
            }

            // Determine the last node.
            DoubleNode last = first;
            while (last.Next != null)
                last = last.Next;

            last.Prev.Next = null;
        }

        // Insert before a given node.
        static private void InsertBefore(DoubleNode node, DoubleNode newNode)
        {
            DoubleNode prev = node.Prev; // keep the current prev node of the given node

            // Modify the given node.
            node.Prev = newNode;

            // Modify the newly inserted node.
            newNode.Next = node;
            newNode.Prev = prev;

            // Modify the former previous node of the given node.
            prev.Next = newNode;
        }

        // Insert after a given node.
        static private void InsertAfter(DoubleNode node, DoubleNode newNode)
        {
            DoubleNode next = node.Next; // keep the current next node of the given node

            // Modify the given node.
            node.Next = newNode;

            // Modify the newly inserted node.
            newNode.Next = next;
            newNode.Prev = node;

            // Modify the former next node of the given node.
            next.Prev = newNode;
        }

        // Remove a given node.
        static private void Remove(DoubleNode node)
        {
            if (first == null || node == null)
                return;

            // Does the list have only one node?
            if (first.Next == null)
            {
                first = null;
                return;
            }

            // Are we removing the first node?
            if (node.Prev == null)
            {
                first = first.Next; // we know that first.Next is not null because the list has at least two nodes 
                first.Prev = null;
                return;
            }

            // Are we removing the last node?
            if (node.Next == null)
            {
                node.Prev.Next = null; // we know that node.Prev is not null because the list has at least two nodes 
                return;
            }

            // node has both Prev and Next

            node.Prev.Next = node.Next;
            node.Next.Prev = node.Prev;

            node = node.Next;
        }

        // ShowItems traverses all the items in the list.
        static private void ShowItems()
        {
            for (DoubleNode node = first; node != null; node = node.Next)
            {
                Console.WriteLine("{0}: {1}-{0}-{2}", 
                    node.Item.ToString(), 
                    (node.Prev != null ? node.Prev.Item.ToString() : "."),
                    (node.Next != null ? node.Next.Item.ToString() : ".")
                    );
            }
        }

        // PopulateList returns a reference to the first element.
        static private void PopulateList()
        {
            string[] arr = { "A", "B", "C", "D" };

            DoubleNode prev = null;

            foreach (string s in arr)
            {
                var node = new DoubleNode();
                node.Item = s;

                if (prev != null)
                {
                    prev.Next = node;
                    node.Prev = prev;
                }
                else
                {
                    first = node;
                }
                
                prev = node;
            }
        }

        private class DoubleNode
        {
            public T Item { get; set; }
            public DoubleNode Prev { get; set; }
            public DoubleNode Next { get; set; }

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

Output:

A: .-A-B
B: A-B-C
C: B-C-D
D: C-D-.
InsertFirst("X")
X: .-X-A
A: X-A-B
B: A-B-C
C: B-C-D
D: C-D-.
InsertLast("Y")
X: .-X-A
A: X-A-B
B: A-B-C
C: B-C-D
D: C-D-Y
Y: D-Y-.
RemoveFirst()
A: .-A-B
B: A-B-C
C: B-C-D
D: C-D-Y
Y: D-Y-.
RemoveLast()
A: .-A-B
B: A-B-C
C: B-C-D
D: C-D-.
InsertBefore("C", "*")
A: .-A-B
B: A-B-*
*: B-*-C
C: *-C-D
D: C-D-.
InsertAfter("C", "#")
A: .-A-B
B: A-B-*
*: B-*-C
C: *-C-#
#: C-#-D
D: #-D-.
Remove("C")
A: .-A-B
B: A-B-*
*: B-*-#
#: *-#-D
D: #-D-.