Java数据结构之链表、栈、队列、树的实现方法示例

本文实例讲述了Java数据结构之链表、栈、队列、树的实现方法。分享给大家供大家参考,具体如下:

最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查。

一、线性表(链表)

1、节点定义

/**链表节点定义
 * @author colonel
 *
 */
class Node {
 public int data;
 Node next=null;
 public Node(int data){
 this.data=data;
 }
}

2、链表操作类

/**链表操作类
 * @author colonel
 *
 */
public class operateClass {
 public Node headNode=null;
 /*给链表添加界节点
 * @param data 链表节点数据
 */
 public Node addNode(int data){
 Node newNode=new Node(data);
 if (headNode==null) {
  headNode=newNode;
  newNode.next=null;
  return headNode;
 }
 Node tempNode=headNode;
 while (tempNode.next!=null) {
  //tempNode=headNode;
  tempNode=tempNode.next;
 }
 tempNode.next=newNode;
 return headNode;
 }
 /**删除节点
 * @param 删除节点的位置
 *
 */
 public boolean delNode(int index){
 if (index<1||index>length()) {
  return false;
 }
 if (index==1) {
  headNode=headNode.next;
  return true;
 }
 Node preNode=headNode;
 Node curNode=preNode.next;
 int count=2;
 while (curNode!=null) {
  if (count==index) {
  preNode.next=curNode.next;
  return true;
  }
  preNode=curNode;
  curNode=curNode.next;
  count++;
 }
 return true;
 }
 /**取链表的长度
 * @return返回链表的长度
 */
 public int length(){
 int length=0;
 Node temp=headNode;
 while (temp!=null) {
  length++;
  temp=temp.next;
 }
 return length;
 }
 /**按照值域对链表数据排序
 * @return 返回排序后的链表头节点
 */
 public Node orderList(){
 Node nextNode=null;
 int temp=0;
 Node curNode=headNode;
 while (curNode.next!=null) {
  nextNode=curNode.next;
  while (nextNode!=null) {
  if (curNode.data>nextNode.data) {
  temp=curNode.data;
  curNode.data=nextNode.data;
  nextNode.data=temp;
  }
  nextNode=nextNode.next;
  }
  curNode=curNode.next;
 }
  return headNode;
 }
 /**
 * 去除链表中值域重复的元素
 */
 public void redRepeat(){
 if (length()<=1) {
  return;
 }
 Node curNode=headNode;
 while (curNode!=null) {
  Node insidNode=curNode.next;
  Node insidPreNode=insidNode;
  while (insidNode!=null) {
  if (insidNode.data==curNode.data) {
   insidPreNode.next=insidNode.next;
   //return;
  }
  insidPreNode=insidNode;
  insidNode=insidNode.next;
  }
  curNode=curNode.next;
 }
 }
 /**倒序输出链表中所有的数据
 * @param hNode 链表头节点
 */
 public void reversePrint(Node hNode){
 if (hNode!=null) {
  reversePrint(hNode.next);
  System.out.println(hNode.data);
 }
 }
 /**
 * 从头节点开始到为节点结尾打印出值
 */
 public void printList(){
 Node tmpNode=headNode;
 while (tmpNode!=null) {
  System.out.println(tmpNode.data);
  tmpNode=tmpNode.next;
 }
 }
}

二、栈

1、该栈使用数组实现,具体的栈操作类

class MyStack<E>{
 private Object[] stack;
 int top=-1;
 public MyStack(){
 stack=new Object[10];
 }
 public boolean isEmpty(){
 return top==0;
 }
 /**弹出栈顶元素(不删除)
 * @return
 */
 public E peek(){
 if (isEmpty()) {
  return null;
 }
 return (E) stack[top];
 }
 /**出栈站顶元素
 * @return 栈顶元素
 */
 public E pop(){
 E e=peek();
 stack[top]=null;
 top--;
 return e;
 }
 /**压栈
 * @param item 待压元素
 * @return 返回待压元素
 */
 public E push(E item){
 //ensureCapacity(top+1);
 stack[++top]=item;
 return item;
 }
 /**栈满扩容
 * @param size
 */
 public void ensureCapacity(int size){
 int len=stack.length;
 if (size>len) {
  int newLen=10;
  stack=Arrays.copyOf(stack, newLen);
 }
 }
 /**返回栈顶元素
 * @return
 */
 public E getTop(){
 if (top==-1) {
  return null;
 }
 return (E) stack[top];
 }
}

三、队列

