team-learning-program/DataStructureAndAlgorithm/02 线性表.md

# 02 线性表

知识结构：

---

1. 线性表的定义与操作

1.1 线性表的定义

线性表（Linear List）是由$n (n≥0)$个相同类型的数据元素$a_0,a_1,⋯,a_{n-1}$组成的序列。即表中除首尾元素外，其它元素有且仅有一个直接前驱和直接后继。首元素仅有一个直接后继，尾元素仅有一个直接前驱，记为：$(a_0,a_1,⋯,a_{n-1})$。

表中数据元素的个数称为表的长度。

例1：字母表

(a,b,c,d,\dots,z)

例2：学生成绩表

1.2 线性表的操作

• 随机存取：获取或设置指定索引处的数据元素值。（支持索引器）
• 插入操作：将数据元素值插入到指定索引处。
• 移除操作：移除线性表指定索引处的数据元素。
• 查找操作：寻找具有特征值域的结点并返回其下标。
• 得到表长：获取线性表中实际包含数据元素的个数。
• 是否为空：判断线性表中是否包含数据元素。
• 清空操作：移除线性表中的所有数据元素。

using System;

namespace LinearStruct
{
    /// <summary>
    /// 线性表的抽象数据类型
    /// </summary>
    /// <typeparam name="T">线性表中元素的类型</typeparam>
    public interface ILinearList<T> where T : IComparable<T>
    {
        /// <summary>
        /// 获取线性表中实际包含元素的个数
        /// </summary>
        int Length { get; }

        /// <summary>
        /// 获取或设置指定索引处的元素
        /// </summary>
        /// <param name="index">要获取或设置的元素从零开始的索引</param>
        /// <returns>指定索引处的元素</returns>
        T this[int index] { get; set; }

        /// <summary>
        /// 判断线性表中是否包含元素
        /// </summary>
        /// <returns>如果包含元素返回false,否则返回true.</returns>
        bool IsEmpty();

        /// <summary>
        /// 将元素插入到指定索引处
        /// </summary>
        /// <param name="index">从零开始的索引,应在该位置插入data.</param>
        /// <param name="data">要插入的元素</param>
        void Insert(int index, T data);

        /// <summary>
        /// 移除线性表指定索引处的元素
        /// </summary>
        /// <param name="index">要移除元素从0开始的索引</param>
        void Remove(int index);

        /// <summary>
        /// 在线性表中寻找元素data.
        /// </summary>
        /// <param name="data">要寻找的元素</param>
        /// <returns>如果存在返回该元素在线性表中的位置,否则返回-1.</returns>
        int Search(T data);

        /// <summary>
        /// 从线性表中移除所有元素
        /// </summary>
        void Clear();
    }
}

---

2. 线性表的顺序存储与实现

定义：利用顺序存储结构（即利用数组）实现的线性表，称为顺序表。

特点：逻辑结构与存储结构相同；具有随机存取的特点。

