创建两个类

SingleLinkedList<T>

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace DevGuideToCollections
{
    /// <summary>
    /// Represents a strongly typed single linked list.
    /// </summary>
    /// <typeparam name="T">Specifies the type of elements in the list.</typeparam>
    [DebuggerDisplay("Count={Count}")]
    [DebuggerTypeProxy(typeof(ArrayDebugView))]
    public class SingleLinkedList<T>
    {
        int m_count;
        SingleLinkedListNode<T> m_head;
        SingleLinkedListNode<T> m_tail;
        int m_updateCode;

        /// <summary>
        /// Initializes a new instance of the SingleLinkedList(T) class that is empty.
        /// </summary>
        public SingleLinkedList()
        {
        }

        /// <summary>
        /// Initializes a new instance of the SingleLinkedList(T) class that contains the items in the list.
        /// </summary>
        /// <param name="items">Adds the items to the end of the SingleLinkedList(T).</param>
        public SingleLinkedList(IEnumerable<T> items)
        {
            foreach (T item in items)
            {
                AddToEnd(item);
            }
        }

        /// <summary>
        /// States if the SingleLinkedList(T) is empty.
        /// </summary>
        public bool IsEmpty
        {
            get { return m_count <= 0; }
        }

        /// <summary>
        /// Gets the number of nodes actually contained in the SingleLinkedList(T).
        /// </summary>
        public int Count
        {
            get { return m_count; }
        }

        /// <summary>
        /// Gets the head node in the SingleLinkedList(T).
        /// </summary>
        public SingleLinkedListNode<T> Head
        {
            get { return m_head; }
            private set { m_head = value; }
        }

        /// <summary>
        /// Gets the tail node in the SingleLinkedList(T).
        /// </summary>
        public SingleLinkedListNode<T> Tail
        {
            get { return m_tail; }
            private set { m_tail = value; }
        }

        /// <summary>
        /// Checks if the specified data is present in the SingleLinkedList(T).
        /// </summary>
        /// <param name="data">The data to look for.</param>
        /// <returns>True if the data is found, false otherwise.</returns>
        public bool Contains(T data)
        {
            return Find(data) != null;
        }

        /// <summary>
        /// Removes all items from the SingleLinkedList(T).
        /// </summary>
        public void Clear()
        {
            SingleLinkedListNode<T> tmp;

            // Clean up the items in the list
            for (SingleLinkedListNode<T> node = m_head; node != null; )
            {
                tmp = node.Next;

                // Change the count and head pointer in case we throw an exception.
                // this way the node is removed before we clear the data
                m_head = tmp;
                --m_count;

                // Erase the contents of the node
                node.Next = null;
                node.Owner = null;

                // Move to the next node
                node = tmp;
            }

            if (m_count <= 0)
            {
                m_head = null;
                m_tail = null;
            }

            ++m_updateCode;
        }

        /// <summary>
        /// Locates the first node that contains the specified data.
        /// </summary>
        /// <param name="data">The data to find.</param>
        /// <returns>The node that contains the specified data, null otherwise.</returns>
        public SingleLinkedListNode<T> Find(T data)
        {
            if (IsEmpty)
            {
                return null;
            }

            EqualityComparer<T> comparer = EqualityComparer<T>.Default;

            // Traverse the list from the Head to Tail.
            for (SingleLinkedListNode<T> curr = Head; curr != null; curr = curr.Next)
            {
                // Return the node we are currently on if it contains the data we are looking for.
                if (comparer.Equals(curr.Data, data))
                {
                    return curr;
                }
            }

            return null;
        }


        /// <summary>
        /// Adds the specified value to the SingleLinkedListNode(T) after the specified node.
        /// </summary>
        /// <param name="node">The node to add the value after.</param>
        /// <param name="value">The value to add.</param>
        /// <returns>The newly created node that holds the value.</returns>
        public SingleLinkedListNode<T> AddAfter(SingleLinkedListNode<T> node, T value)
        {
            SingleLinkedListNode<T> newNode = new SingleLinkedListNode<T>(this, value);
            AddAfter(node, newNode);
            return newNode;
        }

        /// <summary>
        /// Adds the specified newNode to the SingleLinkedListNode(T) after the specified node.
        /// </summary>
        /// <param name="node">The node to add the newNode after.</param>
        /// <param name="newNode">The node to add.</param>
        public void AddAfter(SingleLinkedListNode<T> node, SingleLinkedListNode<T> newNode)
        {
            if (node == null)
            {
                throw new ArgumentNullException("node");
            }
            if (newNode == null)
            {
                throw new ArgumentNullException("newNode");
            }
            if (node.Owner != this)
            {
                throw new InvalidOperationException("node is not owned by this list");
            }
            if (newNode.Owner != this)
            {
                throw new InvalidOperationException("newNode is not owned by this list");
            }

            // The newly added node becomes the tail if you are adding after the tail
            if (m_tail == node)
            {
                m_tail = newNode;
            }

            newNode.Next = node.Next;
            node.Next = newNode;
            ++m_count;
            ++m_updateCode;
        }

        /// <summary>
        /// Adds the specified value to the SingleLinkedListNode(T) before the specified node.
        /// </summary>
        /// <param name="node">The node to add the value before.</param>
        /// <param name="value">The value to add.</param>
        /// <returns>The newly created node that holds the value.</returns>
        public SingleLinkedListNode<T> AddBefore(SingleLinkedListNode<T> node, T value)
        {
            SingleLinkedListNode<T> newNode = new SingleLinkedListNode<T>(this, value);
            AddBefore(node, newNode);
            return newNode;
        }

        /// <summary>
        /// Adds the specified newNode to the SingleLinkedListNode(T) before the specified node.
        /// </summary>
        /// <param name="node">The node to add the newNode before.</param>
        /// <param name="newNode">The node to add.</param>
        public void AddBefore(SingleLinkedListNode<T> node, SingleLinkedListNode<T> newNode)
        {
            if (node == null)
            {
                throw new ArgumentNullException("node");
            }
            if (newNode == null)
            {
                throw new ArgumentNullException("newNode");
            }
            if (node.Owner != this)
            {
                throw new InvalidOperationException("node is not owned by this list");
            }
            if (newNode.Owner != this)
            {
                throw new InvalidOperationException("newNode is not owned by this list");
            }

            if (m_head == node)
            {
                newNode.Next = m_head;
                m_head = newNode;
            }
            else 
            {
                // We have to find the node before the one we are inserting in front of

                SingleLinkedListNode<T> beforeNode = m_head;

                while (beforeNode != null && beforeNode.Next != node)
                {
                    beforeNode = beforeNode.Next;
                }

                // We should always find node in the list
                if (beforeNode == null)
                {
                    throw new InvalidOperationException("Something went wrong");
                }

                newNode.Next = node;
                beforeNode.Next = newNode;
            }


            ++m_count;
            ++m_updateCode;
        }

        /// <summary>
        /// Adds the value to the beginning of the SingleLinkedList(T).
        /// </summary>
        /// <param name="value">The value to add to the beginning of the SingleLinkedList(T).</param>
        /// <returns>The newly created node that is holding the value.</returns>
        public SingleLinkedListNode<T> AddToBeginning(T value)
        {
            SingleLinkedListNode<T> newNode = new SingleLinkedListNode<T>(this, value);

            if (IsEmpty)
            {
                m_head = newNode;
                m_tail = newNode;
            }
            else
            {
                newNode.Next = m_head;
                m_head = newNode;
            }

            ++m_count;
            ++m_updateCode;

            return newNode;
        }

        /// <summary>
        /// Adds the value to the end of the SingleLinkedList(T).
        /// </summary>
        /// <param name="value">The value to add to the end of the SingleLinkedList(T).</param>
        /// <returns>The newly created node that is holding the value.</returns>
        public SingleLinkedListNode<T> AddToEnd(T value)
        {
            SingleLinkedListNode<T> newNode = new SingleLinkedListNode<T>(this, value);

            if (IsEmpty)
            {
                m_head = newNode;
                m_tail = newNode;
            }
            else
            {
                m_tail.Next = newNode;
                m_tail = newNode;
            }

            ++m_count;
            ++m_updateCode;

            return newNode;
        }

        /// <summary>
        /// Removes the first occurrence of the specified item from the SingleLinkedList(T).
        /// </summary>
        /// <param name="item">The item to remove from the SingleLinkedList(T).</param>
        /// <returns>True if an item was removed, false otherwise.</returns>
        public bool Remove(T item)
        {
            return Remove(item, false);
        }

        /// <summary>
        /// Removes the first or all occurrences of the specified item from the SingleLinkedList(T).
        /// </summary>
        /// <param name="item">The item to remove from the SingleLinkedList(T).</param>
        /// <param name="alloccurrences">True if all nodes should be removed that contain the specified item, False otherwise</param>
        /// <returns>True if an item was removed, false otherwise.</returns>
        public bool Remove(T item, bool alloccurrences)
        {
            if (IsEmpty)
            {
                return false;
            }

            SingleLinkedListNode<T> prev = null;
            SingleLinkedListNode<T> curr = Head;
            bool removed = false;

            EqualityComparer<T> comparer = EqualityComparer<T>.Default;

            // Start traversing the list at the head
            while (curr != null)
            {
                // Check to see if the current node contains the data we are trying to delete
                if (!comparer.Equals(curr.Data, item))
                {
                    // Assign the current node to the previous node and the previous node to the current node
                    prev = curr;
                    curr = curr.Next;
                    continue;
                }

                // Create a pointer to the next node in the previous node
                if (prev != null)
                {
                    prev.Next = curr.Next;
                }

                if (curr == Head)
                {
                    // If the current node is the head we will have to assign the next node as the head
                    Head = curr.Next;
                }

                if (curr == Tail)
                {
                    // If the current node is the tail we will have to assign the previous node as the tail
                    Tail = prev;
                }

                // Save the pointer for clean up later
                SingleLinkedListNode<T> tmp = curr;

                // Advance the current to the next node
                curr = curr.Next;

                // Since the node will no longer be used clean up the pointers in it
                tmp.Next = null;
                tmp.Owner = null;

                // Decrement the counter since we have removed a node
                --m_count;

                removed = true;

                if (!alloccurrences)
                {
                    break;
                }
            }

            if (removed)
            {
                ++m_updateCode;
            }

            return removed;
        }

        /// <summary>
        /// Removes the specified node from the SingleLinkedList(T).
        /// </summary>
        /// <param name="node">The node to remove from the SingleLinkedList(T).</param>
        public void Remove(SingleLinkedListNode<T> node)
        {
            if (IsEmpty)
            {
                return;
            }

            if (node == null)
            {
                throw new ArgumentNullException("node");
            }

            if (node.Owner != this)
            {
                throw new InvalidOperationException("The node doesn't belong to this list.");
            }

            SingleLinkedListNode<T> prev = null;
            SingleLinkedListNode<T> curr = Head;

            // Find the node located before the specified node by traversing the list.
            while (curr != null && curr != node)
            {
                prev = curr;
                curr = curr.Next;
            }

            // The node has been found if the current node equals the node we are looking for
            if (curr == node)
            {
                // Assign the head to the next node if the specified node is the head
                if (m_head == node)
                {
                    m_head = node.Next;
                }

                // Assign the tail to the previous node if the specified node is the tail
                if (m_tail == node)
                {
                    m_tail = prev;
                }

                // Set the previous node next reference to the removed nodes next reference.
                if (prev != null)
                {
                    prev.Next = curr.Next;
                }

                // Null out the removed nodes next pointer to be safe.
                node.Next = null;
                node.Owner = null;

                --m_count;
                ++m_updateCode;
            }
        }

        /// <summary>
        /// Copies the elements of the SingleLinkedList(T) to a new array.
        /// </summary>
        /// <returns>An array containing copies of the elements of the SingleLinkedList(T).</returns>
        public T[] ToArray()
        {
            T[] retval = new T[m_count];

            int index = 0;
            for (SingleLinkedListNode<T> i = Head; i != null; i = i.Next)
            {
                retval[index] = i.Data;
                ++index;
            }

            return retval;
        }
    }
}

