单链表 | ApricityJin’s Blog

type

status

date

slug

summary

链表是什么

我的理解:

链表是一种常见的基础数据结构，是一种线性表.

链表并不会按线性的顺序存储数据而是采用动态分配存储单元方式，在每一个节点(Node)储存数据,并保存下一个节点.

链表能够有效地节省存储空间（同数组比较）。

链表的存在解决了什么问题

我的理解:

我们之前已经接触了数组，感到数组已经是万能的数据存储位置了，但是，如果我们一直使用比较复杂的数据（也就是比较多的数据时），我就会很反感，因为对于数组这种数据结构，在使用之前，一定要对其大小进行一番定义，这样一来，它的存储空间在数据处理过程中显得极为不方便，因为谁也不想对将要处理的数据做一个空间的预算，并且还要让其空间足够大，这样才能满足储存数据的要求（但是如果分配的太多，就会浪费内存），上面的一切都证明使用数组需要注意的东西真的很多很多，这样一来，我们就开始说说链表，链表也是一种数据结构，它弥补了数组带来的诸多不便，让我们可以任意为一些数据进行空间的分配，根据需要进行内存单元的开辟。

具体实现

节点(Node)

一个链表就是一串节点(Node),每个节点的作用有二: 一是储存数据,并且一个链表储存相同类型的数据,不同链表储存的数据可以不同; 二是储存下一个节点,当下一个位置没有数据,即当前数据是最后一个数据时,节点保存的下一个节点为空.

这里我先创建一个叫Node的类,同时也是泛型,并重写description.

完成这个类的创建之后,在main.swift文件里写以下代码可以检测创建的Node类是否达到了我们对节点的功能要求:

链表(LinkedList)

我们又遇到一个新问题：如果我有很多个数据，并且要把他们储存在节点（Node）中，如果我用上诉方法创建链表将会是灾难性的，并且没有任何方法让我对其进行管理。那么接下来我就会用一个结构体LinkedList来解决这个问题。

完成链表的基础

我们把LinkedList定义为 Struct 类型，同时也是泛型。重写description方法,这样可以在输出的时候更有利于链表的透明化。

head是第一个元素；tail是最后一个元素。另外添加了isEmpty(), length()方法，方便后续使用。

对链表进行操作

这里我们定义3种添加元素的方法：

push(): 在链表的头结点前面添加元素;

append(): 在链表的尾节点后面添加元素;

insert(after:): 在某个节点后面添加元素。

移除元素

这里我们定义与添加元素对应的移除方法:

pop(): 移除链表第一个元素,并将 head 指向第二个元素;

removeLast(): 移除链表的最后一个元素;

remove(at:): 移除索引值节点的元素.

总结

本文简单实现了链表. 目前添加和移除元素的方法比较少, 如果有兴趣的话, 可以添加更多的方法, 例如 append 一个链表, insert 一个链表等等.

关于 Apple 给 Swift 写的链表实现,可以看本篇最后推荐的文章,这里就不多赘述.

本文的许多点来自于网络,我将我推荐的文章放在这里: 【数据结构与算法 - Swift 实现】02 - 链表 Swift 链表 LinkedList