【原】數(shù)據(jù)結(jié)構(gòu)與算法：06 線性表

老馬的程序人生 2020-09-16

展開全文

06 線性表

知識(shí)結(jié)構(gòu)：

1. 線性表的定義與操作

1.1 線性表的定義

線性表（Linear List）是由個(gè)相同類型的數(shù)據(jù)元素組成的序列。即表中除首尾元素外，其它元素有且僅有一個(gè)直接前驅(qū)和直接后繼。首元素僅有一個(gè)直接后繼，尾元素僅有一個(gè)直接前驅(qū)，記為：。

表中數(shù)據(jù)元素的個(gè)數(shù)稱為表的長(zhǎng)度。

例1：字母表

例2：學(xué)生成績(jī)表

1.2 線性表的操作

隨機(jī)存?。韩@取或設(shè)置指定索引處的數(shù)據(jù)元素值。（支持索引器）
插入操作：將數(shù)據(jù)元素值插入到指定索引處。
移除操作：移除線性表指定索引處的數(shù)據(jù)元素。
查找操作：尋找具有特征值域的結(jié)點(diǎn)并返回其下標(biāo)。
得到表長(zhǎng)：獲取線性表中實(shí)際包含數(shù)據(jù)元素的個(gè)數(shù)。
是否為空：判斷線性表中是否包含數(shù)據(jù)元素。
清空操作：移除線性表中的所有數(shù)據(jù)元素。

using System;

namespace LinearStruct
{
    /// <summary>
    /// 線性表的抽象數(shù)據(jù)類型
    /// </summary>
    /// <typeparam name="T">線性表中元素的類型</typeparam>
    public interface ILinearList<T> where T : IComparable<T>
    {
        /// <summary>
        /// 獲取線性表中實(shí)際包含元素的個(gè)數(shù)
        /// </summary>
        int Length { get; }

        /// <summary>
        /// 獲取或設(shè)置指定索引處的元素
        /// </summary>
        /// <param name="index">要獲取或設(shè)置的元素從零開始的索引</param>
        /// <returns>指定索引處的元素</returns>
        T this[int index] { get; set; }

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

        /// <summary>
        /// 將元素插入到指定索引處
        /// </summary>
        /// <param name="index">從零開始的索引,應(yīng)在該位置插入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. 線性表的順序存儲(chǔ)與實(shí)現(xiàn)

定義：利用順序存儲(chǔ)結(jié)構(gòu)（即利用數(shù)組）實(shí)現(xiàn)的線性表，稱為順序表。

特點(diǎn)：邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)相同；具有隨機(jī)存取的特點(diǎn)。

實(shí)現(xiàn)：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表
    /// </summary>
    /// <typeparam name="T">順序表中元素的類型</typeparam>
    public class SeqList<T> : ILinearList<T> where T : IComparable<T>
    {
        /// <summary>
        /// 數(shù)據(jù)集合
        /// </summary>
        protected readonly T[] Dataset;

        /// <summary>
        /// 獲取SeqList中實(shí)際包含元素的個(gè)數(shù)
        /// </summary>
        public int Length { get; private set; }

        /// <summary>
        /// 獲取SeqList中最多包含元素的個(gè)數(shù)
        /// </summary>
        public int MaxSize { get; }

        /// <summary>
        /// 初始化SeqList類的新實(shí)例
        /// </summary>
        /// <param name="max">SeqList中最多包含元素的個(gè)數(shù)</param>
        public SeqList(int max)
        {
            if (max <= 0)
                throw new ArgumentOutOfRangeException();
            MaxSize = max;
            Dataset = new T[MaxSize];
            Length = 0;
        }

        /// <summary>
        /// 獲取或設(shè)置指定索引處的元素
        /// </summary>
        /// <param name="index">要獲得或設(shè)置的元素從零開始的索引</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">從零開始的索引,應(yīng)在該位置插入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("達(dá)到最大值");

            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;
        }
    }
}

