专栏首页技术碎碎念数据结构之链表、栈和队列 java代码实现

数据结构之链表、栈和队列 java代码实现

定义抽象节点类Node:

 1 package cn.wzbrilliant.datastructure;
 2 
 3 /**
 4  * 节点
 5  * @author ice
 6  *
 7  */
 8 public abstract class Node {
 9     private Node next;
10     
11     public Node(){
12         next=null;
13     }
14     
15     public void setNext(Node nextNode){
16         next=nextNode;
17     }
18     
19     public Node getNext(){
20         return next;
21     }
22 }

链表类,实现了插入首尾节点、指定位置节点,删除节点、指定位置节点,链表的逆序以及判空操作:

  1 package cn.wzbrilliant.datastructure;
  2 
  3 /**
  4  * 链表
  5  * @author ice
  6  *
  7  */
  8 public class Link {
  9     
 10     protected Node head;
 11     protected Node tail;
 12     protected int size;
 13 
 14     public Link() {
 15         this.head = null;
 16         this.tail = null;
 17         this.size = 0;
 18     }
 19     
 20     public void addAtFirst(Node node){
 21         node.setNext(head);
 22         head=node;
 23         if(size==0)
 24             tail=node;
 25         size++;
 26     }
 27     
 28     public void addAtLast(Node node){
 29         if(size==0){
 30             head=tail=node;
 31         }else{
 32             tail.setNext(node);
 33             tail=node;
 34         }
 35         node.setNext(null);
 36         size++;
 37     }
 38     
 39     public void removeFirst(){
 40         if(size==0)
 41             throw new RuntimeException("link size is 0...");
 42         head=head.getNext();
 43         if(size==1){
 44             tail.setNext(null);
 45         }
 46         size--;
 47     }
 48     
 49     public void removeLast(){
 50         if(size==0)
 51             throw new RuntimeException("link size is 0...");
 52         
 53         if(size==1){
 54             head=tail=null;
 55             size--;
 56             return ;
 57         }
 58         
 59         Node node=head;
 60         while(node.getNext()!=tail){
 61             node=node.getNext();
 62         }
 63         node.setNext(null);
 64         tail=node;
 65         size--;
 66     }
 67 
 68     /**
 69      * 队列逆序
 70      */
 71     public void reverse() {
 72         Node preNode, node, tempNode;
 73         if (size == 0)
 74             return;
 75         preNode = head;
 76         node = preNode.getNext();
 77         preNode.setNext(null);
 78         tail = preNode;
 79         while (node != null) {
 80             tempNode = node.getNext();
 81             node.setNext(preNode);
 82             preNode = node;
 83             node = tempNode;
 84         }
 85         head = preNode;
 86     }
 87 
 88     /**
 89      * 在第index个节点后插入newNode
 90      * 
 91      * @param newNode
 92      * @param index
 93      */
 94     public void insert(Node newNode, int index) {
 95         if (index < 0 || index > size)
 96             throw new RuntimeException("索引错误");
 97 
 98         if (index == 0) {
 99             newNode.setNext(head);
100             head = newNode;
101             size++;
102             return;
103         }
104 
105         if (index == size) {
106             newNode.setNext(null);
107             tail.setNext(newNode);
108             tail = newNode;
109             size++;
110             return;
111         }
112 
113         Node node = head;
114         for (int i = 1; node != null; i++, node = node.getNext()) {
115             if (i == index) {
116                 newNode.setNext(node.getNext());
117                 node.setNext(newNode);
118                 size++;
119                 return;
120             }
121         }
122 
123     }
124 
125     /**
126      * 移除Node节点    Node节点需重写equals()方法
127      * 
128      * @param node
129      */
130     public void remove(Node node) {
131         if (node == null || size == 0)
132             throw new RuntimeException("remove error...");
133         for (Node temp = head; temp != null; temp = temp.getNext()) {
134             if (temp == head) {
135                 if (temp.equals(node)) {
136                     head = head.getNext();
137                     size--;
138                     continue;
139                 }
140             }
141             if (temp.getNext().equals(node)) {
142                 temp.setNext(temp.getNext().getNext());
143                 size--;
144             }
145 
146         }
147     }
148 
149     public Node getFirst() {
150         if (size == 0)
151             return null;
152         return head;
153     }
154 
155     public Node getLast() {
156         if (size == 0)
157             return null;
158         return tail;
159     }
160 
161     public int size() {
162         return size;
163     }
164 
165     public boolean isEmpty() {
166         if (size == 0)
167             return true;
168         return false;
169     }
170 }