SingleLinkedListNode<T>

 

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace DevGuideToCollections
{
    /// <summary>
    /// Represents a node in a SingleLinkedList(T).
    /// </summary>
    /// <typeparam name="T">Specifies the type of data in the node.</typeparam>
    [DebuggerDisplay("Data={Data}")]
    public class SingleLinkedListNode<T>
    {
        SingleLinkedList<T> m_owner;
        SingleLinkedListNode<T> m_next;
        T m_data;

        /// <summary>
        /// Initializes a new instance of the SingleLinkedList(T) class with the specified data.
        /// </summary>
        /// <param name="data">The data that this node will contain.</param>
        public SingleLinkedListNode(T data)
        {
            m_data = data;
        }

        /// <summary>
        /// Initializes a new instance of the SingleLinkedList(T) class with the specified data and owner.
        /// </summary>
        /// <param name="data">The data that this node will contain.</param>
        internal SingleLinkedListNode(SingleLinkedList<T> owner, T data)
        {
            m_data = data;
            m_owner = owner;
        }

        /// <summary>
        /// Returns the next node.
        /// </summary>
        public SingleLinkedListNode<T> Next
        {
            get { return m_next; }
            internal set { m_next = value; }
        }

        /// <summary>
        /// Gets or sets the owner of the node.
        /// </summary>
        internal SingleLinkedList<T> Owner
        {
            get { return m_owner; }
            set { m_owner = value; }
        }

        /// <summary>
        /// Gets the data contained in the node.
        /// </summary>
        public T Data
        {
            get { return m_data; }
            internal set { m_data = value; }
        }
    }
}

 

