数据结构 链表学习总结

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

链表

• 数据结构 链表学习总结
• 前言
• 1. 链表介绍
• • 1.1 什么是链表
  • 1.2 链表的性质
  • 1.3 链表的构成
  • 1.4 单链表的框架代码（C++版）
• 2. 单链表的操作
• • 2.1 初始化链表
  • • 2.1.1 步骤
    • 2.1.2 代码展示
  • 2.2 单链表的插入
  • • 2.2.1 步骤
    • 2.2.2 代码展示
  • 2.3 输出单链表各个节点的数据
  • • 2.3.1 步骤
    • 2.3.2 代码展示
  • 2.4 单链表删除节点
  • • 2.4.1 步骤
    • 2.4.2 代码展示
  • 2.5 单链表的反转
  • • 2.5.1 步骤
    • 2.5.2 代码展示
• 3 其他链表
• • 3.1 双向链表
  • 3.2 循环链表
  • 3.3 内核链表
• 总结

前言

线性表是数据结构中最基础也是最常见的一种结构，它像一根“线”把数据像“串珠子”一样串联了起来。根据数据在内存中是否连续，可以把线性表分为：顺序表和链表 ，本文详细介绍链表。

1. 链表介绍

1.1 什么是链表

链表（linked list），将数据如同锁链一样串联起来，每一个存储数据的节点不仅存储的数据（数据域）还存储着下一个节点的内存地址（地址域）。因此，各个节点可以保存在内存中的不连续地址上。

如同这个示意图，所有节点的地址域中只保存了下一个节点的地址并且尾节点的地址域中保存的是NULL的链表称为：单链表。在单链表的基础上，尾节点保存了首节点地址的链表叫做“循环链表“；每个节点不仅保存了下一个节点的地址，还保存了上一个节点的地址的链表叫做”双向链表“。

单链表是链表的基础形式，本文着重介绍单链表。

1.2 链表的性质

• 链表在内存中可以是连续的，也可以是不连续的。

• 链表通过数据域中的地址访问节点，因此不同节点的数据域中的数据类型可以是不同的。

• 相较于顺序表，链表的存储空间内既有数据又有地址，因此它的存储密度小于1.

1.3 链表的构成

链表主要由两部分组成：

• 节点
• 首节点的地址

1.4 单链表的框架代码（C++版）

#include 
#include
using namespace std;
// 节点
template <typename Type> class Node {
public:Type data;					// 数据域Node<Type> *next;			// 地址域Node(const Type &_data) {	// 通过构造函数初始化一个节点data = _data;next = NULL;}
};
// 链表
template <typename Type> class LinkedList {

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！