應(yīng)用：

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. 線性表的鏈?zhǔn)酱鎯?chǔ)與實(shí)現(xiàn)

利用指針方式實(shí)現(xiàn)的線性表稱為鏈表（單鏈表、循環(huán)鏈表、雙向鏈表）。它不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰，即：邏輯結(jié)構(gòu)與物理結(jié)構(gòu)可以相同也可以不相同。

例3：將線性表以鏈表的形式存儲(chǔ)。

3.1 單鏈表

定義：每個(gè)結(jié)點(diǎn)只含有一個(gè)鏈域（指針域）的鏈表。即：利用單鏈域的方式存儲(chǔ)線性表的邏輯結(jié)構(gòu)。

結(jié)構(gòu)：

實(shí)現(xiàn)：

對(duì)結(jié)點(diǎn)的封裝：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 單鏈表結(jié)點(diǎn)
    /// </summary>
    /// <typeparam name="T">結(jié)點(diǎn)中數(shù)據(jù)元素的類型</typeparam>
    public class SNode<T> where T : IComparable<T>
    {
        /// <summary>
        /// 獲取或設(shè)置該結(jié)點(diǎn)的數(shù)據(jù)元素
        /// </summary>
        public T Data { get; set; }

        /// <summary>
        /// 獲取或設(shè)置該結(jié)點(diǎn)的后繼結(jié)點(diǎn)
        /// </summary>
        public SNode<T> Next { get; set; }

        /// <summary>
        /// 初始化SNode類的新實(shí)例
        /// </summary>
        /// <param name="data">該結(jié)點(diǎn)的數(shù)據(jù)元素</param>
        /// <param name="next">該結(jié)點(diǎn)的后繼結(jié)點(diǎn)</param>
        public SNode(T data, SNode<T> next = null)
        {
            Data = data;
            Next = next;
        }
    }
}

對(duì)單鏈表的封裝：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表--單鏈表
    /// </summary>
    /// <typeparam name="T">單鏈表中元素的類型</typeparam>
    public class SLinkList<T> : ILinearList<T> where T : IComparable<T>
    {
        /// <summary>
        /// 存儲(chǔ)頭結(jié)點(diǎn)
        /// </summary>
        protected SNode<T> PHead { get; set; }

        /// <summary>
        /// 獲取SLinkList中實(shí)際包含元素的個(gè)數(shù)
        /// </summary>
        public int Length { get; private set; }

        /// <summary>
        /// 初始化SLinkList類的新實(shí)例
        /// </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>
        /// 獲得指定索引處的結(jié)點(diǎn)
        /// </summary>
        /// <param name="index">元素從零開始的索引</param>
        /// <returns>指定索引處的結(jié)點(diǎn)</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>
        /// 獲取或設(shè)置指定索引處的元素
        /// </summary>
        /// <param name="index">要獲得或設(shè)置的元素從零開始的索引</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">從零開始的索引,應(yīng)在該位置插入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;
        }
    }
}

應(yīng)用：

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 循環(huán)鏈表

定義：是一種首尾相連的單鏈表。即：在單鏈表中，將尾結(jié)點(diǎn)的指針域null改為指向PHead，就得到單鏈形式的循環(huán)鏈表。

表現(xiàn)形式：

通常情況下，使用尾指針表示循環(huán)鏈表。

實(shí)現(xiàn)：

