数据结构基础（2）—链表基础概念

### 链表的优缺点： 优点： 空间没有限制 插入删除元素很快 缺点： 存取速度很慢。 定义： n个节点离散分配（在内存中不是连续存储） 彼此通过指针相连 每个节点只有一个前驱节点，每个节点只有一个后续节点 首节点没有前驱节点，尾节点没有后续节点。 首节点： 第一个有效节点 尾节点： 最后一个有效节点 头节点： 头结点的数据类型和首节点的类型一样 没有存放有效数据，最最前面的，是在首节点之前的，主要是为了方便对链表的操作。 头指针：（指向头） 指向头节点的指针变量 尾指针： 指向尾节点的指针 （头结点有可能很大，占的内存可能大，假设我想造一个函数输出所有链表的值，那你如果不用头指针类型做形参，那由于不同链表的头节点不一样大小，这样就没办法找出形参） 确定一个链表需要几个参数：（或者说如果期望一个函数对链表进行操作我们至少需要接收链表的那些信息？？？） 只需要一个参数:头指针，因为通过它我们可以推出 链表的所有信息。 （链表的程序最好一定要自己敲出来） 链表的分类： 单链表 双链表： 每一个节点有两个指针域 循环链表 能通过任何一个节点找到其他所有的节点 单链表伪算法： 1.插入节点： 在p指向的节点后面插入一个被q指向的节点：   P存放的是指向的节点的地址，q也是。next指针存放的是下一个元素的地址。   q->next=p->next;p->next=q; **也可以** **r=p->next; p->next=q;q->next=r;**   删除p后面的节点   P->next=p->next->next 会造成内存泄露，无法找到要删除的节点，无法释放内存。 正确做法：临时定义一个指针r 存放要删除节点的地址 r=p->next; p->next=p->next->next; free(r);//释放所指节点占用的内存