实现：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 用顺序存储结构实现的线性表
    /// </summary>
    /// <typeparam name="T">顺序表中元素的类型</typeparam>
    public class SeqList<T> : ILinearList<T> where T : IComparable<T>
    {
        /// <summary>
        /// 数据集合
        /// </summary>
        protected readonly T[] Dataset;

        /// <summary>
        /// 获取SeqList中实际包含元素的个数
        /// </summary>
        public int Length { get; private set; }

        /// <summary>
        /// 获取SeqList中最多包含元素的个数
        /// </summary>
        public int MaxSize { get; }

        /// <summary>
        /// 初始化SeqList类的新实例
        /// </summary>
        /// <param name="max">SeqList中最多包含元素的个数</param>
        public SeqList(int max)
        {
            if (max <= 0)
                throw new ArgumentOutOfRangeException();
            MaxSize = max;
            Dataset = new T[MaxSize];
            Length = 0;
        }

        /// <summary>
        /// 获取或设置指定索引处的元素
        /// </summary>
        /// <param name="index">要获得或设置的元素从零开始的索引</param>
        /// <returns>指定索引处的元素</returns>
        public T this[int index]
        {
            get
            {
                if (index < 0 || index > Length - 1)
                    throw new IndexOutOfRangeException();
                return Dataset[index];
            }
            set
            {
                if (index < 0 || index > Length - 1)
                    throw new IndexOutOfRangeException();
                Dataset[index] = value;
            }
        }

        /// <summary>
        /// 判断SeqList中是否包含元素
        /// </summary>
        /// <returns>如果包含元素返回false,否则返回true.</returns>
        public bool IsEmpty()
        {
            return Length == 0;
        }

        /// <summary>
        /// 将元素插入到指定索引处
        /// </summary>
        /// <param name="index">从零开始的索引,应在该位置插入data.</param>
        /// <param name="data">要插入的元素</param>
        public void Insert(int index, T data)
        {
            if (index < 0 || index > Length)
                throw new IndexOutOfRangeException();
            if (Length == MaxSize)
                throw new Exception("达到最大值");

            for (int i = Length; i > index; i--)
            {
                Dataset[i] = Dataset[i - 1];
            }
            Dataset[index] = data;
            Length++;
        }

        /// <summary>
        /// 移除SeqList指定索引处的元素
        /// </summary>
        /// <param name="index">要移除元素从0开始的索引</param>
        public void Remove(int index)
        {
            if (index < 0 || index > Length - 1)
                throw new IndexOutOfRangeException();

            for (int i = index; i < Length - 1; i++)
            {
                Dataset[i] = Dataset[i + 1];
            }
            Length--;
        }

        /// <summary>
        /// 在SeqList中寻找元素data.
        /// </summary>
        /// <param name="data">要寻找的元素</param>
        /// <returns>如果存在返回该元素在线性表中的位置,否则返回-1.</returns>
        public int Search(T data)
        {
            int i;
            for (i = 0; i < Length; i++)
            {
                if (Dataset[i].CompareTo(data) == 0)
                    break;
            }
            return i == Length ? -1 : i;
        }

        /// <summary>
        /// 从SeqList中移除所有元素
        /// </summary>
        public void Clear()
        {
            Length = 0;
        }
    }
}

应用：

using System;
using LinearStruct;

namespace ExampleList
{
    class Program
    {
        static void Main(string[] args)
        {
            ListTest(new SeqList<string>(500));
            // 2
            // a1
            // a3
        }

        private static void ListTest(ILinearList<string> lst)
        {
            lst.Insert(0, "a1");
            lst.Insert(1, "a2");
            lst.Insert(2, "a3");
            lst.Remove(1);
            Console.WriteLine(lst.Length);
            for (int i = 0; i < lst.Length; i++)
            {
                Console.WriteLine(lst[i]);
            }
        }
    }
}

---

3. 线性表的链式存储与实现

利用指针方式实现的线性表称为链表（单链表、循环链表、双向链表）。它不要求逻辑上相邻的数据元素在物理位置上也相邻，即：逻辑结构与物理结构可以相同也可以不相同。

例3：将线性表$(a_3,a_4,a_5)$以链表的形式存储。

3.1 单链表

定义：每个结点只含有一个链域（指针域）的链表。即：利用单链域的方式存储线性表的逻辑结构。

结构：

实现：

对结点的封装：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 单链表结点
    /// </summary>
    /// <typeparam name="T">结点中数据元素的类型</typeparam>
    public class SNode<T> where T : IComparable<T>
    {
        /// <summary>
        /// 获取或设置该结点的数据元素
        /// </summary>
        public T Data { get; set; }

        /// <summary>
        /// 获取或设置该结点的后继结点
        /// </summary>
        public SNode<T> Next { get; set; }

        /// <summary>
        /// 初始化SNode类的新实例
        /// </summary>
        /// <param name="data">该结点的数据元素</param>
        /// <param name="next">该结点的后继结点</param>
        public SNode(T data, SNode<T> next = null)
        {
            Data = data;
            Next = next;
        }
    }
}

