专栏首页Android机动车数据结构学习笔记——线性表(下)

数据结构学习笔记——线性表(下)

了解过线性表的链式存储结构以后,有人就想出来用数组来代替指针,来描述单链表。看看他们是怎么做到的。

静态链表

让数组的元素都由两个数据域组成,data和cur。也就是说,数组的每个下标都有对应的一个data和cur。数据域data,用来存放数据元素,而cur相当于单链表中的next指针,存放该元素的后继在数组中的下标,我们把cur叫做游标。

这种用数组描述的链表叫做静态链表,我们把这种描述叫做游标实现法。

另外我们对数组第一个和最后一个元素作为特殊元素处理,不存数据。我们通常把未使用的数组元素称为备用链表

数组第一个元素,即下标为0的元素的cur存放备用链表的第一个节点的下标;而数组最后一个元素的cur存放第一个有数值的元素的下标,相当于单链表中的头节点的作用。

如下图:

我们对静态链表的插入和删除操作简单了解以下:

静态链表中要解决的是:如何用静态模拟动态链表的存储空间的分配,需要时申请,无用时释放。

静态链表的插入

静态链表的删除

静态链表的优缺点

  • 在插入和删除操作时,只需要修改游标,不需要移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。
  • 没有解决连续内存分配带来的表长度难以确定的问题。
  • 失去了顺序存储结构随机存取的特点。

循环链表

对于单链表,由于每个结点只存储了向后的指针,到了尾标就停止了向后链的操作,这样,当某一个结点就无法找到它的前驱结点了。

将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。

显然解决了一个问题:当从一个结点出发,访问链表的所有结点。

双向链表

双向链表:是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。

双向链表的好处:某个结点对前后结点的操作更快;

双向链表的不足:一个结点,两个指针,耗内存更大。

既然单链表可以由循环链表,那么双向链表当然也可以是循环表,其结构如下:

双向链表的插入

双向链表的删除

关于线性表就整理到这里了,文中有不对或不足的地方,希望大家能够反馈给我,一起进步。

本文分享自微信公众号 - Android机动车(JsAndroidClub),作者:贾帅

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构学习笔记——线性表(中)

    线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的...

    蜻蜓队长
  • Java 基础(四)——集合源码解析 List

    前面我们学习了Iterator、Collection,为集合的学习打下了基础,现在我们来学习集合的第一大体系 List。

    蜻蜓队长
  • Android开发环境搭建

    因此,我们这篇文章将从JDK和AndroidStudio两个方面来讲解Android开发环境的搭建。

    蜻蜓队长
  • 9.4 什么是链表

    1、链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构,是根据需要开辟内存单元。

    C语言入门到精通
  • 算法与数据结构(一) 线性表的顺序存储与链式存储(Swift版)

    温故而知新,在接下来的几篇博客中,将会系统的对数据结构的相关内容进行回顾并总结。数据结构乃编程的基础呢,还是要不时拿出来翻一翻回顾一下。当然数据结构相关博客中我...

    lizelu
  • 如何实现LRU缓存淘汰算法

    LRU:Least recently used,最近最少使用。缓存算法根据数据最近被访问的情况来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问...

    s_在路上
  • 看动画轻松理解「链表」实现「LRU缓存淘汰算法」

    前几节学习了「链表」、「时间与空间复杂度」的概念,本节将结合「循环链表」、「双向链表」与 「用空间换时间的设计思想」来设计一个很有意思的缓存淘汰策略:LRU缓存...

    五分钟学算法
  • 从简单的线性数据结构开始:穿针引线的链表(一)

    在计算机领域离不开算法和数据结构,而在数据结构中我们往往需要一些灵巧的结构去处理一些繁杂的数据,链表 就是这样一种能穿针引线般的帮助我们去解决这种问题的数据结构...

    五分钟学算法
  • HashMap在JDK7和JDK8中的区别

    在[深入浅出集合Map]中,已讲述了HashMap在jdk7中实现,在此就不再细说了

    KEN DO EVERTHING
  • 【每天一道编程系列-2018.1.26】

    Merge two sorted linked lists and return it as a new list. The new list should b...

    yesr

扫码关注云+社区

领取腾讯云代金券