Java数据结构之链表、栈、队列、树的实现方法示例
本文实例讲述了Java数据结构之链表、栈、队列、树的实现方法。分享给大家供大家参考，具体如下：
最近无意中翻到一本书，闲来无事写几行代码，实现几种常用的数据结构，以备后查。
一、线性表（链表）
1、节点定义
/**链表节点定义
*@authorcolonel
*
*/
classNode{
publicintdata;
Nodenext=null;
publicNode(intdata){
this.data=data;
}
}
2、链表操作类
/**链表操作类
*@authorcolonel
*
*/
publicclassoperateClass{
publicNodeheadNode=null;
/*给链表添加界节点
*@paramdata链表节点数据
*/
publicNodeaddNode(intdata){
NodenewNode=newNode(data);
if(headNode==null){
headNode=newNode;
newNode.next=null;
returnheadNode;
}
NodetempNode=headNode;
while(tempNode.next!=null){
//tempNode=headNode;
tempNode=tempNode.next;
}
tempNode.next=newNode;
returnheadNode;
}
/**删除节点
*@param删除节点的位置
*
*/
publicbooleandelNode(intindex){
if(index<1||index>length()){
returnfalse;
}
if(index==1){
headNode=headNode.next;
returntrue;
}
NodepreNode=headNode;
NodecurNode=preNode.next;
intcount=2;
while(curNode!=null){
if(count==index){
preNode.next=curNode.next;
returntrue;
}
preNode=curNode;
curNode=curNode.next;
count++;
}
returntrue;
}
/**取链表的长度
*@return返回链表的长度
*/
publicintlength(){
intlength=0;
Nodetemp=headNode;
while(temp!=null){
length++;
temp=temp.next;
}
returnlength;
}
/**按照值域对链表数据排序
*@return返回排序后的链表头节点
*/
publicNodeorderList(){
NodenextNode=null;
inttemp=0;
NodecurNode=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;
}
returnheadNode;
}
/**
*去除链表中值域重复的元素
*/
publicvoidredRepeat(){
if(length()<=1){
return;
}
NodecurNode=headNode;
while(curNode!=null){
NodeinsidNode=curNode.next;
NodeinsidPreNode=insidNode;
while(insidNode!=null){
if(insidNode.data==curNode.data){
insidPreNode.next=insidNode.next;
//return;
}
insidPreNode=insidNode;
insidNode=insidNode.next;
}
curNode=curNode.next;
}
}
/**倒序输出链表中所有的数据
*@paramhNode链表头节点
*/
publicvoidreversePrint(NodehNode){
if(hNode!=null){
reversePrint(hNode.next);
System.out.println(hNode.data);
}
}
/**
*从头节点开始到为节点结尾打印出值
*/
publicvoidprintList(){
NodetmpNode=headNode;
while(tmpNode!=null){
System.out.println(tmpNode.data);
tmpNode=tmpNode.next;
}
}
}
二、栈
1、该栈使用数组实现，具体的栈操作类
classMyStack{ privateObject[]stack; inttop=-1; publicMyStack(){ stack=newObject[10]; } publicbooleanisEmpty(){ returntop==0; } /**弹出栈顶元素（不删除） *@return */ publicEpeek(){ if(isEmpty()){ returnnull; } return(E)stack[top]; } /**出栈站顶元素 *@return栈顶元素 */ publicEpop(){ Ee=peek(); stack[top]=null; top--; returne; } /**压栈 *@paramitem待压元素 *@return返回待压元素 */ publicEpush(Eitem){ //ensureCapacity(top+1); stack[++top]=item; returnitem; } /**栈满扩容 *@paramsize */ publicvoidensureCapacity(intsize){ intlen=stack.length; if(size>len){ intnewLen=10; stack=Arrays.copyOf(stack,newLen); } } /**返回栈顶元素 *@return */ publicEgetTop(){ if(top==-1){ returnnull; } return(E)stack[top]; } }
三、队列
该队列使用链式实现
1、队节点定义
/** *@authorcolonel *队节点定义 *@param*/ classqueueNode { queueNode nextNode=null; Elemdata; publicqueueNode(Elemdata){ this.data=data; } }
2、队列操作类
/** *@authorcolonel *队列操作类 *@param*/ classMyQueue { privatequeueNode headNode=null; privatequeueNode tailNode=null; privatequeueNode lastNode=null; /**判断该队列是否为空 *@return返回trueorfalse */ publicbooleanisEmpty(){ returnheadNode==tailNode; } /**入队操作 *@paramdata节点元素值 */ publicvoidput(Elemdata){ queueNode newNode=newqueueNode (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返回出队元素 */ publicElempop(){ if(headNode==lastNode){ returnnull; } queueNode tempNode=headNode; ElemstatElem=tempNode.data; headNode=tempNode.nextNode; returnstatElem; } /**返回队列长度 *@return长度 */ publicintsize(){ if(isEmpty()){ return0; } intlength=0; queueNode temp=headNode; while(temp!=null){ length++; temp=temp.nextNode; } returnlength; } }
四、二叉树
1、节点定义
/**树节点定义
*@authorcolonel
*
*/
classTreeNode{
publicintdata;
publicTreeNodeleftNode;
publicTreeNoderightNode;
publicTreeNode(intdata){
this.data=data;
this.leftNode=null;
this.rightNode=null;
}
}
2、二叉树操作类
/**二叉排序树操作类
*@authorcolonel
*
*/
classOperateTree{
publicTreeNoderootNode;
publicOperateTree(){
rootNode=null;
}
/**元素插入二叉排序树
*@paramdata待插节点数据
*/
publicvoidinsert(intdata){
TreeNodenewNode=newTreeNode(data);
if(rootNode==null){
rootNode=newNode;
}else{
TreeNodecurrent=rootNode;
TreeNodeparent;
while(true){
parent=current;
if(datamyQueue=newLinkedList<>();
myQueue.add(rootNode);
while(!myQueue.isEmpty()){
TreeNodetempNode=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程序设计有所帮助。