链表，重要的数据结构有三点优点
1）插入删除速度快(前提是知道插入的位置的前一个节点)
2）内存利用率高，不会浪费内存
3）大小没有固定，拓展很灵活
以单链表为例，实现一下单链表的增删改查
首先，先实现节点的定义
typedef struct List_Nodes
{
int data;
List_Nodes *Next;
List_Nodes(int x):data(x) , Next(nullptr) {} // 初始化
}node;?增
首先实现尾插法插入每一个节点
bool _append(node *p)
{
if(!head) head = tail = p;
else
{
tail -> Next = p;
tail = tail -> Next;
}
}其次实现给定位置插入（这里的位置）
bool _insert(node *p , int cnt) // 插入到第cnt位置后面
{
node *temp = getpos(cnt);
p -> Next = temp -> Next;
temp -> Next = p;
return true;
}删
bool _delete(int cnt)// 删除第cnt位置
{
node *temp = getpos(cnt);
if(!temp) return false;
if(temp != tail) temp -> Next = temp -> Next -> Next;
else temp -> Next = nullptr;
return true;
}
查
bool _find(int cnt)// 查第cnt位置
{
node *temp = getpos(cnt);
if(!temp) return false;
else
{
printf("data[%d] = %d\n",cnt , temp -> data);
return true;
}
}改，可以通过insert和delete操作共同进行实现
里面还有一个关键函数就是getpos函数，实现的结果就是得到给定位置的节点。
node *getpos(int i)// 寻找第i个节点
{
if(i < 0) return head; // 小于0定位于head
int cnt = 0;
node *temp = head;
while(temp && cnt < i)
{
temp = temp -> Next;
cnt ++;
}
return temp;
}完整代码：使用随机种子得到输入数据
#include<iostream>
#include<ctime>
using namespace std;
typedef struct List_Nodes
{
int data;
List_Nodes *Next;
List_Nodes(int x):data(x) , Next(nullptr) {} // 初始化
}node;
class Link_List
{
private:
node *head , *tail;
public:
Link_List()
{
head = tail = nullptr;
}
bool _append(node *p)
{
if(!head) head = tail = p;
else
{
tail -> Next = p;
tail = tail -> Next;
}
}
node *getpos(int i)// 寻找第i个节点
{
if(i < 0) return head; // 小于0定位于head
int cnt = 0;
node *temp = head;
while(temp && cnt < i)
{
temp = temp -> Next;
cnt ++;
}
return temp;
}
bool _insert(node *p , int cnt) // 插入到第cnt位置后面
{
node *temp = getpos(cnt);
p -> Next = temp -> Next;
temp -> Next = p;
return true;
}
bool _delete(int cnt)// 删除第cnt位置
{
node *temp = getpos(cnt);
if(!temp) return false;
if(temp != tail) temp -> Next = temp -> Next -> Next;
else temp -> Next = nullptr;
return true;
}
bool _find(int cnt)// 查第cnt位置
{
node *temp = getpos(cnt);
if(!temp) return false;
else
{
printf("data[%d] = %d\n",cnt , temp -> data);
return true;
}
}
void print()
{
node *temp = head;
cout << "list = [";
while(temp)
{
cout << " " << temp -> data << " ";
temp = temp -> Next;
}
cout << "]\n";
}
};
int main()
{
srand(time(0));
Link_List list;
for(int i = 0;i < 10;i ++)
{
int data = rand() % 10;
node *p = new List_Nodes(data);
list._append(p);
}
cout << "init : ";
list.print();
for(int i = 0;i < 20;i ++)
{
int x = rand() % 3;
int pos = rand() % 11 - 1;// 取值范围[-1 , 9]
if(x == 0)
{
cout << "insert : ";
int num = rand() % 10;
node *temp = new List_Nodes(num);
list._insert(temp , pos);
}
else if(x == 1)
{
cout << "delete : ";
list._delete(pos);
}
else if(x == 2)
{
cout << "find : ";
list._find(pos);
}
list.print();
}
return 0;
} 运行的结果大致就是这样：
init : list = [ 2 ?0 ?3 ?3 ?1 ?0 ?7 ?5 ?0 ?5 ]
insert : list = [ 2 ?0 ?5 ?3 ?3 ?1 ?0 ?7 ?5 ?0 ?5 ]
insert : list = [ 2 ?0 ?5 ?0 ?3 ?3 ?1 ?0 ?7 ?5 ?0 ?5 ]
find : data[2] = 5
list = [ 2 ?0 ?5 ?0 ?3 ?3 ?1 ?0 ?7 ?5 ?0 ?5 ]
delete : list = [ 2 ?0 ?5 ?3 ?3 ?1 ?0 ?7 ?5 ?0 ?5 ]
delete : list = [ 2 ?0 ?5 ?3 ?3 ?0 ?7 ?5 ?0 ?5 ]
find : data[9] = 5
list = [ 2 ?0 ?5 ?3 ?3 ?0 ?7 ?5 ?0 ?5 ]
find : data[4] = 3
list = [ 2 ?0 ?5 ?3 ?3 ?0 ?7 ?5 ?0 ?5 ]
insert : list = [ 2 ?2 ?0 ?5 ?3 ?3 ?0 ?7 ?5 ?0 ?5 ]
delete : list = [ 2 ?2 ?0 ?3 ?3 ?0 ?7 ?5 ?0 ?5 ]
delete : list = [ 2 ?2 ?3 ?3 ?0 ?7 ?5 ?0 ?5 ]
delete : list = [ 2 ?2 ?3 ?3 ?0 ?7 ?0 ?5 ]
find : data[0] = 2
list = [ 2 ?2 ?3 ?3 ?0 ?7 ?0 ?5 ]
delete : list = [ 2 ?2 ?3 ?0 ?7 ?0 ?5 ]
find : data[2] = 3
list = [ 2 ?2 ?3 ?0 ?7 ?0 ?5 ]
insert : list = [ 2 ?2 ?3 ?0 ?7 ?0 ?2 ?5 ]
insert : list = [ 2 ?6 ?2 ?3 ?0 ?7 ?0 ?2 ?5 ]
delete : list = [ 2 ?6 ?2 ?3 ?7 ?0 ?2 ?5 ]
find : data[7] = 5
list = [ 2 ?6 ?2 ?3 ?7 ?0 ?2 ?5 ]
insert : list = [ 2 ?6 ?2 ?1 ?3 ?7 ?0 ?2 ?5 ]
insert : list = [ 2 ?4 ?6 ?2 ?1 ?3 ?7 ?0 ?2 ?5 ]?