分类: Java > 数据结构

链表java实现

发表于3年前(Dec 24, 2014 10:26:19 AM)  阅读 718  评论 0

分类: Java 数据结构

标签: LinkedList LinkList 双向链表 链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,链表比较方便插入和删除操作。—-摘自百度百科。

只包含下一个节点的指针,这样的链表叫单向链表,如果还包含上一个链表的指针叫双向链表。在双向链表里,如果一个节点的上一个节点地址为空,则表示该节点为第一个节点,如果下一个节点的地址为空,则表示该接点为最后一个节点,如果两个都为空,表示该链表只有一个元素(数据不为空)或链表为空(数据为空)。 如果最后一个节点的下一个节点地址为第一个节点,这样的链表叫循环链表。

队列java实现

发表于3年前(Dec 24, 2014 10:24:48 AM)  阅读 681  评论 0

分类: Java 数据结构

标签: FIFO queue 先进先出 队列

队列和栈相反,是先进先出(FIFO,first in first out)的数据集合。就跟排队打饭一样,最先进入队伍的总是最先离开。

队列元素的操作一般由入列(enQueue)和出列(deQueue)组成。 按照通常理解,如果队首的人离开,队伍中所有的人将往前挪一个位置,在下面的代码里,我没有这么做,因为如果每次出列都进行一次平移,就造成了多次元素交换,影响效率,当然如果你不在乎可以进行平移。取而代之的是,用两个索引head跟tail来标记当前队首跟队尾元素的索引,避免了移位。在这里,没有实现队列的自动增长,使用索引来标记队首队尾元素,增加了自动增长的难度,其实也很简单,只是暂时觉得没有必要实现。

栈java实现

发表于3年前(Dec 24, 2014 10:23:52 AM)  阅读 768  评论 0

分类: Java 数据结构

标签: lifo stack 后进先出

栈是一种后进先出(LIFO,last in first out)的数据集合。可以把栈看成餐馆中用来放盘子的、里面安装了弹簧的栈,盘子弹出的顺序跟被压入的顺序正好相反,因为在每一时刻,只有最顶上的盘子是可以拿到的。

栈中操作元素的方法通常为两种,压入(push)与弹出(pop)。先下的代码用java数组实现了栈,加入了栈的自动增长,关于自动增长要说的是,有些算法对于自动增长的时机以及自动增长的容量有特殊研究,这里只是简单的采用当数组满后将数组长度翻倍的做法。代码中自定义的异常StackOverFlowException只是简单实现了RuntimeException中的String构造方法,这里就不再给出,读者可以自行使用RuntimeException替代。对于泛型的使用请参考java中关于泛型的用法。