数据结构总结之链表（一）

线性表
（1）顺序存储结构（数组，必须连续空间）
优点： 不需要为表中元素之间的逻辑结构添加额外的存储空间
可以快速的存取表中任一位置的元素
缺点： 插入和删除操作需要移动大量元素
当线性表长度变化比较大时，难以确定存储空间的容量
易造成存储空间的 “碎片 ”
（2）链式存储结构（连续或不连续，由数据域和指针域组成，称为结点）
头指针与头节点异同：
头指针具有标识作用，常以头指针冠以链表的名字，无论链表是否为空，头指针均不为空，头指针是链表的必要元素。
头结点是为了统一操作而设立的，放在第一元素的结点之前，其数据域一般毫无意义（可存放链表的长度），有了头节点，对在第一元素节点前插入结点和删除结点，其操作与其他结点操作统一，头结点不一定是链表必要元素。

链表的插入与删除
插入：头插法，让头指针指向新结点，始终让新结点处于第一位置

```
  p=(LinkList)malloc(sizeof(Node));
  p->data = rand()%100 + 1;//随机数生成100以内的数字为新结点的数据域
  p->next = (*L)->next;
  (*L)->next = p; //头指针指向新结点
```

尾插法：新的结点始终插在终端结点的后面

r = *L;                 //*r为指向尾部的结点
p=(LinkList)malloc(sizeof(Node));
p->data = rand()%100 + 1;      //随机数生成100以内的数字为新结点的数据域
r->next = p ;
r = p；
r->next = null;     //表示当前链表结束

单链表整表删除：free（p）； p = p -> next；

单链表结构与顺序存储结构优缺点：
存储方式：
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；
单链表采用链式存储结构，用一组任意的存储的单元存放线性表的元素；
时间性能：
查找: 顺序存储O(1) 单链表O(n)
插入删除：顺序存储结构需要平均移动表长一半的元素，时间为O(n)；单链表在找出某位置的指针后，插入和删除仅为O(1）;
空间性能：
顺序存储结构需要预分配存储空间，分大造成浪费，分小发生上溢。单链表不需要分配存储空间，元素个数不受限制。

还有一些链表：静态链表，循环链表（终端结点的指针端由空指针改为指向头结点），双向链表，

数据结构总结之链表（一）

相关推荐