数据结构——单链表的基本操作

最近正好在复习数据结构，链表作为比较重要的数据结构，特地自己实现了一遍。

首先我们要理解几个概念：

1、链式存储是最常用的存储方式之一，可以表示线性和非线性的数据结构。

2、按照链式存储的线性表简称为链表。

3、单链表是一种链式存取的数据结构,用一组地址任意的存储单元来存放线性表中的数据元素。

4、链表由节点构成，每个节点的构成为：元素+指针（指向后继元素）

理解这几个基本的概念之后，考虑如何链表的功能：1、初始化链表2、创建链表3、添加元素（往头部添加、往尾部添加、中间添加)4、删除元素(头删除、尾删除、中间删除)5、查找节点6、查找元素7、修改节点元素8、清空链表9、链表大小10、逆序链表

除此之外，在具体实现上为了方便起见，我们可以为链表设置一个头节点。

下面见代码：

image.png image.png
image.png
image.png
image.png
image.png
image.png

大家经常在笔试或者面试的时候遇到逆序链表类似的问题。一般来说思路有这么几种：
1、创建另外一个单独链表，用来存储待逆序链表遍历过成中从后往前的节点；

2、每次遍历过程中，当前元素都与第一个元素交换位置。比如：1,2,3,4逆序

第一次：2,1,3,4

第二次：3,2,1,4

第三次：4,3,2,1

（代码中使用的便是这种方法）

从算法复杂度来说，建议采用第二种。当然还有其他的方案，此处不做说明了。