数据结构-链表篇_啊荻~的博客-程序员宝宝_链表数据结构

技术标签: 链表  数据结构  

数据结构中数组和链表是是使用频率最高的基础数据结构。数组作为数据存储结构有一定的缺陷。在无序数组中,搜索性能差,在有序数组中,插入效率又很低,而且这两种数组的删除效率都很低,并且数组在创建后,其大小是固定了,设置的过大会造成内存的浪费,过小又不能满足数据量的存储。

一、链表(Linked List)

1.定义
  链表通常由一连串节点(“链结点”)组成,每个节点包含任意的实例数据(data fields)和一或两个用来指向上一个/或下一个节点的位置的链接(“links”)。
  链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。
2.优缺点
  使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。
  链表是一种插入和删除都比较快的数据结构,缺点是查找比较慢。除非需要频繁的通过下标来随机访问数据,否则在很多使用数组的地方都可以用链表代替。
3.图解
  在链表中,每个数据项都包含在“链结点”中,一个链结点是某个类的对象。每个链结点对象中都包含一个对下一个链接点的引用,链表本身的对象中有一个字段指向第一个链结点的引用,如下图所示:
在这里插入图片描述

二、单向链表(Single-Linked List)

1.单向链表的具体实现
  单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分,第一个部分(data)保存或者显示关于节点的信息,另一个部分(next)存储下一个节点的地址。最后一个节点存储地址的部分指向空值
  单向链表只可向一个方向遍历,一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置。而插入一个节点,对于单向链表,我们只提供在链表头插入,只需要将当前插入的节点设置为头节点,next指向原头节点即可。删除一个节点,我们将该节点的上一个节点的next指向该节点的下一个节点。
2.图解
在这里插入图片描述
  head为头节点,不存放任何的数据,只是充当一个指向链表中真正存放数据的第一个节点的作用。
(1)节点添加
(2)节点删除
3.用单向链表实现栈

三、双端链表

1.双端链表的具体实现
  双端链表与单链表的区别在于它不只第一个链结点有引用,还对最后一个链结点有引用。
在这里插入图片描述
  由于有着对最后一个链结点的直接引用,所以双端链表比传统链表在某些方面要方便。比如在尾部插入一个链结点。双端链表可以进行直接操作但传统链表只能通过next节点循环找到最后链结点操作,所以双端链表适合制造队列
  双端链表可以插入表尾,但是仍然不能方便的删除表尾,因为我们没有方法快捷地获取倒数第二个链结点,双端链表没有逆向的指针,这一点就要靠双向链表来解决了。
2.用双端链表实现队列

四、双向链表

在这里插入图片描述
  双向链表即允许向前遍历,也允许向后遍历。实现这种特性的关键在于每个链结点既有下一个链结点的引用,也有上一个链结点的引用。

五、有序链表

存储有序数据的链表结构为有序链表(前面说到的所有链表都是无序的)。
  在有序链表中,数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度(因为元素不需要移动),另外链表可以扩展到全部有效的使用内存,而数组只能局限于一个固定的大小中。
  在有序链表中插入和删除某一项最多需要O(N)次比较,平均需要O(N/2)次,因为必须沿着链表上一步一步走才能找到正确的插入位置;然而可以最快速度删除值,因为只需要删除表头即可,如果一个应用需要频繁的存取最小值,且不需要快速的插入,那么有序链表是一个比较好的选择方案。比如优先级队列可以使用有序链表来实现。

六、跳表

跳表(SkipList)是在有序链表的基础上发展起来的,跳表经常会B+等数据结构比较提及。
  增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表,简称跳表。跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。
  Redis中的有序集合zset就是跳表的一个主要应用。

具体可参考下面这篇文章中的举例:
《跳表》
《Redis 跳跃表实现原理 & 时间复杂度分析》
《一文彻底搞懂跳表的各种时间复杂度、适用场景以及实现原理》

抽象数据类型(ADT)

总结

本文中图片引用自:
https://www.cnblogs.com/bjlhx/p/10751938.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_16268979/article/details/120169175

智能推荐

知人知面需知心——论人工智能技术在推荐系统中的应用_csdn_csdn__AI的博客-程序员宝宝

作者:洪亮劼,Etsy数据科学主管,前雅虎研究院高级经理。长期从事推荐系统、机器学习和人工智能的研究工作,在国际顶级会议上发表论文20余篇,长期担任多个国际著名会议及期刊的评审委员会成员和审稿人。 本文为《程序员》原创文章,未经允许不得转载,更多精彩文章请订阅2016年《程序员》在电子商务、个性化阅读、社交网络(媒体)以及共享经济高速发展的今天,发现用户的需求、了解用户的行为并为用户...

python实现遗传算法求函数最大值(人工智能作业)_dixinheba57619的博客-程序员宝宝