对单链表的封装：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 用链式存储结构实现的线性表--单链表
    /// </summary>
    /// <typeparam name="T">单链表中元素的类型</typeparam>
    public class SLinkList<T> : ILinearList<T> where T : IComparable<T>
    {
        /// <summary>
        /// 存储头结点
        /// </summary>
        protected SNode<T> PHead { get; set; }

        /// <summary>
        /// 获取SLinkList中实际包含元素的个数
        /// </summary>
        public int Length { get; private set; }

        /// <summary>
        /// 初始化SLinkList类的新实例
        /// </summary>
        public SLinkList()
        {
            Length = 0;
            PHead = null;
        }

        /// <summary>
        /// 将元素插入到单链表的首部
        /// </summary>
        /// <param name="data">要插入的元素</param>
        public void InsertAtFirst(T data)
        {
            PHead = new SNode<T>(data, PHead);
            Length++;
        }

        /// <summary>
        /// 获得指定索引处的结点
        /// </summary>
        /// <param name="index">元素从零开始的索引</param>
        /// <returns>指定索引处的结点</returns>
        private SNode<T> Locate(int index)
        {
            if (index < 0 || index > Length - 1)
                throw new IndexOutOfRangeException();

            SNode<T> temp = PHead;
            for (int i = 0; i < index; i++)
            {
                temp = temp.Next;
            }
            return temp;
        }

        /// <summary>
        /// 将元素插入到单链表的尾部
        /// </summary>
        /// <param name="data">要插入的元素</param>
        public void InsertAtRear(T data)
        {
            if (PHead == null)
            {
                PHead = new SNode<T>(data);
            }
            else
            {
                Locate(Length - 1).Next = new SNode<T>(data);
            }
            Length++;
        }

        /// <summary>
        /// 获取或设置指定索引处的元素
        /// </summary>
        /// <param name="index">要获得或设置的元素从零开始的索引</param>
        /// <returns>指定索引处的元素</returns>
        public T this[int index]
        {
            get
            {
                if (index < 0 || index > Length - 1)
                    throw new IndexOutOfRangeException();
                return Locate(index).Data;
            }
            set
            {
                if (index < 0 || index > Length - 1)
                    throw new IndexOutOfRangeException();
                Locate(index).Data = value;
            }
        }

        /// <summary>
        /// 判断SLinkList中是否包含元素
        /// </summary>
        /// <returns>如果包含元素返回false,否则返回true.</returns>
        public bool IsEmpty()
        {
            return Length == 0;
        }

        /// <summary>
        /// 将元素插入到指定索引处
        /// </summary>
        /// <param name="index">从零开始的索引,应在该位置插入data.</param>
        /// <param name="data">要插入的元素</param>
        public void Insert(int index, T data)
        {
            if (index < 0 || index > Length)
                throw new IndexOutOfRangeException();
                
            if (index == 0)
            {
                InsertAtFirst(data);
            }
            else if (index == Length)
            {
                InsertAtRear(data);
            }
            else
            {
                SNode<T> temp = Locate(index - 1);
                temp.Next = new SNode<T>(data, temp.Next);
                Length++;
            }
        }

        /// <summary>
        /// 移除SLinkList指定索引处的元素
        /// </summary>
        /// <param name="index">要移除元素从0开始的索引</param>
        public void Remove(int index)
        {
            if (index < 0 || index > Length - 1)
                throw new IndexOutOfRangeException();
                
            if (index == 0)
            {
                PHead = PHead.Next;
            }
            else
            {
                SNode<T> temp = Locate(index - 1);
                temp.Next = temp.Next.Next;
            }
            Length--;
        }

        /// <summary>
        /// 在SLinkList中寻找元素data.
        /// </summary>
        /// <param name="data">要寻找的元素</param>
        /// <returns>如果存在返回该元素在线性表中的位置,否则返回-1.</returns>
        public int Search(T data)
        {
            int i;
            SNode<T> temp = PHead;
            for (i = 0; i < Length; i++)
            {
                if (temp.Data.CompareTo(data) == 0)
                    break;
                temp = temp.Next;
            }
            return i == Length ? -1 : i;
        }

        /// <summary>
        /// 从SLinkList中移除所有元素
        /// </summary>
        public void Clear()
        {
            PHead = null;
            Length = 0;
        }
    }
}

应用：

using System;
using LinearStruct;

namespace ExampleList
{
    class Program
    {
        static void Main(string[] args)
        {
            ListTest(new SLinkList<string>());
            // 2
            // a1
            // a3
        }

        private static void ListTest(ILinearList<string> lst)
        {
            lst.Insert(0, "a1");
            lst.Insert(1, "a2");
            lst.Insert(2, "a3");
            lst.Remove(1);
            Console.WriteLine(lst.Length);
            for (int i = 0; i < lst.Length; i++)
            {
                Console.WriteLine(lst[i]);
            }
        }
    }
}

