Java 实现单链表、栈、队列三种数据结构，linux 内核编程入门篇
/**
*?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=n
ode;
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()?{
还未添加个人签名 2021.11.08 加入
还未添加个人简介
评论