Linked Lists

Here is one more example of a linked list. This time also, the list allows you to add an item to the beginning or the end of the list:

using System;

public class Node<T>
{
    public T Value { get; set; }
    public Node<T> Next { get; set; }
}

public class LinkedList<T>
{
    private Node<T> begin;
    public Node<T> end;
    private int size;

    public LinkedList()
    {
        begin = default(Node<T>); // null;
        end = default(Node<T>); // null;
        size = 0;
    }

    public int Count
    {
        get { return size; }
    }

    public bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            return false;
        }
    }

    public Node<T> First
    {
        get
        {
            if (begin == null ) // return null;
                throw new NullReferenceException("There is no item in the collection");
            else
            {
                Node<T> temp = null; // default(T);

                Node<T> current = begin;
                while (current != null)
                {
                    temp = current;
                    current = current.Next;
                }
                return temp;
            }
        }
        set
        {
            begin = value;
        }
    }

    public Node<T> Last
    {
        get
        {
            return begin;
        }
        set
        {
            end = value;
        }
    }

    public void AddFirst(Node<T> item)
    {
        // Get a reference to the node we want to add
        Node<T> current = item;

        // If the list is currently empty, specify that the first
        // and the last are the same and they will receive the argument
        if (begin == null)
            begin = end = current;
        else // If there is already at least one item in the collection
        {
            // Get a reference to the current first item
            Node<T> first = this[0];
            // Get the next item to the first and assign it
            // to the next item of the argument
            current.Next = first.Next;
            // Replace the next item of the first with the argument
            first.Next = current;
        }

        // Increase the count of items
        size++;
    }

    public void AddLast(Node<T> item)
    {
        // Get a reference to the new item that will be added
        // and assign the argument to that reference
        Node<T> current = item;

        // Indicate that the first node will become next to the new item
        current.Next = begin;
        // Indicate that the new item becomes the first of the collection
        begin = current;

        // Increase the count of items
        size++;
    }

    public void DeleteFirst()
    {
        if (begin == null)
            return; // throw new NullReferenceException("The list is currently empty");

        Node<T> current = begin.Next;

        begin.Next = current;
        size--;
    }

    public void DeleteLast()
    {
        if (begin == null)
            return; // throw new NullReferenceException("The list is currently empty");
        else
        {
            Node<T> current = new Node<T>();
            Node<T> lastItem = this[size];

            current   = lastItem.Next;
            lastItem.Next = current.Next;

            size--;
        }
    }

    public void Insert(Node<T> item, int index)
    {
        if (index == 0)
            AddFirst(item);
        else if (index >= size)
        {
            // Is the user passes an index higher than the total number of items,
            // instead of throwing an exception,
            // we will add the item to the end of the list
            AddLast(item);
        }
        else
        {
            Node<T> current = item;

            Node<T> itemAtIndex = this[index];
            current.Next = itemAtIndex.Next;
            itemAtIndex.Next = current;
            size++;
        }
    }

    public Node<T> this[int index]
    {
        get
        {
            Node<T> current = begin;

            for (int i = size - 1; (i > index) && (current != null); i--)
                current = current.Next;
            return current;
        }
    }
}

public class Exercise
{
    static int Main(string[] args)
    {
        Node<string> name = null;
        LinkedList<string> employees = new LinkedList<string>();

        name = new Node<string>();
        name.Value = "Alan Baxter";
        employees.AddFirst(name);

        name = new Node<string>();
        name.Value = "Joan Bramble";
        employees.AddFirst(name);

        name = new Node<string>();
        name.Value = "Paul Bertrand Yamaguchi";
        employees.AddFirst(name);

        name = new Node<string>();
        name.Value = "Lionel Berg";
        employees.AddLast(name);

        name = new Node<string>();
        name.Value = "Flora Bruze";
        employees.AddFirst(name);

        //name = new Node<string>();
        //name.Value = "Mathew Jeremy Williams";
        //employees.Insert(name, 3);

        name = new Node<string>();
        name.Value = "Christopher Fox";
        employees.AddFirst(name);

        name = new Node<string>();
        name.Value = "Holly Madsen";
        employees.AddFirst(name);

        for (int i = 0; i < employees.Count; i++)
            Console.WriteLine("Name {0}: {1}", i + 1, employees[i].Value);

        Console.WriteLine("----------------------------------");

        employees.DeleteFirst();

        for (int i = 0; i < employees.Count; i++)
            Console.WriteLine("Name {0}: {1}", i + 1, employees[i].Value);

        //Console.WriteLine("----------------------------------");

        //employees.DeleteLast();

        //for (int i = 0; i < employees.Count; i++)
        //    Console.WriteLine("Name {0}: {1}", i + 1, employees[i].Value);

        Console.WriteLine("----------------------------------");
        Console.WriteLine("First Item: {0}", employees.First.Value);
        Console.WriteLine("Last Item:  {0}", employees.Last.Value);
        Console.WriteLine("----------------------------------");

        return 0;
    }
}

This would produce:

Name 1: Holly Madsen
Name 2: Christopher Fox
Name 3: Flora Bruze
Name 4: Paul Bertrand Yamaguchi
Name 5: Joan Bramble
Name 6: Alan Baxter
Name 7: Lionel Berg
----------------------------------
Name 1: Christopher Fox
Name 2: Flora Bruze
Name 3: Paul Bertrand Yamaguchi
Name 4: Joan Bramble
Name 5: Alan Baxter
Name 6: Lionel Berg
----------------------------------
First Item: Holly Madsen
Last Item:  Lionel Berg
----------------------------------
Press any key to continue . . .