顺序表和链表总结对比

C语言基础结束之后就该迎来了数据结构。数据结构一句话研究数据怎么组织、怎么存、怎么操作的学科。程序 数据结构 算法它是程序的骨架。一、顺序表和链表的对比顺序表和链表都是线性表逻辑结构都是线性结构最大区别就是存储结构物理结构不同顺序表采用了连续物理单元来存储一组数据类似于C语言的数组链表则是采用任意单元存储数据数据元素之间通过指针关系连接。1.1顺序表的优点1、支持下标的随机访问实践中也非常有用比如排序、排序后的二分查找。2、顺序表cpu缓存命中率很高没有内存碎片等也是一大优点。1.2顺序表的缺点1、插入删除需要整体挪动数据复杂度是ON所以他只适合大量尾插尾删的场景。2、空间不够是需要扩容大家也知道malloc是有一定代价的扩容要 malloc 重新申请 拷贝旧数据有时间和空间双重代价。1.3链表的优点1、按需申请释放空间不需要扩容。2、链表在已知节点位置的情况下可以实现任意位置的插入删除不需要挪动数据。1.4链表的缺点1、不支持下标访问。2、链表的cpu缓存命中率相对较低且会导致内存碎片化的问题。#include stdio.h #include stdlib.h /* 顺序表连续内存插入要挪数据 */ typedef struct SeqList { int* data; // 动态数组内存连续 int size; // 当前元素个数 int capacity; // 容量 } SeqList; void SeqListInit(SeqList* s) { s-capacity 4; s-size 0; s-data (int*)malloc(s-capacity * sizeof(int)); } // 尾插O(1) void SeqListPushBack(SeqList* s, int val) { if (s-size s-capacity) { // 满了才扩容 s-capacity * 2; s-data (int*)realloc(s-data, s-capacity * sizeof(int)); } s-data[s-size] val; } // 头插关键对比点 —— 所有元素整体往后挪一位O(n) void SeqListInsertHead(SeqList* s, int val) { if (s-size s-capacity) { s-capacity * 2; s-data (int*)realloc(s-data, s-capacity * sizeof(int)); } for (int i s-size; i 0; i--) { // 从后往前挪一个都不能少 s-data[i] s-data[i - 1]; } s-data[0] val; s-size; } /* 链表任意内存插入只改指针 */ typedef struct Node { int data; struct Node* next; } Node; Node* CreateNode(int val) { Node* n (Node*)malloc(sizeof(Node)); n-data val; n-next NULL; return n; } // 头插关键对比点 —— 新建节点只改两个指针O(1)已有数据一动不动 Node* ListInsertHead(Node* head, int val) { Node* newNode CreateNode(val); newNode-next head; // 新节点指向旧头 return newNode; // 新节点成为新头 } void PrintSeqList(SeqList* s) { for (int i 0; i s-size; i) printf( data[%d]%d %p\n, i, s-data[i], s-data[i]); } void PrintList(Node* head) { int i 0; for (Node* p head; p; p p-next) printf( node[%d]%d %p\n, i, p-data, p); } int main() { printf( 顺序表初始 1 2 3 \n); SeqList s; SeqListInit(s); SeqListPushBack(s, 1); SeqListPushBack(s, 2); SeqListPushBack(s, 3); PrintSeqList(s); printf(\n顺序表头插 0所有元素要往后挪一位\n); SeqListInsertHead(s, 0); PrintSeqList(s); printf(\n 链表初始 1 2 3 \n); Node* n1 CreateNode(1); Node* n2 CreateNode(2); Node* n3 CreateNode(3); n1-next n2; n2-next n3; PrintList(n1); printf(\n链表头插 0只改两个指针已有节点不动\n); Node* head ListInsertHead(n1, 0); PrintList(head); printf(\n注意对比地址顺序表地址连续(间隔4字节)链表地址是分散的\n); free(s.data); while (head) { Node* tmp head; head head-next; free(tmp); } return 0; }二、总结通过上述分析和对比我们会发现这两个数据结构是相辅相成的顺序表的优点正好弥补链表的缺点链表的优点正好弥补顺序表的缺点没有绝对的好坏只有合不合适所以实践中是分析使用场景来选择适合的数据结构的。三、小问题如果要用线性表实现后进先出的栈你会选顺序表还是链表