Question

数据结构单链表？

设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，则需要执行的语句：q->next=p->next ；p->next=q。

为什么不能直接p->next=q呢，这里的q->next=p->next起到什么作用 求解答

Answer 1

举一个现实中的例子你就明白了：
假设有apcde5个小朋友依次手拉着手组成了一个链表a->p->c->d->e，现在来了一个小朋友q，老师要他插到p的后面，如果他只拉着p的手，而不拉着c的手，那链表是不是就断了，变成了两个链表a->p->q和c->d->e。
所以，这里的q->next=p->next;的意思就相当于让q的一只手先拉着c的一只手(此时的c一只手拉着p和q，另一只手拉着d)，而p->next=q;的意思就相当于让p松开与c的手转而拉着q的另一只手，这样就形成了一个完整的链表。

当然，在现实中q和p、c中的谁先拉手是不重要的，但对于链表，q必须先和c拉手，因为只有通过p->next才能找到c，如果q先和p拉手(即执行p->next=q;)，那链表就断了，再也没有办法找到c了(因为现在的p->next是q而不是c了，也没有其它指针指向c)。

总之记住，在链表中插入一个结点时顺序很重要，是先连后断。
比如，要将x插在p和q之间，必须先令x和q连接起来，然后断开原来的p和q之间的连接，转而令p和x建立连接。

Answer 2

想知道链表的基本操作我就随便写下了，无关代码我就省略了，不好编码，说基本操作，不敢是单链还是双链，循环链原理都是一个样的，只是单链式一头指到尾，（一个指针域一个数据域）；其他的就是多了个指针域而已
------------------
template<typename Type> class SingleList{ //用模板提高可用性
SingleList():head(new ListNode<Type>()){} //初始化链表
.....
// 省略无关代码
}
//获取长度，因为单链表一个循环见NULL就说明链表结束了
ListNode<type> *p = head->next; //head是ListNode<type> *类型
int cnt = 0;
while(p!=NULL) {
cnt++;
p = p->next;
}
return cnt ;//好了这就是list _length
-----------------------------------------

template<typename Type> ListNode<Type>* SingleList<Type>::Find(int n){
//查找操作，按节点或按值
if(n<0) return NULL;
ListNode<Type>*p =head->next;
for(int i =0;i<n&&p;i++){
//n&&p 防止开始p=NULL，改用if先判断也可以
p = p ->next;
}
return p==NULL?NULL:p;
}
//按值查找一样就是在循环中加个判断value ==p->data就是了
-------------------------------
//插入，指定位置插入
template<typename Type> bool SingleList<Type>::Insert(Type item, int n){
if(n<0) return false;
ListNote<Type>*p=head;
ListNote<Type>*p1 = new ListNode<Type>(item); //初始化节点
if(p1 == NULL) return false;
for(int i =0;i<n&&p;i++){
p = p->next;
}
if(p == NULL)return false;
//关键代码，叉叉,就是把节点指针域指向调整下，不多说，我烦这个
p1->next = p->next;
p->next=p1;
return true;
}
---------------------------------
//移除操作
template<typename Type> bool SingleList<Type>::RemoveByValue(Type item){
ListNode<Type> *P = head;
ListNode<Type> *P1 = head->next;
while(p1!=NULL){
if(p1->data == item){//等的就是你，remove
p->next = p1->next ;//函数指针域指向的变换
delete p1;
p1=p->next;
contnue;
}
p=p->next;
p1=p1->next;
}
return true ;
}
//按index移除原理一样
------------------------------
//根据index获取data
Type SingLeList<Type>::GetDataByIndex(int n)
{
if(n<0) return define;
ListNode<Type> *p =head->next;
for(int i=0;i<n;i++){
p=p->next;
if(p == null) return define;
}
return p->data;
}
=======================
基本的链表操作就是这样的，其他的不说了，实例不给了，对与以上类似

for(int i=0;i<n;i++){
p=p->next;
if(p == null) return define;
。。。。
}
代码可能有疑惑，这是个人的编程习惯，想最后一个获取值，你往前可以使用类似p[n] 值来输出~ 用循环式是为了判断下，防止输入的n是个无效的指向，以为函数中我基本都只判断了n<0而没判断n是不是超出了链表长度，所以用循环来判断
还有类似查找也可以使用if(p[n]==item) ...来表示，~ 总之编程喜好了
===
有点啰嗦了，

Answer 3

单链表加入元素的操作,同样需要考虑插入的位置,可以做首端插入、尾端插入或者定位插入。但是我们需要注意,在链表中插入元素时,并不需要移动已有的数据。