目录
前言??
链表是指采用链式存储的一种数据结构，其最小结构单元称为结点，一般包含两种信息，即数据域和指针域。数据域用于存储数据，也即是结点的值。指针域一般用于存储其指向的下一个结点的位置，即通过指针域来链接构成链表结构。
我目前所知道的链表大概有以下几种：
1、单链表(最简单的一种链表)
2、双链表(在单链表的基础上采用双向指针的方式实现的链表结构)
3、循环链表(在单链表的基础上把首尾指针相连构成可以循环的链表结构)
4、静态链表(采用数组方式实现的链表结构)
待补充...
下面开始逐一分析我所知道的这几种链表结构的具体实现方式
一、单链表
单链表应该是最基本最简单链表结构了，其具体实现方式可以用一个图来看更加形象
?用小方框来表示数据域，箭头来表示指针域，单链表也就可以形象的看作一个一个向下指的结构了。其中最后一个方框一般为空作为链表的结束位置。
定义讲完了，接下来就是具体的代码实现：
一般有两种方法：数组模拟和类模板
这里先讲数组模拟的方法
首先是采用头插法实现的模拟链表
int head, e[N], ne[N], idx, t;
void init()
{
head = -1;
idx = 0;
}
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx ++;
}
void remove(int k)
{
ne[k] = ne[ne[k]];
}
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx ++;
}
作者：shengshu_
链接：https://www.acwing.com/activity/content/code/content/2708157/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。然后再来看用尾插法实现的模拟链表
#include <iostream>
using namespace std;
const int N = 10010;
int e[N], ne[N], tail, idx;
void init()
{
tail = 0, idx = 1;
}
void add_to_tail(int x)
{
e[idx] = x;
ne[tail] = idx;
ne[idx] = -1;
tail = idx ++;
}
int main()
{
int n, m;
cin >> n;
init();
for (int i = 0; i < n; i ++) {
cin >> m;
add_to_tail(m);
}
for (int i = 1; i != -1; i = ne[i])
cout << e[i] << " ";
return 0;
}
细节会稍有不同，但具体逻辑是相通的。
其中e[N]数组存储值作为数据域，ne[N]数组存储下标也就是下一个指向的位置作为指针域，head或者tail作为头结点或尾结点，idx作为结点给每一个位置赋予一个独特的值。然后遍历链表的情况也大致相同，从首个位置出发，遍历到最后一个位置也就是-1处结束。
第二种就是用类模板的情况
这里我偷个懒没用模板，直接定义了一个int类型的链表
具体实现方法如下：
#include <iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
class LinkList
{
Node *first;
public:
LinkList();
LinkList(int a[], int n, int op);//建表,两种方法
~LinkList();
int Length();
int Get(int i);//按位置查找
int Locate(int x);//按值查找
void Insert(int i, int x);//在第i个位置插入数值x
int Delete(int i);//删除第i个结点并返回第i个结点的值
int Empty();
void PrintList();
};
LinkList::LinkList()
{
first = new Node;
first -> next = NULL;
}
LinkList::LinkList(int a[], int n, int op)
{
//头插法
if (op) {
first = new Node;
first -> next = NULL;
Node *s = NULL;
for (int i = 0; i < n; i ++) {
s = new Node;
s -> data = a[i];
s -> next = first -> next;
first -> next = s;
}
}
//尾插法
else {
first = new Node;
Node * tail = first, *s = NULL;
for (int i = 0; i < n; i ++) {
s = new Node;
s -> data = a[i];
tail -> next = s;
tail = s;
}
tail -> next = NULL;
}
}
LinkList::~LinkList()
{
Node *p = NULL;
while (first != NULL) {
first = first -> next;
delete p;
p = first;
}
}
int LinkList::Length()
{
Node *p = first -> next;
int cnt = 0;
while (p != NULL) {
p = p -> next;
cnt ++;
}
return cnt;
}
int LinkList::Get(int i)
{
Node *p = first -> next;
int cnt = 1;
while (p != NULL && cnt < i) {
p = p -> next;
cnt ++;
}
if (p == NULL) cerr << "查找位置错误";
return p -> data;
}
int LinkList::Locate(int x)
{
Node *p = first -> next;
int cnt = 1;
while (p != NULL) {
if (p -> data == x) return cnt;
p = p -> next;
cnt ++;
}
return 0;
}
void LinkList::Insert(int i, int x)
{
Node *p = first, *s = NULL;
int cnt = 0;
while (p != NULL && cnt < i-1) {
p = p -> next;
cnt ++;
}
if (p == NULL) cerr << "插入位置错误";
else {
s = new Node;
s -> data = x;
s -> next = p -> next;
p -> next = s;
}
}
int LinkList::Delete(int i)
{
int x;
Node *p = first, *q = NULL;
int cnt = 0;
while (p != NULL && cnt < i-1) {
p = p -> next;
cnt ++;
}
if (p == NULL || p -> next == NULL) cerr << "删除位置错误";
else {
q = p -> next;
x = q -> data;
p -> next = q -> next;
delete q;
return x;
}
}
int LinkList::Empty()
{
if (first -> next == NULL) return 1;
else return 0;
}
void LinkList::PrintList()
{
Node *p = first -> next;
while (p != NULL) {
cout << p -> data << " ";
p = p -> next;
}
cout << endl;
}
int main()
{
int r[5] = {1,2,3,4,5}, i, x;
LinkList L(r,5,0);
cout << "当前线性表的数据为: ";
L.PrintList();
try
{
L.Insert(2,8);
L.PrintList();
} catch(string str) {cout << str << endl;}
cout << "当前链表的长度为: " << L.Length() << endl;
cout << "请输入查找的元素值: ";
cin >> x;
i = L.Locate(x);
if (i > 0) cout << "元素" << x << "的位置为: " << i << endl;
else cout << "单链表中没有元素" << x << endl;
try
{
cout << "请输入要删除第几个元素: " ;
cin >> i;
x = L.Delete(i);
cout << "删除的元素值是" << x << ",执行删除操作后数据为: ";
L.PrintList();
} catch(string str) {cout << str << endl;}
return 0;
}
?二、双链表
与上面的单链表类似，不过指针不是用头指针或尾指针了，取而代之的是前驱和后继两个指针同时存储位置信息。对比单链表的优点：可以十分方便的查找出某个结点的前驱值。
具体实现方法如下：
1、数组模拟
int r[N], l[N], e[N], idx;
右指针，左指针，数据域，结点
void init()
{
//0表示左端点，1表示右端点
r[0] = 1;
l[1] = 0;
idx = 2;
}
//在第k个点的右边插入x
//如果是在k的左边插入x，直接调用add(l[k],x)
void add(int k, int x)
{
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx ++;
}
//删除第k个点
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
//遍历链表，直接向右走就可以
void traverse()
{
for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
}
作者：shengshu_
链接：https://www.acwing.com/activity/content/code/content/2727273/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。2、类模板
跟单链表的类模板很相似，不过连指针的时候要注意前驱和后继可能都需要修改
#include <iostream>
using namespace std;
struct Node
{
int data;
Node *prior, *next;
};
class DLinkList
{
Node *first;
public:
DLinkList();
DLinkList(int a[], int n, int op);
~DLinkList();
int Length();
int Get(int i);
int Locate(int x);
void Insert(int i, int x);
int Delete(int i);
int Empty();
void PrintList();
};
DLinkList::DLinkList()
{
first = new Node;
first -> prior = NULL;
first -> next = NULL;
}
DLinkList::DLinkList(int a[], int n, int op)
{
if (op) {
first = new Node;
first -> prior = NULL;
first -> next = NULL;
Node *s = NULL;
for (int i = 0; i < n; i ++) {
s = new Node;
s -> data = a[i];
s -> prior = first;
s -> next = first -> next;
first -> next = s;
}
}
else {
first = new Node;
Node *tail = first, *s = NULL;
for (int i = 0; i < n; i ++) {
s = new Node;
s -> data = a[i];
s -> prior = tail;
tail -> next = s;
tail = s;
}
tail -> next = NULL;
}
}
DLinkList::~DLinkList()
{
Node *p = NULL;
while (p != NULL) {
p = p -> next;
delete p;
p = first;
}
}
int DLinkList::Length()
{
Node *p = first -> next;
int cnt = 0;
while (p != NULL) {
p = p -> next;
cnt ++;
}
return cnt;
}
int DLinkList::Get(int i)
{
Node *p = first -> next;
int cnt = 1;
while (p != NULL && cnt < i) {
p = p -> next;
cnt ++;
}
if (p == NULL) cerr << "查找位置错误";
return p -> data;
}
int DLinkList::Locate(int x)
{
Node *p = first -> next;
int cnt = 1;
while (p != NULL) {
if (p -> data == x) return cnt;
p = p -> next;
cnt ++;
}
return 0;
}
void DLinkList::Insert(int i, int x)
{
Node *p = first, *s = NULL;
int cnt = 0;
while (p != NULL && cnt < i-1) {
p = p -> next;
cnt ++;
}
if (p == NULL) cerr << "插入位置错误";
else {
s = new Node;
s -> data = x;
s -> prior = p;
s -> next = p -> next;
p -> next -> prior = s;
p -> next = s;
}
}
int DLinkList::Delete(int i)
{
int x;
Node *p = first, *q = NULL;
int cnt = 0;
while (p != NULL && cnt < i-1) {
p = p -> next;
cnt ++;
}
if (p == NULL || p -> next == NULL) cerr << "删除位置错误";
else {
q = p -> next;
x = q -> data;
p -> next = q -> next;
q -> next -> prior = p;
delete q;
return x;
}
}
int DLinkList::Empty()
{
if (first -> next == NULL) return 1;
return 0;
}
void DLinkList::PrintList()
{
Node *p = first -> next;
while (p != NULL) {
cout << p -> data << " ";
p = p -> next;
}
cout << endl;
}
int main()
{
int r[5] = {1,2,3,4,5}, i, x;
DLinkList L(r,5,0);
cout << "当前线性表的数据为: ";
L.PrintList();
try
{
L.Insert(2,8);
L.PrintList();
} catch(string str) {cout << str << endl;}
cout << "当前链表的长度为: " << L.Length() << endl;
cout << "请输入查找的元素值: ";
cin >> x;
i = L.Locate(x);
if (i > 0) cout << "元素" << x << "的位置为: " << i << endl;
else cout << "单链表中没有元素" << x << endl;
try
{
cout << "请输入要删除第几个元素: " ;
cin >> i;
x = L.Delete(i);
cout << "删除的元素值是" << x << ",执行删除操作后数据为: ";
L.PrintList();
} catch(string str) {cout << str << endl;}
return 0;
}
三、循环链表
循环链表是一种特殊的单链表，将链表中最后一个结点的指针指向头结点即可实现循环链表
具体实现方式就相当于单链表，但只需改变下最后一个结点的指向即可，这里就不再给出代码了。
若是在双链表中实现循环的话，只需将最后一个结点的后继改为头结点，头结点的前驱改为尾结点即可。
四、静态链表
静态链表使用数组来表示的链表结构，与前面用数组模拟的方法类似，但是采用类模板的方法，通用性更好。静态链表由于大小是固定的，所以指针域不再采用指针类型，取而代之以int类型的游标表示数组的下标。
具体实现原理同单链表，这里就不再给出代码了。