C#数据结构【链表】

前言

【此文章所有代码可在文章末尾下载查看源码】

数据结构是计算机存储，组织数据的方式,同样也是相互之间存在一种或者多种特定关系的数据元素的集合

算法是一系列规定的计算步骤，为了实现特定的计算目的

基本数据结构一般有4类:
(1)集合 (2)线性结构 (3)树形结构 (4)图形结构

集合：数据结构中的集合与数学中的集合类似，在集合中的 数据只是存在同一集合中，但其数据之间没有关系。

线性结构：数据元素之间是一对一的关系

主要包括：线性表，栈，队列（三者的数据元素以及数据间的逻辑关系完全相同，差别就在于线性表的操作不受限制，而栈和队列的操作受到限制，栈的操作只能在表的一端进行，队列的插入操作在表的一端进行而其它操作在表的另一端进行，所以，把栈和队列称为操作受限的线性表）

树形结构：数据元素之间的层次关系是一对多

图形结构：**数据元素之间呈多对多的关系

线性表

List相关常用属性

增加/插入数据（常用）：

1
2
*1.list.Add(T t)//T代表所存储的数据类型，将数据t存入链表末尾
*2.public void Insert(int index, T item);//插入数据，index代表下角标，item代表数据

查找数据（常用）：

1
2
3
1.public bool Contains(T item)//查找是否包含 item
2.public T Find(Predicate<T> match); 返回满足条件的第一个值
3.public int IndexOf(T item, int index, int count);//index开始下标,count查找个数,item查找对象

删除/清除数据（常用）：

1
2
3
4
5
*1.public void Clear();//清除所有数据
*2.public int RemoveAll(Predicate<T> match);//删除满足条件
*3.public bool Remove(T item);//移处数据
*4.public void RemoveAt(int index);//移除下角标为index的值
5.public void RemoveRange(int index, int count);//从下角标为index的值开始count个数

线性表的存储结构

  • 链式存储

  • 顺序存储

线性表的实现方式:

  • 顺序表
  • 单链表 双向表 循环表

顺序表

定义：线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素，简单说把表中的元素一个接一个地放进顺序的存储单元

顺序表要求数据要按照顺序进行存储，同理在内存中也同样是按照顺序进行存储。

顺序表的优点：用地址连续的存储单元顺序存储线性表中的各个数据元素，逻辑上相邻的数据元素在物理位置上也相邻，所以查找任何一个位置上的数据元素非常方便 ；

顺序表的缺点：进行插入和删除时，需要通过移动数据元素来实现，影响了运行效率

