《C语言程序入门——链表基础知识》单、双向链表概念、链表与数组优缺点1.1.6

你的名字 2024-04-07 12:01 55阅读 0赞

## **链表的概念** ##

**链表是常见的动态存储分布的数据结构。由若干个同一结构类型的“结点”依次串连而成。**

![22f9125ca4bf4a28af37b186769ad461.jpeg][]

链表变量一般用**指针head**表示，用来存放链表首结点的地址；每个结点由数据部分和下一个结点的地址部分组成，即**每个结点都指向下一个结点**

（图一单向链表头结点即23）

链表最后一个结点为表尾，其下一个结点的地址部分的值为NULL（表示空地址）（图一圆圈处）

**拿到链表的第一个结点，就相当于拿到了整个链表，**即只需拿起它的头，整个身也跟着连在一起

struct SinglyListNode {
        int val;
        SinglyListNode *next;
        SinglyListNode(int x) : val(x), next(NULL) {}
    };                         //拿起x即可

## 比对数组 ##

### 1.内存中的存放 ###

--------------------

**数组**

一般事先定义好固定长度，在元素个数不确定时会造成**内存空间浪费**

（例如定义了100个长度，实际个数只有10个，而其他位置都被默认为了0值）

--------------------

**链表**

各个结点在内存中可以是**不连续存放**，具体存放位置由系统分配，长度也可不加限定，根据需要**动态开辟内存空间**

###  ###

### 2.增添元素/结点 ###

--------------------

**数组**必定是连续的，当**添加或删减某个元素**，势必会**造成元素移动**，当元素过多，想想，上百万的元素挪动，效率极低

--------------------

**链表****可自由穿插新结点**，节省内存，提高操作效率。

在这里就穿插一个知识点：链表的设计，是针对顺序表的缺陷做出的。顺序表空间不够时需要增容（和数组定义时\[i\]内存不够差不多）而为了避免频繁增容，基本会扩2倍，可能造成空间浪费

而且在某些位置插入数据，之前的数据就得进行挪动

（有点似曾相识是吧）嗯。。。没错，顺序表和数组都是数据结构

## 链表分类 ##

<table style="width:462px;"> 
 <tbody> 
 <tr> 
 <td style="width:139px;">类型</td> 
 <td style="width:157px;">方向</td> 
 <td style="width:163px;">状态</td> 
 </tr> 
 <tr> 
 <td style="width:139px;"></td> 
 <td style="width:157px;">单向链表</td> 
 <td style="width:163px;">静态链表</td> 
 </tr> 
 <tr> 
 <td style="width:139px;"></td> 
 <td style="width:157px;">双向链表</td> 
 <td style="width:163px;">动态链表</td> 
 </tr> 
 <tr> 
 <td style="width:139px;"></td> 
 <td style="width:157px;">循环链表</td> 
 <td style="width:163px;"></td> 
 </tr> 
 <tr> 
 <td style="width:139px;"></td> 
 <td style="width:157px;">单、双向循环链表</td> 
 <td style="width:163px;"></td> 
 </tr> 
 </tbody> 
</table>

### 链表基本结构 ###

#### 定义链表： ####

typedef int Type;
    
    typedef struct Node
    {
        Type data;
        struct Node* next;
    }Node;

此处的Type data；是**数据部分，用于保存该节点的实际数据。**

struct Node\* next；是**地址部分，保存的是下一个节点的地址。**

#include<stdio.h>
 #include<stdlib.h>
 
 typedef int Data; //定义
 typedef struct _Node
 {
 Data data;
 struct _Node* next;
 }Node;
 
 int main()
 {
 Node note1={1}; //数据赋值
 Node note2={2};
 Node note3={3};
 
 note1.next = &note2; //连接结点2
 note2.next = &note3; //连接结点3
 
 Node* p = &note1;
 
 for(int i=0;i<3;i++)
 {
 printf("%d\n",p->data);
 p = p->next;
 }
 system("pause");
 return 0;
 }

#### 双链表 ####

特点：双链表就是在单链表结点上增添了一个指针域，指向当前节点的前驱。相比于单链表，双链表能够从终端结点反向走到开始结点。

typedef struct Data
    {
    	Type data;//存放数据
    	struct Data* next;        //下一个结点
    	struct Data* prev;        //下一个结点
    }Data;

（学的不多，暂时在这里中断一下，等学习到此处时，再把单双向链表和循环链表补齐）

[22f9125ca4bf4a28af37b186769ad461.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/da2106ae08024b368951431f46d12195.jpeg