链表

链表是一个基本的数据结构,其中每个数据项都是一个节点的一部分,每个节点都包含指向下一个节点的链接。
链表的优势在于可以提供高效地重排数据项的功能,但是不能够快速的访问表中的任意数据项。因为链表的访问数据的唯一的方式就是沿着链表一个一个节点的访问。

//C
//指针表示链接,结构体表示节点
typedef struct node *link;
struct node {Item item;link next;}

链表和数组之间的区别:
数组和结构体我们可以把元素保存在内存中,并通过名字或索引引用它,这种方式和我们把一条消息放在文件夹或地址簿中一样。而使用链表存储信息,使得它的信息难以访问,但是容易重排。

链表的基本操作

链表求逆

link reverse(link x)
{
link t, y = x, r = NULL;
while(y != NULL)
{
t = y->next; y->next = r; r = y; y = t;
}
return r;
}

链表的内存分配

链表和数组相比的优点在内存上就是在他们的生存周期内大小可以增大可以减少。
在C中使用malloc 和 free 来动态的分配内存。