3.2 循环链表

定义：是一种首尾相连的单链表。即：在单链表中，将尾结点的指针域null改为指向PHead，就得到单链形式的循环链表。

表现形式：

通常情况下，使用尾指针表示循环链表。

实现：

对循环链表的封装：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 用链式存储结构实现的线性表--循环链表
    /// </summary>
    /// <typeparam name="T">循环链表中元素的类型</typeparam>
    public class CLinkList<T> : ILinearList<T> where T : IComparable<T>
    {
        /// <summary>
        /// 存储尾部结点
        /// </summary>
        protected SNode<T> PRear { get; set; }

        /// <summary>
        /// 获取CLinkList中实际包含元素的个数
        /// </summary>
        public int Length { get; private set; }

        /// <summary>
        /// 获取或设置指定索引处的元素
        /// </summary>
        /// <param name="index">要获得或设置的元素从零开始的索引</param>
        /// <returns>指定索引处的元素</returns>
        public T this[int index]
        {
            get
            {
                if (index < 0 || index > Length - 1)
                    throw new IndexOutOfRangeException();
                return Locate(index).Data;
            }
            set
            {
                if (index < 0 || index > Length - 1)
                    throw new IndexOutOfRangeException();
                Locate(index).Data = value;
            }
        }

        /// <summary>
        /// 初始化CLinkList类的新实例
        /// </summary>
        public CLinkList()
        {
            Length = 0;
            PRear = null;
        }

        /// <summary>
        /// 判断CLinkList中是否包含元素
        /// </summary>
        /// <returns>如果包含元素返回false,否则返回true.</returns>
        public bool IsEmpty()
        {
            return Length == 0;
        }

        /// <summary>
        /// 将元素插入到循环链表的尾部
        /// </summary>
        /// <param name="data">要插入的元素</param>
        public void InsertAtRear(T data)
        {
            if (IsEmpty())
            {
                PRear = new SNode<T>(data);
                PRear.Next = PRear;
            }
            else
            {
                SNode<T> temp = new SNode<T>(data, PRear.Next);
                PRear.Next = temp;
                PRear = temp;
            }
            Length++;
        }

        /// <summary>
        /// 将元素插入到循环链表的首部
        /// </summary>
        /// <param name="data">要插入的元素</param>
        public void InsertAtFirst(T data)
        {
            if (IsEmpty())
            {
                PRear = new SNode<T>(data);
                PRear.Next = PRear;
            }
            else
            {
                SNode<T> temp = new SNode<T>(data, PRear.Next);
                PRear.Next = temp;
            }
            Length++;
        }

        /// <summary>
        /// 获得指定索引处的结点
        /// </summary>
        /// <param name="index">元素从零开始的索引</param>
        /// <returns>指定索引处的结点</returns>
        private SNode<T> Locate(int index)
        {
            if (index < 0 || index > Length - 1)
                throw new IndexOutOfRangeException();

            SNode<T> temp = PRear.Next;
            for (int i = 0; i < index; i++)
            {
                temp = temp.Next;
            }
            return temp;
        }

        /// <summary>
        /// 将元素插入到指定索引处
        /// </summary>
        /// <param name="index">从零开始的索引,应在该位置插入data.</param>
        /// <param name="data">要插入的元素</param>
        public void Insert(int index, T data)
        {
            if (index < 0 || index > Length)
                throw new IndexOutOfRangeException();
                
            if (index == 0)
            {
                InsertAtFirst(data);
            }
            else if (index == Length)
            {
                InsertAtRear(data);
            }
            else
            {
                SNode<T> temp = Locate(index - 1);
                temp.Next = new SNode<T>(data, temp.Next);
                Length++;
            }
        }

        /// <summary>
        /// 移除CLinkList指定索引处的元素
        /// </summary>
        /// <param name="index">要移除元素从0开始的索引</param>
        public void Remove(int index)
        {
            if (index < 0 || index > Length - 1)
                throw new IndexOutOfRangeException();

            if (PRear == PRear.Next)
            {
                PRear = null;
            }
            else
            {
                if (index == Length - 1)
                {
                    SNode<T> temp = Locate(Length - 2);
                    temp.Next = PRear.Next;
                    PRear = temp;
                }
                else if (index == 0)
                {
                    PRear.Next = PRear.Next.Next;
                }
                else
                {
                    SNode<T> temp = Locate(index - 1);
                    temp.Next = temp.Next.Next;
                }
            }
            Length--;
        }

        /// <summary>
        /// 在CLinkList中寻找元素data.
        /// </summary>
        /// <param name="data">要寻找的元素</param>
        /// <returns>如果存在返回该元素在线性表中的位置,否则返回-1.</returns>
        public int Search(T data)
        {
            int i;
            SNode<T> temp = PRear;

            for (i = 0; i < Length; i++)
            {
                if (temp.Next.Data.CompareTo(data) == 0)
                    break;
                temp = temp.Next;
            }
            return (i == Length) ? -1 : i;

        }

        /// <summary>
        /// 从CLinkList中移除所有元素
        /// </summary>
        public void Clear()
        {
            Length = 0;
            PRear = null;
        }
    }
}