對(duì)循環(huán)鏈表的封裝：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表--循環(huán)鏈表
    /// </summary>
    /// <typeparam name="T">循環(huán)鏈表中元素的類型</typeparam>
    public class CLinkList<T> : ILinearList<T> where T : IComparable<T>
    {
        /// <summary>
        /// 存儲(chǔ)尾部結(jié)點(diǎn)
        /// </summary>
        protected SNode<T> PRear { get; set; }

        /// <summary>
        /// 獲取CLinkList中實(shí)際包含元素的個(gè)數(shù)
        /// </summary>
        public int Length { get; private set; }

        /// <summary>
        /// 獲取或設(shè)置指定索引處的元素
        /// </summary>
        /// <param name="index">要獲得或設(shè)置的元素從零開始的索引</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類的新實(shí)例
        /// </summary>
        public CLinkList()
        {
            Length = 0;
            PRear = null;
        }

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

        /// <summary>
        /// 將元素插入到循環(huán)鏈表的尾部
        /// </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>
        /// 將元素插入到循環(huán)鏈表的首部
        /// </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>
        /// 獲得指定索引處的結(jié)點(diǎn)
        /// </summary>
        /// <param name="index">元素從零開始的索引</param>
        /// <returns>指定索引處的結(jié)點(diǎn)</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">從零開始的索引,應(yīng)在該位置插入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;
        }
    }
}

應(yīng)用：

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 雙向鏈表

定義：每個(gè)結(jié)點(diǎn)含有兩個(gè)鏈域（指針域）的鏈表。即：利用雙鏈域的方式存儲(chǔ)線性表的邏輯結(jié)構(gòu)。

結(jié)構(gòu)：

實(shí)現(xiàn)：

對(duì)結(jié)點(diǎn)的封裝：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 雙向鏈表結(jié)點(diǎn)
    /// </summary>
    /// <typeparam name="T">結(jié)點(diǎn)中數(shù)據(jù)元素的類型</typeparam>
    public class DNode<T> where T : IComparable<T>
    {
        /// <summary>
        /// 獲取或設(shè)置該結(jié)點(diǎn)的前趨結(jié)點(diǎn)
        /// </summary>
        public DNode<T> Prior { get; set; }

        /// <summary>
        /// 獲取或設(shè)置該結(jié)點(diǎn)的后繼結(jié)點(diǎn)
        /// </summary>
        public DNode<T> Next { get; set; }

        /// <summary>
        /// 獲取或設(shè)置該結(jié)點(diǎn)的數(shù)據(jù)元素
        /// </summary>
        public T Data { get; set; }

        /// <summary>
        /// 初始化DNode類的新實(shí)例
        /// </summary>
        /// <param name="data">該結(jié)點(diǎn)的數(shù)據(jù)元素</param>
        /// <param name="prior">該結(jié)點(diǎn)的前趨結(jié)點(diǎn)</param>
        /// <param name="next">該結(jié)點(diǎn)的后繼結(jié)點(diǎn)</param>
        public DNode(T data, DNode<T> prior = null, DNode<T> next = null)
        {
            Prior = prior;
            Data = data;
            Next = next;
        }
    }
}

對(duì)雙向鏈表的封裝：

using System;

namespace LinearStruct
{
    /// <summary>
    /// 用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表--雙鏈表
    /// </summary>
    /// <typeparam name="T">結(jié)點(diǎn)中數(shù)據(jù)元素的類型</typeparam>
    public class DLinkList<T> : ILinearList<T> where T : IComparable<T>
    {
        /// <summary>
        /// 存儲(chǔ)頭結(jié)點(diǎn)
        /// </summary>
        protected DNode<T> PHead { get; set; }

        /// <summary>
        /// 存儲(chǔ)尾結(jié)點(diǎn)
        /// </summary>
        protected DNode<T> PRear { get; set; }

        /// <summary>
        /// 獲取DLinkList中實(shí)際包含元素的個(gè)數(shù)
        /// </summary>
        public int Length { get; private set; }

        /// <summary>
        /// 初始化DLinkList類的新實(shí)例
        /// </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>
        /// 獲得指定索引處的結(jié)點(diǎn)
        /// </summary>
        /// <param name="index">元素從零開始的索引</param>
        /// <returns>指定索引處的結(jié)點(diǎn)</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">從零開始的索引,應(yīng)在該位置插入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>
        /// 獲取或設(shè)置指定索引處的元素
        /// </summary>
        /// <param name="index">要獲得或設(shè)置的元素從零開始的索引</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;
            }
        }
    }
}

應(yīng)用：

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]);
            }
        }
    }
}