题目:用遗传算法求函数f(a,b)=2a x sin(8PI x b) + b x cos(13PI x a)最大值,a:[-3,7],b:[-4:10]实现步骤:初始化种群计算种群中每个个体的适应值淘汰部分个体(这里是求最大值,f值存在正值,所以淘汰所有负值)轮盘算法对种群进行选择进行交配、变异,交叉点、变异点随机分析:为了方便,先将自变量范围调整为[0,10]、...

vue-cli3 一直运行 /sockjs-node/info?t= 解决方案_飞奔的五花肉的博客-程序员宝宝

首先sockjs-node是一个JavaScript库,提供跨浏览器JavaScript的API,创建了一个低延迟、全双工的浏览器和web服务器之间通信通道。服务端:sockjs-node(https://github.com/sockjs/sockjs-node)客户端:sockjs-clien(https://github.com/sockjs/sockjs-client)如...

我的新博客地址:http://zhuyanfeng.com_GARY的博客-程序员宝宝

csdn的这个博客已经很久不用了,现在自己搭建了一个新的个人博客,地址:http://zhuyanfeng.com,另外停止使用qq。

LVS+Keepalived实现高可用负载均衡_weixin_34387284的博客-程序员宝宝

概述 随着近年来互联网的快速发展;而众多需要提供给用户访问的WEB服务器,必须保证每天24小时不间断的提供服务,随着访问量的增加,又有哪些好的WEB构架能实现高可用负载均衡,而且又是免费的呢?答案是肯定是有了,而这种架构就是LVS+KeepalivedKeepalived简介 什么是Keepalived:keepalived可以实现服务的高可用或热备,用来防止单点故障的问...

渲染类博客和游戏相关工作室论文发布地址大集合_wolf96的博客-程序员宝宝

首先是国外知名工作室的论文和技术文档发布地址集合:PIXARBlackRockBungieCrytekGuerrilla GamesInsomniacSplashdamage Tri-AceValveDiceBitsquid Square-Enix(感谢Miloyip前辈补充)然后是个人收集的渲染类博客地址集合:#AltDevBlogADay 很多开发博客聚合的网站,感觉做的挺

随便推点

lqc_selinux的安全控制_weixin_33787529的博客-程序员宝宝

了解selinux,设置给文件selinux的安全上下文件,复制、移动对selinux规则的影响,设置apache、vsftpd的selinux规则 1.了解selinux 1)DAC:指用户访问资源的控制,即权限 MAC:selinux标签,限制进程访问资源,进程归用户所有;当用户调用进程去访问资源(file)时,检查selinux安全标签,匹配了才能访问。 sel...

Android ImageView 不显示JPEG图片 及 Android Studio中如何引用图片资源_二一点的博客-程序员宝宝

Android ImageView 不显示JPEG图片 今天在写一个小实例,ImageView在xml里面设置的是INVISIBLE,在代码里需要设置成setVisibility(View.VISIBLE),但图片没有显示出来,换成PNG或其它的JPEG格式的图片确可以正常的显示。原因:显示的图片大小为5.39K,图片格式有损坏,所以不能正常显示。解决:换一张图片,或重新生成JPE

在Xcode8中使用Swift2.3_iOSHot的博客-程序员宝宝

Xcode8支持两个Swift版本:2.3和3.0 。用Xcode8打开Swift2.3的项目时,会弹窗提示你是否需要自动转换代码至Swift3.0 。自动转换代码后,仍会有不少报错。那么怎样让Swift2.3的项目在Xcode8上快速Run起来呢?Build Settings → 搜索Legacy Swift → 找到Use Legacy Swift Language Versi

ruby截取字符串_西夏一品堂的博客-程序员宝宝_ruby字符串截取

2.0.0-p481 :011 > 'admin321'[2,4] => "min3" 2.0.0-p481 :012 > 'admin321'[2..4] => "min" 2.0.0-p481 :013 > str[n, m]  从n开始,截取m个字符str[n .. m] 从n开始,截取到m

一、图像直方图显示(python)_步步星愿的博客-程序员宝宝_python显示图像直方图

图像处理中绘制图像直方图往往是观察和处理图像的利器之一。直方图的观察方面的基本知识:横坐标代表着灰度级、纵坐标是该灰度值在图像中出现的概率或者次数。直方图的型态为斜态和峰态,斜态指的是直方图的不对称的程度,峰态表示的是直方图的分布在均值周围的集中程度。直方图可以基本上反映出图像对比度的基本情况。直方图的基本性质直方图没有位置信息。直方图反映了总体灰度分布。直方图具...

JZOJ1266.【USACO题库】2.3.1 Longest Prefix最长前缀_路人黑的纸巾的博客-程序员宝宝

题目描述在生物学中,一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的(称之为元素的)序列很感兴趣。如果一个集合 P 中的元素可以通过串联(允许重复;串联,相当于 Pascal 中的 “+” 运算符)组成一个序列 S ,那么我们认为序列 S 可以分解为 P 中的元素。并不是所有的元素都必须出现。举个例子,序列 ABABACABAAB 可以分解为下面集合中的元素:

推荐文章

热门文章

相关标签