链表和STL —— list 【复习笔记】

1. 链表

1.1 链表的定义和类型

和顺序表一样，链表也是一种线性表，线性表存储结构为链式存储就是链表

链式存储不仅要保存数据元素，还要保存数据元素间的关系，这两个部分信息形成了结点。结点有两个域：数据域（存储数据元素）和指针域（存储逻辑关系）

链表又以方向、带不带头节点、是否循环分类：

共有8种类型

1.2 单链表的实现

1.2.1 实现方式

和顺序表一样，单链表的实现方式也分为静态实现和动态实现

静态实现：通过两个数组，第一个数组存储数据元素，第二个数组存储逻辑关系

动态实现：通过new申请结点，delete释放结点

1.2.2 静态带头单链表的模拟实现

#include<iostream>
using namespace std;

//创建
const int N = 1e6 + 10;
int e[N];//存储数据
int ne[N];//存储位置
int h;//标记头结点
int id;//标记下一个指针位置

//下标0位置为哨兵位，初始头结点
//e[N]和ne[N]绑定使用，表示一个元素的数据信息和逻辑信息，也可以将二者放入一个结构体内


//头插，时间复杂度O(1)
void push_front(int x)
{
	//将x放入e数组内存储
	e[++id] = x;
	//头插是指插入哨兵位后一位
	ne[id] = ne[h];
	ne[h] = id;
}

//打印链表,时间复杂度O(N)
void print()
{
	//指针从头结点开始，空指针结束
	for (int i = ne[h]; i ; i = ne[i])
	{
		cout << e[i] << " ";
	}
	cout << endl;
}

//任意位置后插入,时间复杂度O(1)
void insert(int p, int x)//p是位置
{
	//将x放入e数组内存储
	e[++id] = x;
	ne[id] = ne[p];
	ne[p] = id;
}

//按值查找
//法一：遍历链表
//法二：额外开辟一个数组进行标记(存储数据范围不大的情况）
int mp[N];
/*
  push_front和insert的时候标记
  mp[x]=id;位置放在mp数组中，查找时可以直接得到位置

  erase时取消标记
  mp[x]=0;
*/
//方法一，时间复杂度O(1)
int find(int x)
{
	for (int i = ne[h]; i; i = ne[i])
	{
		if (e[i] == x)
		{
			return i;
		}
	}
	return 0;
}
//方法二，使用额外数组,时间复杂度O(1)
return mp[x];

//删除任意位置后的元素,时间复杂度O(1)
void erase(int p)
{
	if (ne[p])
	{
		mp[e[ne[p]]] = 0;
		ne[p] = ne[ne[p]];
	}
}

1.3 双链表的模拟实现

双链表的实现无非是在单链表的基础上加一个保存前一个元素位置的数组

//创建
const int N = 1e6 + 10;
int e[N], ne[N];
int pre[N];//存储前一个元素位置
int h, id;
int mp[N];//存储位置

//头插，时间复杂度O(1)
void push_front(int x)
{
	e[++id] = x;
	//先修改插入元素的前后指向
	ne[id] = ne[h];
	pre[id] = h;
	//在修改相邻元素的指向
	pre[ne[h]] = id;
	ne[h] = id;
	//存储位置
	mp[x] = id;
}

//打印数组，时间复杂度O(N)
void print()
{
	for (int i = ne[h]; i; i = ne[i])
	{
		cout << e[i] << " ";
	}
	cout << endl;
}

//按值查找,时间复杂度O(1)
int find(int x)
{
	return mp[x];//直接返回位置
}

//任意位置后插入元素，时间复杂度O(1)
void insert_back(int p, int x)
{
	e[++id] = x;

	mp[x] = id;

	ne[id] = ne[p];
	pre[id] = p;

	pre[ne[p]] = id;
	ne[p] = id;
}

//任意位置前插入一个元素，时间复杂度O(1)
void insert_front(int p, int x)
{
	e[++id] = x;

	mp[x] = id;

	ne[id] = p;
	pre[id] = pre[p];

	ne[pre[p]] = id;
	pre[p] = id;
}

//删除任意位置元素,时间复杂度O(1)
void erase(int p)
{
	mp[e[p]] = 0;

	pre[ne[p]] = pre[p];
	ne[pre[p]] = ne[p];
}

1.4 循环链表

上面的链表，尾指针指向0，单哨兵位就是0位置，所以正好是一个循环

2. list

STL里的list就是动态实现的双向循环链表，涉及new和delete

#include<iostream>
using namespace std;
#include<list>
//打印list
void print(list<int>& lt)
{
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

//push_front/push_back,时间复杂度O(1)
void test1()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_front(2);
	print(lt);
}

//pop_front/pop_back,时间复杂度O(1)
void test2()
{
	list<int> lt;
	for (int i; i <= 10; i++)
	{
		lt.push_back(i);
	}
	for (int i = 1; i <= 2; i++) lt.pop_front();
	for (int i = 1; i <= 3; i++)lt.pop_back();
	print(lt);
}