Java实现单链表、栈、队列三种数据结构
回复“666”获取独家整理的学习资料！
作者：远航
cnblogs.com/yang-guang-zhang/p/13884023.html
一、单链表
1、在我们数据结构中，单链表非常重要。它里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成，在java集合框架里面 LinkedList、HashMap（数组加链表）等等的底层都是用链表实现的。
2、下面是单链表的几个特点：
数据元素在内存中存放的地址是不连续的：单链表的结点里面还定义一个结点，它里面保存着下一个结点的内存地址，在实例化对象的时候，jvm会开辟不同内存空间，并且是不连续的。
添加效率高：添加一个元素时，先找到插入位置的前一个，只需要将1，2个元素的连接断开，将插入结点的next指向第一个元素的next
（1），然后将第一个元素的next指向插入结点（2），
不用在挪动后面元素。
删除效率高：删除一个元素时，先找到删除位置，将前一个的next指向删除位置的next，不用在挪动后面元素。
查询效率低：查询的时候必须从头开始，依次遍历，而数组因为它的内存是连续的，可以直接通过索引查找。
3、下面通过代码来实现单链表结构：
package com.tlinkedList;
/**
* User:zhang
* Date:2020/10/26
**/
public class TLinkedList<T> {
private Node head;//链表头部
private int size;//链表元素的个数
public TLinkedList(){
head=null;
size=0;
}
// 将结点作为内部类。也可以新建一个Node类，作为结点
class Node{
private Node next;//下一个结点
private T t;//结点的数据
public Node(T t){
this.t=t;
}
public T getT() {
return t;
}
public void setT(T t) {
this.t = t;
}
}
// 在链表头部添加一个结点
public void addFirst(T t){
Node node = new Node(t);
node.next=head;
head=node;
size++;
}
// 在链表中间添加一个结点
public void addMid(T t,int index){
Node node = new Node(t);
Node mid=head;
for (int i = 0; i < index - 1; i++) {
mid=mid.next;
}
node.next=mid.next;
mid.next=node;
size++;
}
// 在链表尾部添加一个结点
public void addLast(T t){
Node node = new Node(t);
Node last=head;
while (last.next!=null){
last=last.next;
}
last.next=node;
node.next=null;
size++;
}
// 删除链表的头结点
public void removeFirst(){
head=head.next;
size--;
}
// 删除链表的中间元素
public void removeMid(int index){
Node mid=head;
if (index==0){
removeFirst();
return;
}
int j=0;
Node qMid=head;
while (j<index){
qMid=mid;
mid=mid.next;
j++;
}
qMid.next=mid.next;
size--;
}
// 删除链表的尾结点
public void removeLast(){
Node mid=head;
Node qMid=head;
while (mid.next!=null){
qMid=mid;
mid=mid.next;
}
qMid.next= null;
size--;
}
// 获取链表指定下标的结点
public Node get(int index){
Node mid=head;
if (index==0){
return head;
}
int j=0;
while (j<index){
mid=mid.next;
j++;
}
return mid;
}
public static void main(String[] args) {
TLinkedList<String> linkedList = new TLinkedList<>();
linkedList.addFirst("hello1");
linkedList.addFirst("hello2");
linkedList.addFirst("hello3");
for (int i = 0; i < linkedList.size; i++) {
System.out.println(linkedList.get(i).getT());
}
// linkedList.removeLast();
// linkedList.removeFirst();
// linkedList.addLast("hello4");
linkedList.addMid("hello",2);
System.out.println("--------------");
for (int i = 0; i < linkedList.size; i++) {
System.out.println(linkedList.get(i).getT());
}
}
}
结果如下：
二、栈(Stack)
1、一提到栈我们脑海就会浮现四个字“先进后出”，没错，它就是栈的最大特点。
2、栈的应用场景也非常多，比如将字符串反转、jvm里面的栈区等等。
3、栈里面的主要操作有：
-
push（入栈）：将一个数据元素从尾部插入 -
pop（出栈）：将一个数据元素从尾部删除 -
peek（返回栈顶元素）：将栈顶元素的数据返回
相当于只有一个开口就是尾部，只能从尾进，从尾出。
4、下面通过链表结构实现栈结构：
package com.tStack;
/**
* User:zhang
* Date:2020/10/26
**/
public class Test_Stack<T> {
private Node head;//栈的头结点
private int size;//栈的元素个数
class Node{
private Node next;//下一个结点
private T t;//结点的数据
public Node(T t){
this.t=t;
}
public T getT() {
return t;
}
public void setT(T t) {
this.t = t;
}
}
public Test_Stack() {
head=null;
size=0;
}
public static void main(String[] args) {
Test_Stack<String> TStack = new Test_Stack<>();
TStack.push("hello1");
TStack.push("hello2");
TStack.push("hello3");
for (int i = 0; i < 3; i++) {
System.out.println(TStack.pop());
}
}
// 入栈
public void push(T t){
Node node = new Node(t);
if (size==0){
node.next=head;
head=node;
size++;
return;
}
if (size==1){
head.next=node;
node.next=null;
size++;
return;
}
Node lastNode=head;
while (lastNode.next!=null){
lastNode=lastNode.next;
}
lastNode.next=node;
node.next=null;
size++;
}
// 出栈
public T pop(){
if (size==0){
System.out.println("栈内无值");
return null;
}
if (size==1){
T t = head.getT();
head=null;
size--;
return t;
}
Node lastNode=head;
Node qNode=head;
while (lastNode.next!=null){
qNode=lastNode;
lastNode=lastNode.next;
}
T t = lastNode.getT();
qNode.next=null;
size--;
return t;
}
// 获取栈里面元素的个数
public int getSize(){
return size;
}
// 返回栈顶元素
public T peek(){
if (size==0){
System.out.println("栈内无值");
return null;
}
if (size==1){
return head.getT();
}
Node lastNode=head;
while (lastNode.next!=null){
lastNode=lastNode.next;
}
return lastNode.getT();
}
}
结果：
三、队列(Queue)
1、队列的特点也用“先进先出”四个字来概括。就是先进去的元素先输出出来。
2、我们常见的消息队列就是队列结构实现的。
3、队列的常见操作如下：
-
put（入队）：将一个结点插入到尾部。 -
pop（出队）：将头结点的下一个结点作为头，然后将原来的头结点删除。
4、通过链表结构实现队列：
package com.tQueue;
/**
* User:zhang
* Date:2020/10/26
**/
public class TQueue<T> {
private Node front;//头结点
private Node tail;//尾结点
private int size;//队列中元素的个数
class Node {
private Node next;//下一个结点
private T t;//结点的数据
public Node(T t) {
this.t = t;
}
public T getT() {
return t;
}
public void setT(T t) {
this.t = t;
}
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
public TQueue() {
front = tail = null;
}
// 入队
public void put(T t) {
Node node = new Node(t);
if (size == 0) {
front = tail = node;
size++;
return;
}
Node lastNode = front;
while (lastNode.next != null) {
lastNode = lastNode.next;
}
lastNode.next = node;
tail = node;
size++;
}
// 出队
public T pop() {
if (size == 0) {
System.out.println("队列中无值");
return null;
}
T t = front.getT();
front=front.next;
size--;
return t;
}
public static void main(String[] args) {
TQueue<String> tQueue = new TQueue<>();
tQueue.put("Hello1");
tQueue.put("Hello2");
tQueue.put("Hello3");
for (int i = 0; i < 3; i++) {
System.out.println(tQueue.pop());
}
}
}
结果：
文章有不足之处，欢迎大家留言指正，谢谢大家啦！
热门内容： -
第 3 次读 Effective Java，这 58 个技巧最值！
-
10大黑客专用的 Linux 操作系统，每个都很酷！ -
Spring官方都推荐使用的@Transactional事务，为啥我不建议使用！
-
Java生鲜电商平台-监控模块的设计与架构
![]()
最近面试BAT，整理一份面试资料《Java面试BAT通关手册》，覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。
获取方式：点“在看”，关注公众号并回复 666 领取，更多内容陆续奉上。
明天见(｡･ω･｡)ﾉ♡
本文分享自微信公众号 - 方志朋（walkingstory）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
关注公众号 低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有，本站原创内容转载请注明来源。
- 上一篇
多线程问的太深入不知道怎么回答，从volatile开始给你讲清楚
volatile的用途 1.线程可见性 可见性是一种复杂的属性，因为可见性中的错误总是会违背我们的直觉。通常，我们无法确保执行读操作的线程能适时地看到其他线程写入的值，有时甚至是根本不可能的事情。为了确保多个线程之间对内存写入操作的可见性，必须使用同步机制。 可见性，是指线程之间的可见性，一个线程修改的状态对另一个线程是可见的。也就是一个线程修改的结果。另一个线程马上就能看到。比如：用volatile修饰的变量，就会具有可见性。volatile修饰的变量不允许线程内部缓存和重排序，即直接修改内存。所以对其他线程是可见的。但是这里需要注意一个问题，volatile只能让被他修饰内容具有可见性，但不能保证它具有原子性。比如 volatile int a = 0；之后有一个操作 a++；这个变量a具有可见性，但是a++ 依然是一个非原子操作，也就是这个操作同样存在线程安全问题。 package com.msb.testvolatile; public class T01_ThreadVisibility { private static volatile boolean fla...
- 下一篇
如何利用装饰者模式在不改变原有对象的基础上扩展功能
点击上方蓝色“ 方志朋 ”，选择“设为星标” 回复“666”获取独家整理的学习资料！ 作者：双子孤狼 blog.csdn.net/zwx900102/article/details/107740212 阅读目录 什么是装饰者模式 普通示例 装饰者模式示例 类图关系 装饰者模式使用场景 装饰者模式优点 装饰者模式缺点 什么是装饰者模式 装饰者模式（DecoratorPattern）是指在不改变原有对象的基础之上，将功能附加到对 象上，提供了比继承更有弹性的替代方案（扩展原有对象的功能），属于结构型模式。 装饰者模式在生活中也有很多形象的例子，比如说给蛋糕加上一些水果，给披萨加上榴莲，或者说给烧饼加上鸡蛋火腿之类等等。 下面我们就以给蛋糕加上水果为例来看看如果不用装饰者模式要怎么实现，如果使用装饰者模式又要怎么实现，对比之后就知道装饰者模式的优势了。 普通示例 新建一个普通的蛋糕类： packagecom.zwx.design.pattern.decorator.common; importjava.math.BigDecimal; publicclassCake{ ...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- CentOS关闭SELinux安全模块
- Docker快速安装Oracle11G，搭建oracle11g学习环境
- SpringBoot2初体验，简单认识spring boot2并且搭建基础工程
- CentOS7编译安装Gcc9.2.0，解决mysql等软件编译问题
- Docker安装Oracle12C，快速搭建Oracle学习环境
- SpringBoot2全家桶，快速入门学习开发网站教程
- SpringBoot2配置默认Tomcat设置，开启更多高级功能
- Eclipse初始化配置，告别卡顿、闪退、编译时间过长
- CentOS6,CentOS7官方镜像安装Oracle11G
微信收款码
支付宝收款码