单链表、双链表

链表是一种线性数据结构，节点不连续存储，每个节点包含数据域和指针域（指向下一个/上一个节点），通过指针将各节点逻辑上连接起来。

单链表

单链表中一个节点存储两个东西：节点值、指向下一个节点的指针。

C++ 实现

这里我们定义head, e[ ], ne[ ], idx

head是头指针，指向第一个节点，在链表为空的时候，把head初始化为-1。

e[] 用来存节点的值。

ne[] 用来存指向下一个节点的指针。

idx 这个变量实际上就是个下标，记录操作的元素的下标，用到了哪个节点了。

int head, e[N], ne[N], idx;   

// 初始化
void init(){
	head = -1;
	idx = 0; // 因为链表是空的
}

// 插入元素
void insert(int x){
	e[idx] = x;
	ne[idx] = head;
	head = idx ++ ;
}

void remove(){
	// 这里可以加个if判断是否为空
	head = ne[head];
	
}

优点
-按需扩容 。
-知道前驱节点，插入和删除只需要改指针，时间复杂度就是O(1)。
-节点不用连续内存空间，灵活。
-只需要一个next指针，比双链表省内存。

缺点
-不能随机访问，如果要访问第n个元素，需要从头遍历。
-只能单向遍历，没办法回溯上一个节点，因为没有指针指向上一个节点。
-删除某节点需要拿到它的前驱节点，如果拿不到就要从头遍历。

---

双链表

双链表的节点中存三个东西：左指针、值、右指针。

C++ 实现

定义出idx, e[], r[], l[]

idx, e[]同单链表。

r[]存指向下一个节点的指针。

l[]存指向上一个节点的指针。

int idx, e[N], r[N], l[N];

void init(){
	r[0] = 1, l[1] = 0;
	idx = 2;
}

// 在节点a后面插入
void insert(int a, int x){
	e[idx] = x;
	r[idx] = r[a], l[idx] = a;
	l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点
void remove(int a){
	l[r[a]] = l[a];
	r[l[a]] = r[a];
}

优点
-可以双向遍历。
-已知节点可以直接删除。
-可以回溯。

缺点
-比单链表多一倍指针开销。
-节点不支持随机访问。

---

谢谢。