我们都知道链表作为一种存储空间不连续的数组,需要有引用或者指针来指向下一个,在java中,虽然没有指针,但是也大同小异,那怎么用java语言实现一个简单的链表呢?
首先我们要明确,链表是由结点构成的,所以我们要先构造一个结点类
这个结点类的属性有:存储的值,对下一个结点的链接。
以及设置和取得他们的方法
package com.LinkList20180828;
public class Node {
private int data;
private Node next;
public int getData() {
return data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node(int data) {
this.data=data;
}
}
这只是一个简单的结点,根据需要,他还可以有更多的属性和方法
接下来就是将结点汇成链表,用根结点来表示,你可能会奇怪,一个结点怎么可能表示一个链表呢?链表可能有无数个结点呢。其实很简单,每个Node的next都连上下一个结点,所以我们只要找到最开始的Node就行,不断循环的next会将所有的点连接起来
而从尾到头输出,用栈就可以解决,将结点们依次放入栈中,再依次取出,即可
所以,我们的代码很简单
在main方法中,创建一个头结点,并不断创建其next结点。
在printListFromTailToHead中,让头结点和其next结点们放入stack中
然后再构造一个队列依次放入从stack中取出的结点
package com.LinkList20180828;
import java.util.ArrayList;
import java.util.Stack;
public class List {
public ArrayList<Integer> printListFromTailToHead(Node node) {
//传入的结点为头结点,其next连接了很多结点
Stack<Integer>stack=new Stack<Integer>();
while(node!=null) {
//只要下一个结点不为空,就将其放入栈中
stack.push(node.getData());
node=node.getNext();
}
//新构建一个队列来获取从栈中取出的结点
ArrayList<Integer>list=new ArrayList<Integer>();
while(!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
public static void main(String [] args) { List list=new List(); int length=10; Node node=new Node (1); Node cur=node;//cur和node指向同一片区域,即对cur的next结点增多后,node也可以调用 for(int i=2;i<length;i++) { cur.setNext(new Node(i)); cur=cur.getNext(); } System.out.println(list.printListFromTailToHead(node)); } }
输入为1-9,输出结果如下
[9, 8, 7, 6, 5, 4, 3, 2, 1]