Java实现单链表、栈、队列三种数据结构

发布于 2021-05-08 11:46 ，所属分类：JAVA工程师开发学习资料

我们有助于升职加薪噢！

点击上方 “Java研究所”

设为“星标”，和你一起掌握更多数据库知识

单链表

1、在我们数据结构中，单链表非常重要。

它里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成，在java集合框架里面 LinkedList、HashMap（数组加链表）等等的底层都是用链表实现的。

2、下面是单链表的几个特点：

数据元素在内存中存放的地址是不连续的：单链表的结点里面还定义一个结点，它里面保存着下一个结点的内存地址，在实例化对象的时候，jvm会开辟不同内存空间，并且是不连续的。

添加效率高：添加一个元素时，先找到插入位置的前一个，只需要将1，2个元素的连接断开，将插入结点的next指向第一个元素的next

（1），然后将第一个元素的next指向插入结点（2），

不用在挪动后面元素。

删除效率高：删除一个元素时，先找到删除位置，将前一个的next指向删除位置的next，不用在挪动后面元素。

查询效率低：查询的时候必须从头开始，依次遍历，而数组因为它的内存是连续的，可以直接通过索引查找。

3、下面通过代码来实现单链表结构：

packagecom.tlinkedList;

/**
*User:zhang
*Date:2020/10/26
**/
publicclassTLinkedList<T>{
privateNodehead;//链表头部
privateintsize;//链表元素的个数
publicTLinkedList(){
head=null;
size=0;
}
//将结点作为内部类。也可以新建一个Node类，作为结点
classNode{
privateNodenext;//下一个结点
privateTt;//结点的数据
publicNode(Tt){
this.t=t;
}

publicTgetT(){
returnt;
}

publicvoidsetT(Tt){
this.t=t;
}
}
//在链表头部添加一个结点
publicvoidaddFirst(Tt){
Nodenode=newNode(t);
node.next=head;
head=node;
size++;
}
//在链表中间添加一个结点
publicvoidaddMid(Tt,intindex){
Nodenode=newNode(t);
Nodemid=head;
for(inti=0;i<index-1;i++){
mid=mid.next;
}
node.next=mid.next;
mid.next=node;
size++;
}
//在链表尾部添加一个结点
publicvoidaddLast(Tt){
Nodenode=newNode(t);
Nodelast=head;
while(last.next!=null){
last=last.next;
}
last.next=node;
node.next=null;
size++;
}
//删除链表的头结点
publicvoidremoveFirst(){
head=head.next;
size--;
}
//删除链表的中间元素
publicvoidremoveMid(intindex){
Nodemid=head;
if(index==0){
removeFirst();
return;
}
intj=0;
NodeqMid=head;
while(j<index){
qMid=mid;
mid=mid.next;
j++;
}
qMid.next=mid.next;
size--;
}
//删除链表的尾结点
publicvoidremoveLast(){
Nodemid=head;
NodeqMid=head;
while(mid.next!=null){
qMid=mid;
mid=mid.next;
}
qMid.next=null;
size--;
}
//获取链表指定下标的结点
publicNodeget(intindex){
Nodemid=head;
if(index==0){
returnhead;
}
intj=0;
while(j<index){
mid=mid.next;
j++;
}
returnmid;
}
publicstaticvoidmain(String[]args){
TLinkedList<String>linkedList=newTLinkedList<>();
linkedList.addFirst("hello1");
linkedList.addFirst("hello2");
linkedList.addFirst("hello3");
for(inti=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(inti=0;i<linkedList.size;i++){
System.out.println(linkedList.get(i).getT());
}
}
}

结果如下：

栈(Stack)

1、一提到栈我们脑海就会浮现四个字“先进后出”，没错，它就是栈的最大特点。

2、栈的应用场景也非常多，比如将字符串反转、jvm里面的栈区等等。

3、栈里面的主要操作有：

push（入栈）：将一个数据元素从尾部插入
pop（出栈）：将一个数据元素从尾部删除
peek（返回栈顶元素）：将栈顶元素的数据返回
相当于只有一个开口就是尾部，只能从尾进，从尾出。

4、下面通过链表结构实现栈结构：

packagecom.tStack;


/**
*User:zhang
*Date:2020/10/26
**/
publicclassTest_Stack<T>{
privateNodehead;//栈的头结点
privateintsize;//栈的元素个数
classNode{
privateNodenext;//下一个结点
privateTt;//结点的数据
publicNode(Tt){
this.t=t;
}

publicTgetT(){
returnt;
}

publicvoidsetT(Tt){
this.t=t;
}
}

publicTest_Stack(){
head=null;
size=0;
}

publicstaticvoidmain(String[]args){
Test_Stack<String>TStack=newTest_Stack<>();
TStack.push("hello1");
TStack.push("hello2");
TStack.push("hello3");
for(inti=0;i<3;i++){
System.out.println(TStack.pop());
}
}
//入栈
publicvoidpush(Tt){
Nodenode=newNode(t);
if(size==0){
node.next=head;
head=node;
size++;
return;
}
if(size==1){
head.next=node;
node.next=null;
size++;
return;
}
NodelastNode=head;
while(lastNode.next!=null){
lastNode=lastNode.next;
}
lastNode.next=node;
node.next=null;
size++;
}
//出栈
publicTpop(){
if(size==0){
System.out.println("栈内无值");
returnnull;
}
if(size==1){
Tt=head.getT();
head=null;
size--;
returnt;
}
NodelastNode=head;
NodeqNode=head;
while(lastNode.next!=null){
qNode=lastNode;
lastNode=lastNode.next;
}
Tt=lastNode.getT();
qNode.next=null;
size--;
returnt;
}
//获取栈里面元素的个数
publicintgetSize(){
returnsize;
}
//返回栈顶元素
publicTpeek(){
if(size==0){
System.out.println("栈内无值");
returnnull;
}
if(size==1){
returnhead.getT();
}
NodelastNode=head;
while(lastNode.next!=null){
lastNode=lastNode.next;
}
returnlastNode.getT();
}
}

结果：

队列(Queue)

1、队列的特点也用“先进先出”四个字来概括。就是先进去的元素先输出出来。

2、我们常见的消息队列就是队列结构实现的。

3、队列的常见操作如下：

put（入队）：将一个结点插入到尾部。
pop（出队）：将头结点的下一个结点作为头，然后将原来的头结点删除。

4、通过链表结构实现队列：

packagecom.tQueue;

/**
*User:zhang
*Date:2020/10/26
**/
publicclassTQueue<T>{
privateNodefront;//头结点
privateNodetail;//尾结点
privateintsize;//队列中元素的个数
classNode{
privateNodenext;//下一个结点
privateTt;//结点的数据

publicNode(Tt){
this.t=t;
}

publicTgetT(){
returnt;
}

publicvoidsetT(Tt){
this.t=t;
}
}
publicintgetSize(){
returnsize;
}

publicvoidsetSize(intsize){
this.size=size;
}

publicTQueue(){
front=tail=null;
}

//入队
publicvoidput(Tt){
Nodenode=newNode(t);
if(size==0){
front=tail=node;
size++;
return;
}
NodelastNode=front;
while(lastNode.next!=null){
lastNode=lastNode.next;
}
lastNode.next=node;
tail=node;
size++;
}

//出队
publicTpop(){
if(size==0){
System.out.println("队列中无值");
returnnull;
}
Tt=front.getT();
front=front.next;
size--;
returnt;
}

publicstaticvoidmain(String[]args){
TQueue<String>tQueue=newTQueue<>();
tQueue.put("Hello1");
tQueue.put("Hello2");
tQueue.put("Hello3");
for(inti=0;i<3;i++){
System.out.println(tQueue.pop());
}
}
}