数据结构-链表
单链表
一般在算法里面都是采用的静态链表，动态链表
单链表一般就是邻接表，包括存储树与图
双链表一般是优化某些问题的
一下是动态链表与静态链表之间的区别
. 内存分配方式
• 静态链表：
• 静态链表通常是基于一个固定大小的数组来实现的。链表中的每个结点在数组中占据一个位置，通过数组下标来模拟指针的功能。
• 每个结点除了存储数据外，还需要一个指向下一个结点的位置（数组的下标或索引）。
• 静态链表的内存大小在编译时确定，不能动态扩展。
• 动态链表：
• 动态链表使用的是 指针 来动态分配内存。每次需要插入一个新结点时，程序会调用 malloc() 或 new 操作符（取决于编程语言）来动态分配内存空间。
• 动态链表的内存是按需分配的，因此可以随时扩展或收缩，内存使用效率较高。
2. 内存管理
• 静态链表：
• 由于静态链表基于数组，内存是一次性分配的。数组的大小在编译时固定，因此如果链表的实际大小小于数组的大小，会浪费内存；如果链表的大小超过了预设的数组大小，则无法继续扩展。
• 静态链表没有真正的指针，而是通过数组下标来模拟指针关系。
• 动态链表：
• 动态链表的内存管理由操作系统或运行时环境来负责，程序可以在运行时动态申请和释放内存。
• 每个结点可以独立分配内存，因此内存空间的使用更灵活，能够根据链表实际的大小来管理内存。
3. 空间效率
• 静态链表：
• 由于预先分配了固定大小的内存，因此空间利用率可能较低。特别是当链表的元素数目变化很大时，静态链表可能会浪费很多内存。
• 动态链表：
• 空间利用率较高。每个结点的内存空间是动态分配的，只有当需要更多空间时才会分配额外的内存。
4. 灵活性
• 静态链表：
• 静态链表的灵活性较差，因为它的大小是固定的，一旦数组大小确定，无法改变。
• 动态链表：
• 动态链表的灵活性较强，可以根据实际需要动态增减结点，适应不同的链表大小。
5. 实现方式
• 静态链表：
• 通常通过一个结构体和一个固定大小的数组来实现。数组中的每个元素都包含数据部分和指向下一个结点的“下标”或“索引”，模拟指针的功能。
• 动态链表：
• 每个结点包含两个部分：数据部分和一个指针（或者引用）指向下一个结点。内存是动态分配的，因此每个结点都是独立的。
静态链表不同与动态链表，他一般是不用->next 指针的，所以
可以参考这个图片，下面是一个单链表的程序
void init()
{
head = -1;
idx = 0;
}
// 将x插到头结点
void add_to_head(int x)
{
e[idx] = x, ne[idx] = head, head = idx ++ ;
}
// 将x插到下标是k的点后面
void add(int k, int x)
{
e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}
// 将下标是k的点后面的点删掉
void remove(int k)
{
ne[k] = ne[ne[k]];
}
这个就是大体的头插，删除，插在某一个节点的后面
现在来画图解释一下头插
head = idx; // 将当前的 `idx` 赋值给 `head`，使头节点指向当前结点。 idx = idx + 1; // 自增 `idx`，为下一次插入操作预留新的数组位置。
这里是一个拆分，也许这样你就理解了为什么是idx++了
现在再来解释一下再一个节点（不是头节点插入）
下面在画一个删除节点的
这个就简单一点吧
现在在回到刚刚那个题，现在我们来上代码
#include<iostream>
using namespace std;
const int N = 100010;
int head,e[N],ne[N],idx;
void init()
{
head = -1;
idx = 0;
}
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx++;
}
void add(int k,int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
void remove( int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
int m;
cin >> m;
init();
while(m--)
{
int k,x;
char op;
cin >> op;
if(op == 'H')
{
cin >> x;
add_to_head(x);
}
else if(op == 'D')
{
cin >> k;
if(!k) head = ne[head];
else remove(k-1);
}
else {
cin >> k >> x;
add(k-1,x);
}
}
for(int i = head;i != -1;i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
这里面最重要的是add(k-1,x) 这里，因为很容易搞错
双链表
因为只写代码的话很多同学就不明白为什么是这样的，所以现在我画个图
大体上就是这样的，根据这个图，我们就要进行4次修改才可以
void add(int k,int x)
{
e[idx] = x; //对当前我要插入的点赋值
r[idx] = r[k] ; //这里指的是将要添加的值的右边箭头指向k位置的右边箭头指向的值
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
} 四个指针操作，主要是画图就理解深刻；
那么这里是插入，如果是删除嫩？我应该怎么写呢
void remove(int k) //如果我要删除第k的点
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
我一直都是写的数组，推荐写数组，因为写数组比写结构体简单
1. 数组是连续存储，结构简单
• 数组是 连续内存块，通过索引直接访问元素，无需处理复杂的指针操作。
• 在实现链表时，数组模拟的静态链表通过下标来模拟指针（例如 next 数组存储后继位置），逻辑更直观。
• 而结构体需要真正的指针去指向动态分配的内存，涉及内存分配 (malloc 或 new)、释放 (free 或 delete) 和指针操作，这增加了复杂度。
下面为两个示例对比：
数组操作（静态链表）
e[idx] = x; // 存储数据 next[idx] = head; // 模拟指针，存储下标 head = idx++;
结构体操作（动态链表）
Node* newNode = new Node(); // 动态分配内存 newNode->data = x; // 存储数据 newNode->next = head; // 指向当前头节点 head = newNode; // 更新头节点
• 为什么 idx = 2：
• 左端点（0）和右端点（1）被预留用于标记链表边界。
• 数据存储从下标 2 开始，逻辑清晰且避免冲突。
• 是否可以使用其他值：
• 从 2 开始是最合理的选择，因为更小的值（0 或 1）会导致下标冲突，更大的值（3 或以上）会浪费空间。
• 左端点和右端点的作用：
• 统一链表操作的边界处理，无需额外判断特殊情况。
所以一般设置idx从2开始
下面上代码
实现一个双链表，双链表初始为空，支持 5 种操作：
-
在最左侧插入一个数；
-
在最右侧插入一个数；
-
将第 k 个插入的数删除；
-
在第 k 个插入的数左侧插入一个数；
-
在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
-
L x，表示在链表的最左端插入数 x。 -
R x，表示在链表的最右端插入数 x。 -
D k，表示将第 k 个插入的数删除。 -
IL k x，表示在第 k 个插入的数左侧插入一个数。 -
IR k x，表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。
数据范围
1≤M≤100000 所有操作保证合法。
输入样例：
10 R 7 D 1 L 3 IL 2 10 D 3 IL 2 7 L 8 R 9 IL 4 7 IR 2 2
输出样例：
8 7 7 3 2 9
这个是题目：
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;
// 在节点a的右边插入一个数x
void insert(int a, int x)
{
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++ ;
}
// 删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}
int main()
{
cin >> m;
// 0是左端点，1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
while (m -- )
{
string op;
cin >> op;
int k, x;
if (op == "L")
{
cin >> x;
insert(0, x);
}
else if (op == "R")
{
cin >> x;
insert(l[1], x);
}
else if (op == "D")
{
cin >> k;
remove(k + 1);
}
else if (op == "IL")
{
cin >> k >> x;
insert(l[k + 1], x);
}
else
{
cin >> k >> x;
insert(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
大体上，这个就是基于数组的单链表，双链表的实现。
标签：head,idx,int,ne,链表,插入,数据结构,day From： https://blog.csdn.net/2401_87202881/article/details/145133605