1.链表简介
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。(百度百科)
2.链表的基本操作
-
创建链表
首先要创建链表节点结构体,链表的单个节点由两部分构成,即数据域与指针域。数据域用来存储数据,指针域存储后继的地址。(本博文仅讨论单向链表)
创建链表时,需要声明一个头节点。一般情况下,头节点不含数据,并且指向存储第一个数据的节点。 -
插入数据
对链表进行数据插入操作时,需要分配一个新的存储空间存储新的节点,并且使插入位置的前驱指向新节点,新节点指针域指向后继。如图所示:
-
删除数据
对链表中的数据进行删除时,只需要其前驱直接指向后继,打断被删除节点与后继的连接,并释放该节点即可,如图所示:
-
遍历
遍历链表的重要依据就是其指针域指向其后继,只需访问每个节点指针域指向节点即可完成遍历。
3.链表的C++实现
- 构造链表类以及节点结构体
template<class DataType>
struct node //节点
{
DataType data; //数据域
node<DataType> *next; //指针域
};
template<class DataType>
class LinkList //链表类
{
public:
LinkList(); //无参数构造
LinkList(DataType a[], int n); //按数组构造
~LinkList(); //析构
int length(); //返回长度
DataType get(int i); //按位查值
int locate(DataType x); //按值查位
void insert(int i, DataType x); //插值
void del_loc(int i); //按位删值
void del_data(DataType x); //按值删值
void clear(); //清空
private:
node<DataType> *head; //头节点
};
- 构造方法
template<class DataType>
LinkList<DataType>::LinkList()
{
head = new node<DataType>; //为头节点分配内存空间完成构造
head->next = NULL;
cout << "LinkList Constructed" << endl;
}
template<class DataType>
LinkList<DataType>::LinkList(DataType a[], int n)
{
head = new node<DataType>;
head->next = NULL;
for (