该队列使用链式实现

1、队节点定义

/**
 * @author colonel
 *队节点定义
 * @param <Elem>
 */
class queueNode<Elem>{
 queueNode<Elem> nextNode=null;
 Elem data;
 public queueNode(Elem data){
 this.data=data;
 }
}

2、队列操作类

/**
 * @author colonel
 *队列操作类
 * @param <Elem>
 */
class MyQueue<Elem>{
 private queueNode<Elem> headNode=null;
 private queueNode<Elem> tailNode=null;
 private queueNode<Elem> lastNode=null;
 /**判断该队列是否为空
 * @return 返回true or false
 */
 public boolean isEmpty(){
 return headNode==tailNode;
 }
 /**入队操作
 * @param data 节点元素值
 */
 public void put(Elem data){
 queueNode<Elem> newNode=new queueNode<Elem>(data);
 if (headNode==null&&tailNode==null) {
  headNode=tailNode=newNode;
  //tailNode=headNode.nextNode;
  lastNode=tailNode.nextNode;
  return;
 }
 tailNode.nextNode=newNode;
 tailNode=newNode;
 lastNode=tailNode.nextNode;
 //tailNode=tailNode.nextNode;
 }
 /**出队操作
 * @return 返回出队元素
 */
 public Elem pop(){
 if (headNode==lastNode) {
  return null;
 }
 queueNode<Elem> tempNode=headNode;
 Elem statElem=tempNode.data;
 headNode=tempNode.nextNode;
 return statElem;
 }
 /**返回队列长度
 * @return 长度
 */
 public int size(){
 if (isEmpty()) {
  return 0;
 }
 int length=0;
 queueNode<Elem> temp=headNode;
 while (temp!=null) {
  length++;
  temp=temp.nextNode;
 }
 return length;
 }
}

四、二叉树

1、节点定义

/**树节点定义
 * @author colonel
 *
 */
class TreeNode{
 public int data;
 public TreeNode leftNode;
 public TreeNode rightNode;
 public TreeNode(int data){
 this.data=data;
 this.leftNode=null;
 this.rightNode=null;
 }
}

2、二叉树操作类

/**二叉排序树操作类
 * @author colonel
 *
 */
class OperateTree{
 public TreeNode rootNode;
 public OperateTree(){
 rootNode=null;
 }
 /**元素插入二叉排序树
 * @param data 待插节点数据
 */
 public void insert(int data){
 TreeNode newNode=new TreeNode(data);
 if (rootNode==null) {
  rootNode=newNode;
 }else {
  TreeNode current=rootNode;
  TreeNode parent;
  while (true) {
  parent=current;
  if (data<current.data) {
   current=current.leftNode;
   if (current==null) {
   parent.leftNode=newNode;
   return;
   }
  } else {
   current=current.rightNode;
   if (current==null) {
   parent.rightNode=newNode;
   return;
   }
  }
  }
 }
 }
 /**构建二叉排序树
 * @param item 元素数组
 */
 public void buildTree(int[] item){
 for (int i = 0; i < item.length; i++) {
  insert(item[i]);
 }
 }
 /**
 * 先序遍历二叉树
 */
 public void preOrder(TreeNode root){
 if (root!=null) {
  System.out.println(root.data);
  preOrder(root.leftNode);
  preOrder(root.rightNode);
 }
 }
 /**中序遍历
 * @param root
 */
 public void inOrder(TreeNode root){
 if (root!=null) {
  inOrder(root.leftNode);
  System.out.println(root.data);
  inOrder(root.rightNode);
 }
 }
 /**后序遍历
 * @param root
 */
 public void afterOrder(TreeNode root){
 if (root!=null) {
  afterOrder(root.leftNode);
  afterOrder(root.rightNode);
  System.out.println(root.data);
 }
 }
 /**
 * 层序遍历二叉排序树
 */
 public void layerTrave(){
 if (this.rootNode==null) {
  return;
 }
 Queue<TreeNode> myQueue=new LinkedList<>();
 myQueue.add(rootNode);
 while (!myQueue.isEmpty()) {
  TreeNode tempNode=myQueue.poll();
  System.out.println(tempNode.data);
  if (tempNode.leftNode!=null) {
  myQueue.add(tempNode.leftNode);
  }
  if (tempNode.rightNode!=null) {
  myQueue.add(tempNode.rightNode);
  }
 }
 }

五、总结

更好的理解数据结构为何物,还需继续探索,谨记。by:colonel

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

(0)

相关推荐

