JAVA 数据结构实现 01-- 单链表与循环链表

一般来说 , 顺序存储是最好理解 , 也最好实现的一种数据结构 , 然而 , 就像我们排队去买火车票一样 ,总会有人不按照排好的顺序来 , 有的人会插队 , 有的人会放弃排队 , 整个队伍在不断的发生变化 , 每个人的位置都会改变 ; 顺序表在实现添加和删除数据时 , 会移动大量的数据 , 这显然是需要浪费大量的时间的 , 所以我们需要一种新的存储结构来解决这个问题 。

下面要介绍的这种物理存储结构被称为 链式存储 ; 链式存储结构是把数据元素放在任意的存储单元里 , 数据元素的逻辑关系和他们的存储位置没有任何关系 , 因此我们需要一个指针来存放数据元素的地址 , 这样我们就可以找到相关数据元素的位置 。为了避免顺序存储中插入/删除的线性开销 , 我们需要保证表可以不连续存储 , 否则表的每个部分可能都需要整体移动

图 1

链表是由一系列节点组成 , 这些节点不必再内存中按照顺序紧密相连 , 在上图中 , 我们可以把 A2 称为 A1 的直接后继 , 在顺序存储中 , 每个数据元素只需要存储它本身的数据 , 但是在链表中 , 每个节点除了要存储它本身的数据元素之外还要存储它直接后继元素的信息 ; 我们可以把存储它本身数据的部分叫做数据域 , 存储它直接后继元素的部分叫做指针域 ; 一个节点是由数据域与多个指针域组成的 , 多个节点连成一个链表 , 我们就可以把它称为线性表的链式存储结构 ; 如果一个链表中只含有一个指针域 , 我们就可以叫它为单链表(如上图) 。有的时候为了方便我们对链表的访问 , 会在第一个节点前添加一个头节点 , 在最后一个节点后添加一个尾节点 , 头结点和尾节点中不存储任何数据 , 只存储下一个节点的信息或者上一个节点的信息 。