栈类,实现了入栈、出战、获取栈顶元素以及判空的操作:

 1 package cn.wzbrilliant.datastructure;
 2 
 3 /**
 4  * 栈
 5  * @author ice
 6  *
 7  */
 8 public class Stack {
 9     private int size;
10     private Node top;
11 
12     public Stack() {
13         size = 0;
14         top = null;
15     }
16 
17     public void push(Node node) {
18         node.setNext(top);
19         top = node;
20         size++;
21     }
22 
23     public Node pop() {
24         if (top == null)
25             return null;
26         Node node = top;
27         top = top.getNext();
28         size--;
29         return node;
30     }
31 
32     public Node top() {
33         return top;
34     }
35 
36     public int size() {
37         return size;
38     }
39 
40     public boolean isEmpty() {
41         if (size == 0)
42             return true;
43         return false;
44     }
45 }

队列类,实现了入队、出队、判空的操作:

 1 package cn.wzbrilliant.datastructure;
 2 
 3 /**
 4  * 队列
 5  * @author ice
 6  *
 7  */
 8 public class Queue {
 9 
10     private Node head;
11     private Node tail;
12     private int size;
13 
14     public Queue() {
15         this.head = null;
16         this.tail = null;
17         this.size = 0;
18     }
19 
20     public void enQueue(Node node) {
21         tail.setNext(node);
22         tail = node;
23         size++;
24     }
25 
26     public Node deQueue() {
27         if (size == 0)
28             return null;
29         Node node = head;
30         head = head.getNext();
31         size--;
32         return node;
33     }
34 
35     public int size() {
36         return size;
37     }
38 
39     public boolean isEmpty() {
40         if (size == 0)
41             return true;
42         return false;
43     }
44 
45 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 递归算法介绍及Java应用实战

    什么是递归算法 递归算法是把问题转化为规模缩小了的同类问题的子问题,然后递归调用函数(或过程)来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程...

    Java技术栈
  • ONOS集群选举分析

    首先简单介绍下自己,之前是做 floodlight 控制器开发的,鉴于 ODL 和 onos 的如火如荼的发展,如果不对了解点就感觉自己 OUT 了,因此忙里偷...

    SDNLAB
  • JSON Web Token (JWT)生成Token及解密实战。

    昨天讲解了JWT的介绍、应用场景、优点及注意事项等,今天来个JWT具体的使用实践吧。 从JWT官网支持的类库来看,jjwt是Java支持的算法中最全的,推荐使用...

    Java技术栈
  • Java父类强制转换子类原则

    最近,微信群友在讨论子类父类的转换问题,其实不难,给大家用实例来说明一下就很明了了。 我们知道Java中子类转换成父类是没有任何问题的,那父类可以转换成子类吗?...

    Java技术栈
  • 栈和队列就是这么简单

    一、前言 上一篇已经讲过了链表【Java实现单向链表】了,它跟数组都是线性结构的基础,本文主要讲解线性结构的应用:栈和队列 如果写错的地方希望大家能够多多体谅并...

    Java3y
  • Java对象引用四个级别(强、软、弱、虚)

    最近,高级Java技术栈微信群中,有一些猿友在讨论JVM中对象的周期问题,有谈到引用的级别,现在为大家做个总结吧,虽然大多数公司并没有意识或者用到这些引用,但了...

    Java技术栈
  • 史上最全Java多线程面试题及答案

    多线程并发编程是Java编程中重要的一块内容,也是面试重点覆盖区域。所以,学好多线程并发编程对Java程序员来来说极其重要的。 下面小编整理了60道最常见的Ja...

    Java技术栈
  • 为什么Netty这么火?与Mina相比有什么优势?

    Netty是什么?为什么这么火? Netty是目前最流行的由JBOSS提供的一个Java开源框架NIO框架,Netty提供异步的、事件驱动的网络应用程序框架和工...

    Java技术栈
  • Java实现单向链表

    一、前言 最近在回顾数据结构与算法,有部分的算法题用到了栈的思想,说起栈又不得不说链表了。数组和链表都是线性存储结构的基础,栈和队列都是线性存储结构的应用~ 本...

    Java3y
  • Java中的6颗语法糖

    来源:http://blog.csdn.net/danchu/article/details/54986442 ? 语法糖(Syntactic Sugar),也...

    Java技术栈

扫码关注云+社区

领取腾讯云代金券