测试方法

 

 

        static void TestSingleLinkedList()
        {
            SingleLinkedList<int> list = new SingleLinkedList<int>();

            //Testing add
            list.AddToEnd(6);
            list.AddToEnd(9);
            SingleLinkedListNode<int> nodeAddAfter = list.AddToEnd(5);
            System.Diagnostics.Debug.Assert(list.Count == 3);

            SingleLinkedListNode<int> nodeAddBefore1 = list.AddToBeginning(4);
            list.AddToBeginning(1);
            list.AddBefore(nodeAddBefore1, 3);
            System.Diagnostics.Debug.Assert(list.Count == 6);

            SingleLinkedListNode<int> nodeAddBefore2 = list.AddToEnd(7);
            list.AddAfter(nodeAddAfter, 6);
            list.AddBefore(nodeAddBefore2, 9);
            list.AddBefore(nodeAddBefore2, 9);
            System.Diagnostics.Debug.Assert(list.Count == 10);

            // Check the links
            SingleLinkedListNode<int> node = list.Head;
            System.Diagnostics.Debug.Assert(node.Data == 1);
            node = node.Next;
            System.Diagnostics.Debug.Assert(node.Data == 3);
            node = node.Next;
            System.Diagnostics.Debug.Assert(node.Data == 4);
            node = node.Next;
            System.Diagnostics.Debug.Assert(node.Data == 6);
            node = node.Next;
            System.Diagnostics.Debug.Assert(node.Data == 9);
            node = node.Next;
            System.Diagnostics.Debug.Assert(node.Data == 5);
            node = node.Next;
            System.Diagnostics.Debug.Assert(node.Data == 6);
            node = node.Next;
            System.Diagnostics.Debug.Assert(node.Data == 9);
            node = node.Next;
            System.Diagnostics.Debug.Assert(node.Data == 9);
            node = node.Next;
            System.Diagnostics.Debug.Assert(node.Data == 7);

            // Deleting the first 6 from the list
            list.Remove(6, false);
            System.Diagnostics.Debug.Assert(list.Contains(6));
            //System.Diagnostics.Debug.Assert(list[5] == 6);
            System.Diagnostics.Debug.Assert(list.Count == 9);

            // Deleting all 9s from the list
            list.Remove(9, true);
            System.Diagnostics.Debug.Assert(!list.Contains(9));
            System.Diagnostics.Debug.Assert(list.Count == 6);

            // Check the DebugView method
            ArrayDebugView view = new ArrayDebugView(list);
            object[] values = view.Items;
            System.Diagnostics.Debug.Assert(values.Length == list.Count);
            int i = 0;
            for (SingleLinkedListNode<int> tmpNode = list.Head; tmpNode != null; tmpNode = tmpNode.Next )
            {
                System.Diagnostics.Debug.Assert((int)values[i++] == tmpNode.Data);
            }

            // Testing clear
            list.Clear();
            System.Diagnostics.Debug.Assert(list.Count == 0);
            list.AddToEnd(99);
            list.AddToBeginning(66);
            list.AddToEnd(199);
            System.Diagnostics.Debug.Assert(list.Head.Data == 66);
            System.Diagnostics.Debug.Assert(list.Head.Next.Data == 99);
            System.Diagnostics.Debug.Assert(list.Tail.Data == 199);

            // Test removing
            System.Diagnostics.Debug.Assert(list.Remove(66));
            System.Diagnostics.Debug.Assert(!list.Remove(68));
        }