顺序表代码实现
【1】IListDS接口
1
2
3
4
5
6
7
8
9
10
11
12
13
 public interface IListDS<T>
{
    int GetLength(); //求长度
    void Clear(); //清空操作
    bool IsEmpty(); //判断线性表是否为空
    void Add(T item); //附加操作
    void Insert(T item, int i); //插入操作
    T Delete(int i); //删除操作
    T GetElem(int i); //取表元
    T this[int index] { get; }//定义一个索引器 获取元素
    int Locate(T value); //按值查找

}
【2】SeqList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/// <summary>
/// 顺序表实现方式
/// </summary>
/// <typeparam name="T"></typeparam>
class SeqList<T> : IListDS<T>
{
    public T[] data;//用来存储数据
    private int count=0;//表示存了多少个数据
    public SeqList(int size)
    {
        data = new T[size];
        count = 0;
    }
    /// <summary>
    /// 默认构造函数容量为10
    /// </summary>
    public SeqList() : this(10) { }
    public T this[int index]
    {
        get { return GetElem(index); }
    }
    /// <summary>
    /// 添加数据
    /// </summary>
    /// <param name="item"></param>
    public void Add(T item)
    {
        //说明数据组已经存满
        if (count == data.Length){
            Console.WriteLine("当前顺序表已经存满，不允许在存入数据");
        }
        else {
            data[count] = item;
            count++;
        }
    }
    /// <summary>
    /// 清空数据
    /// </summary>
    public void Clear() {
        count = 0;
    }
    /// <summary>
    /// 删除数据
    /// </summary>
    /// <param name="index"></param>
    /// <returns></returns>
    public T Delete(int index) {
        T temp=data[index];
        for (int i = index+1; i < count; i++) {
            data[i - 1] = data[i];
        }
        count--;
        return temp;
    }
    /// <summary>
    /// 根据索引获取数据
    /// </summary>
    /// <param name="index">索引</param>
    /// <returns></returns>
    public T GetElem(int index){
        //若索引存在
        if (index >= 0 && index <= count - 1) {
            return data[index];
        }
        else {
            Console.WriteLine("索引不存在");
            return default(T);
        }
    }
    /// <summary>
    /// 取到的数据大小
    /// </summary>
    /// <returns></returns>
    /// <exception cref="NotImplementedException"></exception>
    public int GetLength() {
        return count;
    }
    /// <summary>
    /// 插入数据
    /// </summary>
    /// <param name="item">数据</param>
    /// <param name="index">下标索引</param>
    public void Insert(T item, int index) {
        for (int i = count-1; i>=index; i--) {
            data[i+1]=data[i];
        }
        data[index] = item;
        count++;
    }
    //清空数据
    public bool IsEmpty() {
        return count == 0;
    }
    /// <summary>
    /// 返回所要查找的数据位置索引
    /// </summary>
    /// <param name="value">数据</param>
    /// <returns></returns>
    public int Locate(T value) {
        for (int i = 0; i < count; i++) {
            if (data[i].Equals(value)) {
                return i;
            }
        }
        return -1;
    }
}
具体测试代码详见
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SeqList<string> seqList = new SeqList<string>();
seqList.Add("计算机学院");
seqList.Add("软件学院");
seqList.Add("艺术学院");
for (int i = 0; i < seqList.GetLength(); i++) {
    Console.WriteLine("数据{0}:{1}", i, seqList[i]);
}
Console.WriteLine("顺序表长度:"+seqList.GetLength());
Console.WriteLine("顺序表中第一个数值:" + seqList.GetElem(0));
Console.WriteLine("删除顺序表中第二个数据:"+seqList.Delete(2));
Console.WriteLine("顺序表长度:" + seqList.GetLength());
seqList.Insert("工程学院", 1);
for (int i = 0; i < seqList.GetLength(); i++) {
    Console.WriteLine("添加完后的数据{0}个:{1}", i, seqList[i]);
}
Console.WriteLine("顺序表长度:" + seqList.GetLength());
Console.WriteLine("数据所在位置:"+seqList.Locate("艺术学院")+"【注：-1代表未查询到】");
控制台输出效果
1
2
3
4
5
6
7
8
9
10
11
12
数据0:计算机学院
数据1:软件学院
数据2:艺术学院
顺序表长度:3
顺序表中第一个数值:计算机学院
删除顺序表中第二个数据:艺术学院
顺序表长度:2
添加完后的数据0个:计算机学院
添加完后的数据1个:工程学院
添加完后的数据2个:软件学院
顺序表长度:3
数据所在位置:-1【注：-1代表未查询到】

链表

优点：

一般数组都是需要一连串的内存空间来存储数据，但是链表结构不需要一连串的内存空间。此外，由于它具有的独特的结构，使得链表插入数据变得非常的快捷。因为它不需要移动后面的数据。List列表中间插入一个数据时，后面所有的数据都要进行移动。

缺点：

链表每个节点都是离散的，所以访问链表中数据只能一个接着一个访问，这需要较长的时间来查找位于链表中间或尾部的元素。访问数据效率就会变得低下。

单链表

定义：如果结点的引用域只存储该结点直接后继结点的存储地址，则该链表叫单链表

单向链表的每一个节点又包含两部分，一部分是存放数据的变量 data（值） ，另一部分是指向下一个节点的 next（下个位域）指针

单链表结点的结构如图所示

data 表示结点的数据域

