单链表

来自计算思维百科
跳转至: 导航搜索
单链表.png

在我们编写程序的时候,首先要解决的问题是处理的数据如何组织,以方便把数据取出来或是修改数据,这就是数据结构要解决的问题。链式存储的线性表就是一种数据结构,它采用一组任意的存储单元存放需要处理的数据。

基本概念

在单链表中,每个存储单元存储一个数据,那么怎么能找到下一个数据在哪呢?解决的方法就是在每个存储单元中除了存储数据,还增加一个内容,就是下一个数据存放的内存地址,这样根据这个地址就可以找到下一个数据的位置了。这就好像一个数据用一个链子连接到下一个数据,而下一个数据也用链子连接到下下个数据,如此重复,就形成了一个像链子一样的串,这个串上的每个节点都存储一个数据,通过链子找到下一个数据。这就是单链表。 

单链表的优点是可以灵活地利用内存的空间,通过链表可以指向内存中的任何位置,这样再小的内容空间都可以被使用到。但是它也存在着缺点:插入和删除运算需要移动大量的元素。

应用范围

单链表是在内容中组织数据的有效方式,在生活中也有很多应用。

应用案例

应用1- 寻宝之旅

案例:从前有个人发现了一座金库,金库被七把金锁锁住,智慧的老人告诉他,要打开金库,就要先找到七把放在不同地方的钥匙。这七把钥匙分别装在七种颜色的锦囊里,每个锦囊里除了钥匙还有一张启示条,启示条会指引你去找下一个锦囊。于是,老人给了他第一个红色的锦囊,年轻人就开始了他艰辛的寻宝之旅。

在这个案例中,体现了单链表的存储结构,我们可以把每个锦囊当成一个结点,锦囊里的钥匙就相当于该结点的数据,启示条则相当于链子,指引他去寻找下一个结点。直到找到最后一个结点。

应用2-公安局找人

案例:公安局的警察想找小明,但是没有小明的具体地址。警察就先找了小明的朋友,小明的朋友提供了最近一次见到小明的地址,警察在这个地址继续访问,这个地方的人又告诉警察一个新地址,警察继续找,最后就可以找到小明了。

在这个案例中,小明的朋友提供的地址就是一个链子,指向新的小明信息,在这个地址又提供了下一个地址,又指向一个新信息,如此反复,就形成了一个单链表,可以顺着这个链表找到小明。

可以体现的计算思维

单链表是一种抽象数据类型,是计算机组织数据的一种方式,可以有效利用内存的空间,体现了计算思维的抽象特点。