数据结构线性表特点详解：顺序表与链表的对比分析

数据结构线性表特点详解：顺序表与链表的对比分析

引用

CSDN

1.

https://blog.csdn.net/yishaobai/article/details/145649026

线性表是数据结构中最基础、最常用的逻辑结构之一，几乎所有程序都会直接或间接地使用它。本文将深入探讨线性表的核心概念、实现方式、操作原理以及应用场景，帮助读者构建系统化的知识体系。

引言

线性表（Linear List）是数据结构中最基础、最常用的逻辑结构之一，几乎所有程序都会直接或间接地使用它。本文将深入探讨线性表的核心概念、实现方式、操作原理以及应用场景，帮助读者构建系统化的知识体系。

1、线性表的定义与特性

1.1 基本概念

线性表是由相同数据类型的n nn（n ≥ 0 n\geq0n≥0）个数据元素组成的有限序列。

2、顺序表

2.1 存储结构

• 使用连续内存空间存储元素。
• 通过数组实现，物理顺序与逻辑顺序一致。

2.2 核心操作分析

• 尾部插入：
• 当
  size == capacity
  就会触发扩容。
• 中间插入：

2.3 模拟实现关键点

• 基础结构：

typedef int DataType;
typedef struct ArrayList
{
    DataType* a; // 存储数据的指向数组的指针
    int size; // 存储数据的数量
    int capacity; // 数组容量
} ArrayList;

• 顺序表初始化：
• 需要注意：
  pal->a = (DataType*)malloc(4 * sizeof(DataType));
  中
  sizeof
  后一定是数据类型，不能是指针类型，不然会空间报错。

void Init(ArrayList* pal)
{
    assert(pal);
    pal->a = (DataType*)malloc(4 * sizeof(DataType)); // 动态开辟
    if (pal->a == NULL)
    {
        perror("Init::malloc");
    }
    pal->size = 0;
    pal->capacity = 4;
}

• 扩容：
• 当
  size == capacity
  时，表示空间已满，需扩容，使用
  realloc
  进行扩容。
• 每次插入元素都应该检查容量。

if (pal->size == pal->capacity)
{
    int new_capacity = 2 * pal->capacity;
    DataType* new_ptr = (DataType*)realloc(pal->a, sizeof(DataType) * new_capacity);
    if (new_ptr == NULL)
    {
        perror("Reserve::realloc");
        return;
    }
    pal->a = new_ptr;
    pal->capacity = new_capacity;
}

3、链表

3.1 存储结构

• 由一个一个节点构成。
• 逻辑结构：
• 逻辑结构可以想象各个节点是集中在一起的。
• 物理结构：

• 节点在内存中并不一定是集中在一起的，操作系统可能随意找一块内存开辟空间。

3.2 核心操作分析

• 尾部插入：
• 单链表需要先找到尾节点，时间复杂度O ( N ) O(N)O(N)。
• 双向链表尾插时间复杂度O ( 1 ) O(1)O(1)。

3.3 单链表模拟实现关键点

• 基本结构：

typedef int DataType;
typedef struct Node
{
    DataType a;
    struct Node* next;
} Node;

• 指针传入问题：
• 传入结构体指针:
• 因此要想改变结构，需要传入二级指针。

4、对比