next代表该引用域，即指向另一个结点

图片加载有误

下图是线性表(a1,a2,a3,a4,a5,a6)对应的链式存储结构示意图

图片加载有误 图片加载有误
单链表插入某个数据时的执行效果

需要考虑插入的位置：(1)若插入的位置在头部为空时，只需将节点的next为head即可 (2)如果插入到其他部分（假设插入位置为n），则需将n-1和n位置next连接切断，将n-1的next指向新的n，新的n的next指向原本的n，即可完成单链表插入数据操作。

单链表添加某个数据时的执行效果

添加数据比插入数据较为简单，但是也需要判断head结点是否为空，如果为空的话，将新添加的结点设置为head即可，若head结点不是空的，则需要通过遍历结点，判断结点的next是否为空，如next为空，则将新的结点放到链表尾部，即可完成添加操作。

单链表移除某个数据时的执行效果

移除某个数据时，需要判断删除的位置，若删除的位置在于head，则需将head结点指向新的newNode，若删除的位置在于n个位置，则需通过for循环到所删除位置的n-1位置，将其定义为preNode，将n定义为currentNode，由于需要删除currentNode，所以要获取currentNode的next结点，也就是nextNode，将preNode的next更改为nextNode即可完成删除数据操作【这里无需考虑删除位置为末尾所导致的没有next，因为在Node构造方法中next可以】

单链表代码实现
【1】IListDS接口==>用于设定单链表所要实现的相关方法
1
2
3
4
5
6
7
8
9
10
11
public interface IListDS<T>{
       int GetLength(); //求长度
       void Clear(); //清空操作
       bool IsEmpty(); //判断线性表是否为空
       void Add(T item); //附加操作
       void Insert(T item, int i); //插入操作
       T Delete(int i); //删除操作
       T GetElem(int i); //取表元
       T this[int index] { get; }//定义一个索引器 获取元素
       int Locate(T value); //按值查找
   }
【2】Node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Node<T>{
       private T data;//存储数据
       private Node<T> next;//指针，用来指向下一个元素
       public T Data { get => data; set => data = value; }
       internal Node<T> Next { get => next; set => next = value; }
       public Node(){ 
           data=default(T);
           next=null;
       }
       public Node(T value){
           data=value;
           next=null;
       }
       public Node(Node<T> next) {
           this.next = next;
       }
       public Node(T data, Node<T> next) {
           this.data = data;
           this.next = next;
       }
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
class LinkList<T> : IListDS<T> {
        private Node<T> head;//存储一个头结点
        public LinkList()
        {
            head = null;
        }
        /// <summary>
        /// 返回索引下的数据
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T this[int index] {
            get{
                Node<T> temp = head;
                for (int i = 1; i <= index; i++){
                    temp = temp.Next;
                }
                return temp.Data;
            }
        }
        /// <summary>
        /// 添加数据
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item) {
            Node<T> newNode = new Node<T>(item); //根据新的数据创建一个新的结点
            //如果头结点为空，那么这个新的节点就是头结点
            if(head==null) head = newNode;
            else {
                //把新来的结点放到链表的尾部
                //要访问到链表的尾结点
                Node<T> temp = head;
                while (true) {
                    if (temp.Next != null) {
                        temp=temp.Next;
                    }
                    else{
                        break;
                    }
                }
                temp.Next = newNode;//把新来的结点放到链表的尾部
            }
        }
        /// <summary>
        /// 清空单链表
        /// </summary>
        public void Clear() {
            head=null;
        }
        /// <summary>
        /// 删除指定索引数据
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T Delete(int index) {
            T data = default(T);
            if(index==0){  //删除头结点
                data =head.Data;
                head=head.Next;
            }
            else {
                Node<T> temp = head;
                for (int i = 1; i <= index - 1; i++){
                    //让temp向后移动一个位置
                    temp = temp.Next;
                }
                Node<T> preNode = temp;
                Node<T> currentNode = temp.Next;
                data = currentNode.Data;
                Node<T> nextNode = temp.Next.Next;
                //上一节点指向新的结点
                preNode.Next = nextNode;
            }
            return data;
        }
        /// <summary>
        /// 获取索引下的数据
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T GetElem(int index){
            return this[index];
        }
        /// <summary>
        /// 获取单链表长度
        /// </summary>
        /// <returns></returns>
        public int GetLength(){
            if (head == null) return 0;
            Node<T> temp = head;
            int count = 1;
            while (true){
                if (temp.Next != null){
                    count++;
                    temp = temp.Next;
                }
                else{
                    break;
                }
            }
            return count;
        }
        /// <summary>
        /// 插入数据【需要考虑插入的是头部还是其他位置】
        /// </summary>
        /// <param name="item">所要插入的数据</param>
        /// <param name="index">插入的位置索引</param>
        public void Insert(T item, int index) {
            Node<T> newNode=new Node<T>(item);
            //插入到头结点
            if (index == 0) {
                newNode.Next = head;
                head = newNode;
            }
            else {
                Node<T> temp = head;
                for (int i = 1;i<=index-1;i++){
                    //让temp向后移动一个位置
                    temp=temp.Next;
                }
                Node<T> preNode = temp;
                Node<T> currentNode = temp.Next;
                //上一节点指向新的结点
                preNode.Next = newNode;
                //新节点指向当前结点
                newNode.Next = currentNode;
            }
        }
        /// <summary>
        /// 判断是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty() {
            return head == null;
        }
        /// <summary>
        /// 返回所要查找的数据位置索引
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        public int Locate(T value) {
            Node<T> temp=head;
            if (temp == null) return -1;
            else {
                int index = 0;
                while (true) {
                    if(temp.Data.Equals(value)){
                        return index;
                    }
                    else {
                        if (temp.Next != null) {
                            temp = temp.Next;
                            index++;
                        }
                        else {
                            break;
                        }
                    }
                }
                return -1;
            }
        }
    }
