链式存储的定义
链式存储为了表示数据元素与其直接后继元素间的逻辑关系，数据元素除了存储本身的信息外，还需要存储直接后继的信息。相连的数据元素之间在存储空间中不要求连续。
链式存储的逻辑结构
基于链式存储结构的线性表中，每个节点都包含数据域和指针域。数据域用于存储数据元素本身，指针域用于存储相邻节点的地址。
image.png
一个完整的链表需要由以下几部分构成：
- 头指针：
一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据； - 节点：
链表中的节点又细分为头节点、首元节点和其他节点：
头节点：
其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
完整的链表示意图
线性表的基本操作方式
LinkList(); //构造函数，初始化线性表
virtual ~LinkList(); //析构函数。销毁线性表
void ClearList(); //清空线性表
bool listisEmpty(); //判断线性表是否为空
int ListLength(); //获取线性表的长度
bool GetElem(int i,Node *pNode); //获取指定元素
int LocateElem(Node *pNode); //寻找第一个满足的数据元素的位序
bool PriorElem(Node *pcurrentNode,Node *pPreNode); //获取指定节点的前驱
bool NextElem(Node *pcurrentNode,Node *pNextNode); //后去指定节点的后驱
bool ListInsert(int i,Node *pNode); //在指定位置插入节点
bool ListDelete(int i,Node *pNode); //删除指定位置的节点
bool ListInsertHead(Node *pNode); //在头节点插入新的节点
bool ListInsrtTail(Node *pNode); //在尾节点插入新的节点
void ListTraverse();
在头节点插入新的节点操作
在链表头节点插入新节点存在两种情况
1、链表本身是空表
- 即链表的新节点的next指针会指向null，然后操作LinkedList对象的头指针指向新的节点，完成链表头节点插入新节点动作。
2、链表本身已含其他节点
- 即链表的新节点的next指针会指向LinkedList对象的头指针指向的节点，然后操作LinkedList对象的头指针指向新的节点，完成链表头节点插入新节点动作。
//在链表的头部插入结点
bool LinkList::ListInsertHead(Node *pNode)
{
Node *temp = m_pList->next; //将头节点保存一个新的临时节点中
Node *newNode = new Node; //堆中申请内存
if(newNode == NULL)
{
return false;
}
newNode->data = pNode->data;
m_pList->next = newNode; //头节点指向新申请的节点
newNode->next = temp; //新申请的节点指针域
m_iLength++;
return true;
}
在末端插入元素操作
将要插入的节点放在链表中最后一个节点，因此该节点的next指针需要指向NULL
//在链表的尾部插入结点
bool LinkList::ListInsrtTail(Node *pNode)
{
Node *currentNode = m_pList;
while(currentNode ->next != NULL) //遍历最后一个节点
{
currentNode = currentNode->next;
}
Node *newNode = new Node; //堆中申请内存
if(newNode == NULL)
{
return false;
}
//最后一个节点的next指向新创建的节点。
newNode->data = pNode->data; //
newNode->next = NULL; //指向空作为最后一个节点
currentNode->next = newNode;
m_iLength++; //链表长度加一
return true;
}
往链表中的任意位置插入新节点操作
插入新节点操作需遍历到第i-1个节点,插入前需要将一个临时指针副本偏移到指定索引的位置，第i-1个位置的节点的next指针需要指向新的节点，新的节点的next指针需要指向原来第i-1个位置的节点的next指针
//往链表中任意位置插入节点
bool LinkList::ListInsert(int i,Node *pNode)
{
if(i < 0 || i > m_iLength) return false;
Node *currentNode = m_pList;//找到头结点并保存到currentNode
for(int j = 0;j<i;j++) //遍历到第i-1个节点,因为插入前需要将一个临时指针副本偏移到指定索引的位置,需要注意的
{
currentNode = currentNode->next;
}
Node *newNode = new Node;
if(newNode == NULL)
{
return false;
}
newNode->data = pNode->data; //赋值
newNode->next = currentNode->next; //原来currentNode的下一个节点变成了newNode的下一个节点
currentNode->next = newNode; //再把newNode成为urrentNode的下一个节点
m_iLength++;
return true;
}
链表中删除节点
此时与插入节点操作不同的最大不同的是遍历到第i个节点，因为对于单向链表来说,一但我们的遍历的指针位于第i个节点时已经无法返回到位于i-1位置的节点，此时我们将位于第i个位置的节点执行delete操作，那么第i-1个位置的节点与第k+1个位置的节点本应要建立的链接关系已经无法建立，那么从第k+1个位置的节点算起的部分与链表就“断链”，造成链表内存泄漏。
bool LinkList::ListDelete(int i,Node *pNode)
{
if(i < 0 || i >= m_iLength) return false;
Node *currentNode = m_pList;//找到头结点并保存到currentNode
Node *currentNodeBefore = NULL;
for(int j = 0;j<=i;j++) //遍历到第i个节点
{
currentNodeBefore = currentNode; //临时指针副本偏移到指定索引的第i个位置
currentNode = currentNode->next; //遍历操作
}
currentNodeBefore->next = currentNode->next;
pNode->data = currentNode->data;
delete currentNode;
currentNode = NULL;
m_iLength--;
return true;
}
清空链表操作
清空链表，我们从头链表的头部元素一直遍历到链表的末端,遍历过程中,在每次循环偏移链表的头指针时,我们需要一个临时指针变量来缓存前一个节点然后对其执行内存释放操作。
//清空链表操作
void LinkList::ClearList()
{
//删除节点
Node *currentNode = m_pList->next ;
while( currentNode != NULL)
{
Node *temp = currentNode->next;
delete currentNode;
currentNode = temp;
}
m_pList ->next =NULL;
}