  • 如何使用两个栈实现队列Java

    这篇文章主要介绍了如何使用两个栈实现队列Java,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 题目 用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 题解 描述 栈的特性是先进后出,队列的特点是先进先出,当数字依次入栈1后,依次出栈1并且压入栈2后,然后再出栈的顺序与进入栈1的顺序是一致的. 因此,进入队列通过压入栈1实现,弹出队列通过弹出栈2的栈顶元素实现,在弹出元素时需要保证当前栈弹出元素的顺序和队列弹

  • Java编程用两个栈实现队列代码分享

    题目:用两个栈来实现一个队列,完成队列的Push和Pop操作. 队列中的元素为int类型. 经典题,不多说,直接上代码 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { st

  • Java延迟队列原理与用法实例详解

    本文实例讲述了Java延迟队列原理与用法.分享给大家供大家参考,具体如下: 延时队列,第一他是个队列,所以具有对列功能第二就是延时,这就是延时对列,功能也就是将任务放在该延时对列中,只有到了延时时刻才能从该延时对列中获取任务否则获取不到-- 应用场景比较多,比如延时1分钟发短信,延时1分钟再次执行等,下面先看看延时队列demo之后再看延时队列在项目中的使用: 简单的延时队列要有三部分:第一实现了Delayed接口的消息体.第二消费消息的消费者.第三存放消息的延时队列,那下面就来看看延时队列dem

  • 浅谈Java消息队列总结篇(ActiveMQ、RabbitMQ、ZeroMQ、Kafka)

    一.消息队列概述 消息队列中间件是分布式系统中重要的组件,主要解决应用解耦,异步消息,流量削锋等问题,实现高性能,高可用,可伸缩和最终一致性架构.目前使用较多的消息队列有ActiveMQ,RabbitMQ,ZeroMQ,Kafka,MetaMQ,RocketMQ. 二.消息队列应用场景 以下介绍消息队列在实际应用中常用的使用场景.异步处理,应用解耦,流量削锋和消息通讯四个场景. 2.1异步处理 场景说明:用户注册后,需要发注册邮件和注册短信.传统的做法有两种 1.串行的方式;2.并行方式 a.串

  • 浅谈使用java实现阿里云消息队列简单封装

    一.前言 最近公司有使用阿里云消息队列的需求,为了更加方便使用,本人用了几天时间将消息队列封装成api调用方式以方便内部系统的调用,现在已经完成,特此记录其中过程和使用到的相关技术,与君共勉. 现在阿里云提供了两种消息服务:mns服务和ons服务,其中我认为mns是简化版的ons,而且mns的消息消费需要自定义轮询策略的,相比之下,ons的发布与订阅模式功能更加强大(比如相对于mns,ons提供了消息追踪.日志.监控等功能),其api使用起来更加方便,而且听闻阿里内部以后不再对mns进行新的开发

  • java实现消息队列的两种方式(小结)

    实现消息队列的两种方式 Apache ActiveMQ官方实例发送消息 直接在Apache官网http://activemq.apache.org/download-archives.html下载ActiveMQ源码 下载解压后拿到java代码实例 然后倒入IDE 如下: 请认真阅读readme.md文件,大致意思就是把项目打成两个jar包,然后启动服务,然后同时运行打的两个jar包,然后就能看到具体的调用信息.打jar包时直接利用maven打就行了,不用修改代码. 启动服务: 利用Spring

  • Java实现栈和队列面试题

    面试的时候,栈和队列经常会成对出现来考察.本文包含栈和队列的如下考试内容: (1)栈的创建 (2)队列的创建 (3)两个栈实现一个队列 (4)两个队列实现一个栈 (5)设计含最小函数min()的栈,要求min.push.pop.的时间复杂度都是O(1) (6)判断栈的push和pop序列是否一致 1.栈的创建: 我们接下来通过链表的形式来创建栈,方便扩充. 代码实现: public class Stack { public Node head; public Node current; //方法

  • java中栈和队列的实现和API的用法(详解)

    在java中要实现栈和队列,需要用到java集合的相关知识,特别是Stack.LinkedList等相关集合类型. 一.栈的实现 栈的实现,有两个方法:一个是用java本身的集合类型Stack类型:另一个是借用LinkedList来间接实现Stack. 1.Stack实现 直接用Stack来实现非常方便,常用的api函数如下: boolean        isEmpty() // 判断当前栈是否为空 synchronized E        peek() //获得当前栈顶元素 synchro

  • C语言数据结构之平衡二叉树(AVL树)实现方法示例

    本文实例讲述了C语言数据结构之平衡二叉树(AVL树)实现方法.分享给大家供大家参考,具体如下: AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树. 要维持这个树,必须在插入和删除的时候都检测是否出现破坏树结构的情况.然后立刻进行调整. 看了好久,网上各种各种的AVL树,千奇百怪. 关键是要理解插入的时候旋转的概念. // // AvlTree.h // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 201

  • Java数据结构之链表、栈、队列、树的实现方法示例

    本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth

  • Java数据结构学习之栈和队列

    一.栈 1.1 概述 Java为什么要有集合类: 临时存储数据. 链表的本质: 对象间通过持有和引用关系互相关联起来. 线性表: 普通线性表, 操作受限线性表(某些操作受到限制 --> 某一个线性表它的增删改操作受到限制) --> 栈 & 队列 1.1.1 线性表的概念 (1)线性表:n个数据元素的有序序列. ①首先,线性表中元素的个数是有限的. ②其次,线性表中元素是有序的. (2)那这个"序"指的是什么呢? ①除表头和表尾元素外,其它元素都有唯一前驱和唯一后继,

  • Java数据结构之链表相关知识总结

    一.链表 1.1 概述 链表是真正动态的数据结构,最简单的动态数据结构,基本用于辅助组成其他数据结构. 数据存储在"节点"(Node)中 优点:真正的动态,不需要处理固定容量的问题 缺点:丧失了随机访问的能力 1.2 链表使用的基本功能 定义Node节点 private class Node{ public E e; public Node next; public Node(E e, Node next){ this.e = e; this.next = next; } public

  • Java数据结构之链表(动力节点之Java学院整理)

    单链表: insertFirst:在表头插入一个新的链接点,时间复杂度为O(1) deleteFirst:删除表头的链接点,时间复杂度为O(1) find:查找包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) remove:删除包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) public class LinkedList { private class Data{ private Object obj; private Data next =

  • Java数据结构之链表详解

    一.链表的介绍 什么是链表 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 相比于线性表顺序结构,操作复杂.由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的

  • java 数据结构单链表的实现

    java 数据结构单链表的实现 单链表实现链表的打印及元素删除操作,链表的实现主要是next属性的定义,将一堆节点关联起来的.实现简单的链表如下: public class LinkNode { private int value; private LinkNode next; public LinkNode(int x) { value = x; } public LinkNode getNext(){ return next; } public void setNext(LinkNode n

  • Java数据结构之哈夫曼树概述及实现

    一.与哈夫曼树相关的概念 概念 含义 1. 路径 从树中一个结点到另一个结点的分支所构成的路线 2. 路径长度 路径上的分支数目 3. 树的路径长度 长度从根到每个结点的路径长度之和 4. 带权路径长度 结点具有权值, 从该结点到根之间的路径长度乘以结点的权值, 就是该结点的带权路径长度 5. 树的带权路径长度 树中所有叶子结点的带权路径长度之和 二.什么是哈夫曼树 定义: 给定n个权值作为n个叶子结点, 构造出的一棵带权路径长度(WPL)最短的二叉树,叫哈夫曼树(), 也被称为最最优二叉树.

  • Java数据结构之链表的增删查改详解

    一.链表的概念和结构 1.1 链表的概念 简单来说链表是物理上不一定连续,但是逻辑上一定连续的一种数据结构 1.2 链表的分类 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构. 单向和双向,带头和不带头,循环和非循环.排列组合和会有8种. 但我这只是实现两种比较难的链表,理解之后其它6种就比较简单了 1.单向不带头非循环链表 2.双向不带头非循环链表 二.单向不带头非循环链表 2.1 创建节点类型 我们创建了一个 ListNode 类为节点类型,里面有两个成员变量,val用来存储数值

  • Java数据结构之链表实现(单向、双向链表及链表反转)

    前言 之前学习的顺序表查询非常快,时间复杂度为O(1),但是增删改效率非常低,因为每一次增删改都会元素的移动.可以使用另一种存储方式-链式存储结构. 链表是一种物理存储单元上非连续.非顺序的存储结构.链表由一序列的结点(链表中的每一个元素成为结点)组成. 结点API设计: 类名 Node 构造方法 Node(T t,Node next) 创建Node对象 成员变量 T item:存储数据 Node next :指向下一个结点 结点类: public class Node<T>{ Node ne

随机推荐