应用：

using System;
using LinearStruct;

namespace ExampleList
{
    class Program
    {
        static void Main(string[] args)
        {
            ListTest(new CLinkList<string>());
            // 2
            // a1
            // a3
        }

        private static void ListTest(ILinearList<string> lst)
        {
            lst.Insert(0, "a1");
            lst.Insert(1, "a2");
            lst.Insert(2, "a3");
            lst.Remove(1);
            Console.WriteLine(lst.Length);
            for (int i = 0; i < lst.Length; i++)
            {
                Console.WriteLine(lst[i]);
            }
        }
    }
}

3.3 双向链表

定义：每个结点含有两个链域（指针域）的链表。即：利用双链域的方式存储线性表的逻辑结构。

结构：

实现：

对结点的封装：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 双向链表结点
    /// </summary>
    /// <typeparam name="T">结点中数据元素的类型</typeparam>
    public class DNode<T> where T : IComparable<T>
    {
        /// <summary>
        /// 获取或设置该结点的前趋结点
        /// </summary>
        public DNode<T> Prior { get; set; }

        /// <summary>
        /// 获取或设置该结点的后继结点
        /// </summary>
        public DNode<T> Next { get; set; }

        /// <summary>
        /// 获取或设置该结点的数据元素
        /// </summary>
        public T Data { get; set; }

        /// <summary>
        /// 初始化DNode类的新实例
        /// </summary>
        /// <param name="data">该结点的数据元素</param>
        /// <param name="prior">该结点的前趋结点</param>
        /// <param name="next">该结点的后继结点</param>
        public DNode(T data, DNode<T> prior = null, DNode<T> next = null)
        {
            Prior = prior;
            Data = data;
            Next = next;
        }
    }
}

