数据结构笔记之链表

1.3 线性结构之链表

1.3.1 基础知识

一个数据域一个指针域
逻辑结构：链表是一个线性结构，由一系列结点(Node)组成，每个结点包含一个数据元素和一个指向下一个结点的指针(Pointer)。所有结点通过指针相连，形成一个链式结构。通常我们将链表中的第一个结点称为头结点。
data ：数据域，存放结点的值。
next ：指针域，存放结点的直接后继的地址。
物理结构：与数组不同，链表中的结点需要自行组织，向系统申请很多分散在内存各处的结点，每个结点都保存了当前结点的数据和下一个结点的地址(指针)，通过指针将结点串成一串。
具体如下：

链表的分类：
链表又分为单链表、双链表、循环单链表、循环双链表和静态链表。


相关概念
n个结点离散分配，彼此通过指针相连，每个结点只有一个前驱结点，每个结点只有一个后续结点，头结点没有前驱结点，尾结点没有后续结点。确定一个链表我们只需要头指针，通过头指针就可以把整个链表都能推出来。

1.3.2优缺点

优点：

插入和删除操作效率高
动态扩展性能更好

链表不需要像数组那样预先指定固定的大小，而是可以随时动态的增长或缩小。
链表是真正的动态数据结构，不需要处理固定容量的问题

缺点：

查找慢

由于链表中的结点不是连续存储的，无法像数组一样根据索引直接计算出每个结点的地址。必须从头结点开始遍历链表，直到找到目标结点，这导致了链表的随机访问效率较低。

额外的存储空间

链表的每个结点都需要存储指向下一个结点的指针，这会占用额外的存储空间。所以，相比于数组，链表需要更多的内存空间来存储相同数量的数据元素。

1.3.3 功能定义

| void destroyLinkedList(LinkedList *list)

1.3.4 代码实现

#include<stdio.h>
#include<stdlib.h>

/**
 * 自定义链表结构
*/

//定义存储数据的结构体

typedef struct Node
{
    int data;
    struct Node *next;
}Node;

//定义一个虚拟头节点
typedef struct 
{
    int size;       //记录单链表中存储数据的个数
    Node *next
}LinkedList;

//明确：在包含虚拟头节点的情况下：首个保存数据的节点的索引为0



// 初始化链表
void initLinkedList(LinkedList *list){
    //初始化LinkedList内部的成员
    list->size = 0;
    list->next = NULL;

}
// 返回链表的长度
size_t getLength(const LinkedList *list){

    return list->size;


}
// 在指定位置插入元素
void insertAt(LinkedList *list, size_t index, int element){
    //不合法的情况
    if (index < 0 || index > list->size)
    {
        printf("输入的index非法！\n");
        return;
    }
    //插入数据
    //1.将数据封装到node结构体的变量中
    Node *node = (Node *)malloc(1 * sizeof(Node));
    node->data = element;

    //找到index的位置进行插入操作
    if (index ==0)
    {
        node->next = list->next;
        list->next = node;
        list->size++;
        return;
    }else if (index < list->size)
    {
        Node *currentnode = list->next;//指向有数据的首元素
        for (int i = 0; i < index; i++)
        {
            currentnode = currentnode->next;
        }
        
        node->next = currentnode->next;
        currentnode->next = node;

        list->size++;
        return;
    }
    
    

}
// 在末尾插入元素
void insertEnd(LinkedList *list, int element){

    insertAt(list,list->size,element);


}
// 删除指定位置的元素并返回被删除的元素
int deleteAt(LinkedList *list, size_t index){

    if (index < 0 || index >= list->size)
    {
        printf("不合法！\n");
        return;
    }

    Node * deleteNode = list->next;
    int deleteElem = deleteNode->data;

    if (index == 0)
    {
        
        list->next = deleteNode->next;


    }else{
        Node *currentNode = list->next;
        for (int i = 0; i < index -1; i++)
        {
           currentNode = currentNode->next;
        }       
        currentNode->next = deleteNode->next;

        
    }
            //获取要删除的node的数据
 
        list->size --;
        free(deleteNode);

        return deleteElem;
    
    


}
// 删除末尾元素
int deleteEnd(LinkedList *list){

    deleteAt(list,list->size-1);

}
// 获取指定位置的元素
int getElementAt(const LinkedList *list, size_t index){

    if (index < 0 || index >= list->size)
    {
        printf("输入的index不合法！\n");
        return -1;
    }

   Node *currentNode =  list->next;
   for (int i = 0; i < index; i++)
   {
    currentNode = currentNode->next;
   }

   return currentNode->next;
   

    

}
// 修改指定位置的元素
void modifyAt(LinkedList *list, size_t index, int newValue){

        if (index < 0 || index >= list->size)
    {
        printf("输入的index不合法！\n");
        return -1;
    }

   Node *currentNode =  list->next;
   for (int i = 0; i < index; i++)
   {
    currentNode = currentNode->next;
   }
     currentNode->data = newValue;



}
// 释放链表内存
void destroyLinkedList(LinkedList *list){
    Node * currentNode =  list->next;

    for (int i = 0; i < list->size; i++)
    {
        Node * tempNode = currentNode;
        currentNode = currentNode->next;
        free(tempNode);
       

    }
    list->next = NULL;
    list->size = 0;    

}



int main(){

    LinkedList list;
    initLinkedList(&list);

    insertAt(&list,0,10);
        insertAt(&list,0,20);

    insertAt(&list,0,30);

    size_t count = getLength(&list);
    printf("%d",count);

    getchar();

    return 0;
}
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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206