What is a singly linked list

Singly linked list is a sequence of data structures (nodes), which are connected together through links. Node is a data entity that contains data of any type and a reference to another node.

A linked list can be represented as railway carriages connected to each other:

A linked list implements several basic operations:

• AddFirst inserts a new node at the beginning of the linked list
• AddLast inserts a new node at the end of the linked list
• RemoveFirst removes a new node from the beginning of the linked list

Linked list node can be created as a nested class:

    private sealed class Node
    {
        /// <summary>
        /// Store value
        /// </summary>
        public T Value;

        /// <summary>
        /// Reference to a next node
        /// </summary>
        public Node Next;
    }

AddFirst method:

    /// <summary>
    /// Add at the beginning
    /// </summary>
    public void AddFirst(T value)
    {
        var node = new Node
        {
            Value = value,
            Next = _head
        };

        _head = node;
    }

AddLast method:

    /// <summary>
    /// Add at the end
    /// </summary>
    public void AddLast(T value)
    {
        var node = new Node
        {
            Value = value
        };
        if (_head == null)
        {
            _head = node;
        }
        else
        {
            Node current = _head;
            while (current.Next != null)
            {
                current = current.Next;
            }

            current.Next = node;
        }
    }

RemoveFirst method:

    /// <summary>
    /// Remove from the beginning
    /// </summary>
    public T RemoveFirst()
    {
        if (_head == null)
        {
            throw  new NullReferenceException();
        }

        T result = _head.Value;
        _head = _head.Next;
        return result;
    }

Full implementation:

    public class SinglyLinkedList<T>
    {
        private Node _head;

        public void AddFirst(T value)
        {
            var node = new Node
            {
                Value = value,
                Next = _head
            };

            _head = node;
        }

        public void AddLast(T value)
        {
            var node = new Node
            {
                Value = value
            };
            if (_head == null)
            {
                _head = node;
            }
            else
            {
                Node current = _head;
                while (current.Next != null)
                {
                    current = current.Next;
                }

                current.Next = node;
            }
        }

        public T RemoveFirst()
        {
            if (_head == null)
            {
                throw  new NullReferenceException();
            }

            T result = _head.Value;
            _head = _head.Next;
            return result;
        }


        private sealed class Node
        {
            public T Value;

            public Node Next;
        }
    }