对双向链表的封装：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 用链式存储结构实现的线性表--双链表
    /// </summary>
    /// <typeparam name="T">结点中数据元素的类型</typeparam>
    public class DLinkList<T> : ILinearList<T> where T : IComparable<T>
    {
        /// <summary>
        /// 存储头结点
        /// </summary>
        protected DNode<T> PHead { get; set; }

        /// <summary>
        /// 存储尾结点
        /// </summary>
        protected DNode<T> PRear { get; set; }

        /// <summary>
        /// 获取DLinkList中实际包含元素的个数
        /// </summary>
        public int Length { get; private set; }

        /// <summary>
        /// 初始化DLinkList类的新实例
        /// </summary>
        public DLinkList()
        {
            PHead = null;
            PRear = null;
            Length = 0;
        }

        /// <summary>
        /// 将元素插入到双链表的首部
        /// </summary>
        /// <param name="data">要插入的元素</param>
        public void InsertAtFirst(T data)
        {
            if (IsEmpty())
            {
                DNode<T> temp = new DNode<T>(data);
                PHead = temp;
                PRear = temp;
            }
            else
            {
                DNode<T> temp = new DNode<T>(data, null, PHead);
                PHead.Prior = temp;
                PHead = temp;
            }
            Length++;
        }

        /// <summary>
        /// 将元素插入到双链表的尾部
        /// </summary>
        /// <param name="data">要插入的元素</param>
        public void InsertAtRear(T data)
        {
            if (IsEmpty())
            {
                DNode<T> temp = new DNode<T>(data);
                PHead = temp;
                PRear = temp;
            }
            else
            {
                DNode<T> temp = new DNode<T>(data, PRear, null);
                PRear.Next = temp;
                PRear = temp;
            }
            Length++;
        }

        /// <summary>
        /// 获得指定索引处的结点
        /// </summary>
        /// <param name="index">元素从零开始的索引</param>
        /// <returns>指定索引处的结点</returns>
        private DNode<T> Locate(int index)
        {
            if (index < 0 || index > Length - 1)
                throw new IndexOutOfRangeException();

            DNode<T> temp = PHead;
            for (int i = 0; i < index; i++)
            {
                temp = temp.Next;
            }
            return temp;
        }

        /// <summary>
        /// 将元素插入到指定索引处
        /// </summary>
        /// <param name="index">从零开始的索引,应在该位置插入data.</param>
        /// <param name="data">要插入的元素</param>
        public void Insert(int index, T data)
        {
            if (index < 0 || index > Length)
                throw new IndexOutOfRangeException();

            if (index == 0)
            {
                InsertAtFirst(data);
            }
            else if (index == Length)
            {
                InsertAtRear(data);
            }
            else
            {
                DNode<T> temp1 = Locate(index);
                DNode<T> temp2 = new DNode<T>(data, temp1.Prior, temp1);
                temp2.Prior.Next = temp2;
                temp2.Next.Prior = temp2;
                Length++;
            }
        }

        /// <summary>
        /// 移除DLinkList指定索引处的元素
        /// </summary>
        /// <param name="index">要移除元素从0开始的索引</param>
        public void Remove(int index)
        {
            if (index < 0 || index > Length - 1)
                throw new IndexOutOfRangeException();

            if (Length == 1)
            {
                PHead = null;
                PRear = null;
            }
            else
            {
                if (index == 0)
                {
                    PHead = PHead.Next;
                    PHead.Prior = null;
                }
                else if (index == Length - 1)
                {
                    PRear = PRear.Prior;
                    PRear.Next = null;
                }
                else
                {
                    DNode<T> temp = Locate(index);
                    temp.Prior.Next = temp.Next;
                    temp.Next.Prior = temp.Prior;
                }
            }
            Length--;
        }

        /// <summary>
        /// 判断DLinkList中是否包含元素
        /// </summary>
        /// <returns>如果包含元素返回false,否则返回true.</returns>
        public bool IsEmpty()
        {
            return Length == 0;
        }

        /// <summary>
        ///  从DLinkList中移除所有元素
        /// </summary>
        public void Clear()
        {
            Length = 0;
            PHead = null;
            PRear = null;
        }

        /// <summary>
        /// 在DLinkList中寻找元素data.
        /// </summary>
        /// <param name="data">要寻找的元素</param>
        /// <returns>如果存在返回该元素在线性表中的位置,否则返回-1.</returns>
        public int Search(T data)
        {
            int i;
            DNode<T> temp = PHead;
            for (i = 0; i < Length; i++)
            {
                if (temp.Data.CompareTo(data) == 0)
                    break;

                temp = temp.Next;
            }
            return i == Length ? -1 : i;
        }

        /// <summary>
        /// 获取或设置指定索引处的元素
        /// </summary>
        /// <param name="index">要获得或设置的元素从零开始的索引</param>
        /// <returns>指定索引处的元素</returns>
        public T this[int index]
        {
            get
            {
                if (index < 0 || index > Length - 1)
                    throw new IndexOutOfRangeException();
                return Locate(index).Data;
            }
            set
            {
                if (index < 0 || index > Length - 1)
                    throw new IndexOutOfRangeException();
                Locate(index).Data = value;
            }
        }
    }
}

应用：

using System;
using LinearStruct;

namespace ExampleList
{
    class Program
    {
        static void Main(string[] args)
        {
            ListTest(new DLinkList<string>());
            // 2
            // a1
            // a3
        }

        private static void ListTest(ILinearList<string> lst)
        {
            lst.Insert(0, "a1");
            lst.Insert(1, "a2");
            lst.Insert(2, "a3");
            lst.Remove(1);
            Console.WriteLine(lst.Length);
            for (int i = 0; i < lst.Length; i++)
            {
                Console.WriteLine(lst[i]);
            }
        }
    }
}