02.顺序表、链表简述+对比

一、线性表

二、顺序表

三、链表

四、顺序表和链表的区别

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列（相同特性指都为整型int、字符型char或其它类型）。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

1）.顺序表概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删改查。一般见到的顺序表都是在结构体中定义的数组，只是比普通数组多了增删改查等一些其他功能函数。

顺序表一般可以分为：

①. 静态顺序表：使用定长数组存储元素。（即数组大小一旦确定就不能改变）。可能导致有时空间开大了，造成空间浪费；或者空间开小了，空间不够用。

#define N 7
typedef int SLDataType;
typedef int SeqList
{SLDataType a[N];	//定长数组，N的值一开始就确定了size_t size;
}SeqList;

②. 动态顺序表：使用realloc动态开辟的数组存储，数组大小可以改变，每次增容2倍。


typedef int SLDataType
typedef struct SeqList
{SLDataType* a;		//指向动态开辟的数组size_t size;		//有效数据个数size_t capicity;	//容量空间的大小
}SeqList;

2）.动态顺序表接口：（接口实现见下一篇博客）

//顺序表初始化
//检查空间，如果满了，进行增容
//顺序表尾插
//顺序表头插
//顺序表尾删
//顺序表头删
//顺序表查找
//顺序表在指定位置插入
//顺序表删除指定位置的值
//顺序表的销毁
//顺序表的打印

三、链表

1）链表的概念及结构

数据元素是由指针链接实现的。每次增加数据都要申请空间。

typedef int SLTDateType
typedef struct SListNode
{SLTDateType data;          //存储数据struct SListNode* next;    //next指针，指向下一个数据节点
}SListNode;

链表的结构如下，每个head为链表的头节点（头节点可有可无），是一个指针指向链表的第一个元素，每个链表节点中的next指针指向下一个节点的地址，每个节点通过上一个节点的next指针链接。

2）.链表的分类

①.单向或者双向，双向链表中有两个指针，一个指向前一个节点的地址，一个指向后一个节点的地址。

②.带有节点，或者不带头节点。

③.循环或者非循环。

循环：最后一个节点的next指向第一个节点。

非循环：最后一个节点的next指向NULL。

3）.链表的实现（单链表）（具体实现见下下篇博客）

typedef int SLTDateType
typedef struct SListNode
{SLTDateType data;          //存储数据struct SListNode* next;    //next指针，指向下一个数据节点
}SListNode;//动态申请一个节点
//单链表打印
//单链表尾插
//单链表头插
//单链表尾删
//单链表头删
//单链表查找
//单链表在指定位置之后插入
//单链表在指定位置之后删除

四、顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低