线性表的链式表示

单链表

定义

线性表的链式存储； 通过一组任意的存储单元存储线性表中的数据元素

每个结点除了存放自身信息还存储一个指向后继的指针

1
2
3
4
5
6
typedef int datatype;
typedef struct link_node
{
    datatype data;    
    struct link_node* next;
}node;

结点

单链表是非随机存储的，即不能直接找到表中某个特定的结点

查找某结点时，需要从头节点依次遍历查找

操作

插入结点p

1
2
3
4
原来a指向b
1.查找插入位置（插入ab结点之间）
2.p指向b
3.a指向p

删除结点p

1
2
原来a指向p,p指向b
1.a指向b

双链表

由于单链表是只有一个指向后继的指针，所以只能从头遍历，依次访问，为了解决这个缺点引入了双链表

定义

结点中有两个指针，分别指向前驱和后继

1
2
3
4
5
6
typedef int datatype;
typedef struct link_node
{
    datatype data;    
    struct link_node* prior,next;
}node;

操作

插入

1
2
3
4
5
原来a的后继是c，c的前驱是a，现在a后插入x
1.x指向c
2.c指向x
3.x指向a
4.a指向x

第12步一定在4前

删除

1
2
3
原来a的后继是b，b的后继是c，现在删除b
1.a指向c
2.c指向a

循环链表

循环单链表和单链表的区别在于最后一个结点的指针不是空，而是指头结点

因为循环单链表没有为空的结点，所以循环单链表判空条件为是否为头结点

对单链表常做的操作在表头和表尾，因此对于循环单链表来说，不设头指针效率更高；

若设立头指针，对表尾的操作需要o(n),而不设立只要o(1);

因为若尾指针是L，则头指针是L->next

静态链表

静态链表借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next

和顺序表一样，静态链表也要预先分配一块连续的内存空间

和链表不同的是，不使用指针，改用结点的相对地址（数组下标)

在一些不支持指针的语言中，比如(Basic)，是一种巧妙的设计方法