具体测试代码详见
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
nodeList.Add("计算机科学与技术");
nodeList.Add("软件工程");
nodeList.Add("自动化");
for (int i = 0; i < nodeList.GetLength(); i++) {
    Console.WriteLine("数据{0}:{1}", i, nodeList[i]);
}
Console.WriteLine("单链表长度:" + nodeList.GetLength());
Console.WriteLine("单链表中第一个数值:" + nodeList.GetElem(0));
Console.WriteLine("删除单链表中第二个数据:" + nodeList.Delete(2));
Console.WriteLine("单链表长度:" + nodeList.GetLength());
nodeList.Insert("艺术与实践", 1);
for (int i = 0; i < nodeList.GetLength(); i++) {
    Console.WriteLine("添加完后的数据{0}个:{1}", i, nodeList[i]);
}
Console.WriteLine("单链表长度:" + nodeList.GetLength());
Console.WriteLine("数据所在位置:" + nodeList.Locate("软件工程") + "【注：-1代表未查询到】");
控制台输出效果
1
2
3
4
5
6
7
8
9
10
11
12
数据0:计算机科学与技术
数据1:软件工程
数据2:自动化
单链表长度:3
单链表中第一个数值:计算机科学与技术
删除单链表中第二个数据:自动化
单链表长度:2
添加完后的数据0个:计算机科学与技术
添加完后的数据1个:艺术与实践
添加完后的数据2个:软件工程
单链表长度:3
数据所在位置:2【注：-1代表未查询到】

双链表

含义：

双向链表其元素指向它前面和后面的元素。它的每一个节点除了拥有 data 和 next 指针，还拥有指向前置节点的 prev （上个位域）指针

特性：

1）LinkedList 无法通过下标查找元素，在查找链表元素时，总是从头结点开始查找。

2）LinkedList 的容量是链表最大包含的元素数，会根据元素增减而动态调整容量。

3）LinkedList 中的每个节点 都属于 LinkedListNode 类型。

4）LinkedList 的值可以为 null，并允许重复值。

5）LinkedList **不自带排序方法。