数据结构之基于无序链表的集合和映射

   #region 链表类
    public class MyLinkedList<T>
    {
        //当前链表类记录这个链表的头部类
        private Node head;
        //链表的节点数量
        private int N;
        public MyLinkedList()
        {
            N = 0;
            //因为一开始链表没有元素，所以头部节点指向空。
            head = null;
        }



        /// <summary>
        /// 链表节点数量
        /// </summary>
        public int Count
        {
            get { return N; }
        }
        /// <summary>
        /// 链表是否为空
        /// </summary>
        public bool IsEmpty
        {
            get { return N == 0; }
        }

        public void Add(int index, T e)
        {
            if (index < 0 || index > N)
            {
                throw new Exception("非法索引");
            }

            if (index == 0)
            {
                //新的头部节点
                //1:添加新节点
                //Node node = new Node(e);
                ////2：将新添加的头结点的箭头指向原先头结点
                //node.next = head;
                ////3：现在的头结点信息赋给类的头结点字段，记录下来。
                //head = node;
                //其实上面三步可以结合到一步中，
                head = new Node(e, head);
            }
            else
            {
                //添加非头部节点
                //1.需要找到插入位置的上一个节点，对于链表来说就要从头部节点开始一步一步的查找了
                Node pre = head;
                //一步一步遍历找到前一个节点信息
                for (int i = 0; i < index - 1; i++)
                {
                    pre = pre.next;
                }
                //1：将前一节点的下一节点信息赋值给当前节点对象的下一节点字段，目的是为了让当前节点能够链接到下一节点
                Node node = new Node(e);
                node.next = pre.next;
                //2：前一节点链接到新插入的节点 此时链表已经重新完成
                pre.next = node;
                //上面代码也可以合成一句
                //   pre.next = new Node(e, pre.next);

            }
            //链表的元素加一
            N++;
        }

        public void AddFirst(T e)
        {
            Add(0, e);
        }

        public void AddLast(T e)
        {
            Add(N, e);
        }

        /// <summary>
        /// 节点类  不让外部知道此类，设为私有
        /// </summary>
        private class Node
        {
            //当前节点
            public T e;
            //当前节点的下一节点
            public Node next;
            public Node(T e, Node next)
            {
                this.e = e;
                this.next = next;
            }
            public Node(T e)
            {
                this.e = e;
            }

        }


        public T Get(int index)
        {
            if (index < 0 || index >= N)
            {
                throw new Exception("非法索引");
            }

            Node currentNode = head;//从头结点开始查找
            for (int i = 0; i < index; i++)
            {
                currentNode = currentNode.next;
            }

            return currentNode.e;
        }


        public T GetFirst()
        {
            return Get(0);
        }
        public T GetLast()
        {
            return Get(N - 1);
        }

        /// <summary>
        /// 修改
        /// </summary>
        /// <param name="index"></param>
        /// <param name="e"></param>
        /// <returns></returns>
        public void Set(int index, T e)
        {
            if (index < 0 || index >= N)
            {
                throw new Exception("非法索引");
            }

            Node currentNode = head;//从头结点开始查找
            for (int i = 0; i < index; i++)
            {
                currentNode = currentNode.next;
            }

            currentNode.e = e; ;
        }
        /// <summary>
        /// 查找链表中是否存在此元素
        /// </summary>
        /// <param name="e"></param>
        /// <returns></returns>
        public bool Contains(T e)
        {
            Node current = head;
            while (current != null)
            {
                if (current.e.Equals(e))
                {
                    return true;
                }

                current = current.next;
            }

            return false;
        }
        /// <summary>
        /// 可以重写tostring打印方法
        /// 打印出链表信息
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            StringBuilder stringBuilder = new StringBuilder();
            Node cur = head;
            while (cur != null)
            {
                stringBuilder.Append(cur.e + "->");
                cur = cur.next;
            }
            stringBuilder.Append("null");
            return stringBuilder.ToString();

        }

        #region 删除节点

        public T Remove(int index)
        {
            if (index < 0 || index > N)
            {
                throw new Exception("非法索引");
            }

            if (index == 0)
            {
                Node delNode = head;
                //直接将原头部节点指向的下一节点的信息存储到头部节点的字段上，直接这样就能删除原头部节点了
                head = delNode.next;
                N--;
                return delNode.e;
            }
            else
            {
                Node pre = head;
                //找到删除节点的前一节点信息
                for (int i = 0; i < index - 1; i++)
                {
                    pre = pre.next;
                }
                Node delNode = pre.next;
                //1：z将前一节点的指向做更改
                pre.next = delNode.next;
                N--;
                return delNode.e;
            }
        }

        public T RemoveFirst()
        {
            return Remove(N);
        }

        #endregion
        #region 删除节点  根据值节点查找

        public void Remove(T e)
        {
            if (head == null)
            {
                return;
            }

            if (head.e.Equals(e))
            {
                //删除的是头结点
                head = head.next;
                N--;
            }
            else
            {
                Node current = head;
                Node pre = null;
                while (current != null)
                {
                    if (current.e.Equals(e))
                    {
                        break;
                    }

                    pre = current;
                    current = current.next;

                }

                if (current != null)
                {
                    pre.next = current.next.next;
                    N--;
                }
            }

        }

        #endregion
    }
    #endregion