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程序设计有所帮助。

来源：https://blog.csdn.net/sinat_34322082/article/details/53694315