链表很灵活，长度不固定，分散存储弥补了数组长度固定的不足。链表有单链表，双向链表，循环链表等
我就写了个双向链表，实现了一些简单功能~
队列和栈可以用链表的形式和数组的形式实现，两者的区别在于前者的存储空间是分散的，后者是连续并且固定的。
一、实现双向链表
/**
* @author linqh0806
* @param <U>
*/
public class DoubleLinkedList<U> {
public static class Node<T> {
private Node<T> pre;
private Node<T> next;
private T val;
public Node() {
this.val = null;
this.pre = null;
this.next = null;
}
public Node(T val, Node<T> pre, Node<T> next) {
this.val = val;
this.pre = pre;
this.next = next;
}
}
private Node<U> nil;
private int size;
private Node<U> head;
public DoubleLinkedList() {
this.size = 0;
this.nil = new Node();
nil.next = nil;
nil.pre = nil; // 保证链表安全，在初始化链表为空时，插入数据不会报空指针错误
}
/**
* 在链表头插入数据
* @param val
*/
public void insert(U val) {
Node<U> newNode = new Node<U>();
newNode.val = val;
newNode.next = nil.next;
newNode.pre = nil;
nil.next.pre = newNode;
nil.next = newNode;
size++;
}
/**
* 删除链表中的node
* @param node
* @return
*/
public boolean delete(Node<U> node) {
Node<U> head = null;
head = nil;
while (head.next != nil) {
if (head.next.val == node.val) {
Node<U> nodetodelete = head.next; //将要删除的节点。这里很重要，如果使用node.next或者next.pre将造成空指针
//因为node是我们自己放进去的，他并不是在链表中的node
head.next = nodetodelete.next;
nodetodelete.next.pre = head;
nodetodelete=null;
size--;
return true;
}else
head=head.next;
}
return false;
}
// 正向输出链表
public void traverse() {
Node head = nil;
while (head.next != nil) {
System.out.println(head.next.val);
head = head.next;
}
}
//反向输出
public void reversOutput(){
Stack<U> stack=new Stack<U>();
Node head=nil;
while(head.next!=nil){
stack.push((U) head.next.val);
head=head.next;
}
while(!stack.empty()){
System.out.println(stack.pop());
}
}
public static void main(String[] args){
DoubleLinkedList<Character> doubleLinkedList=new DoubleLinkedList<>();
for(int i=48;i<60;i++){
doubleLinkedList.insert((char)i);
}
doubleLinkedList.delete(new Node<Character>('5',null,null));
doubleLinkedList.traverse();
System.out.println("-==-=-=-=-=-=-=-=-=-=-=-=-");
doubleLinkedList.reversOutput(); //测试反向输出
}
}
二、实现链式队列
public class Queue<T> {
/**
* 内部类，定义结点结构。
* @author linqh0806
* @param <U>
*/
class Node<U> {
U val;
Node<U> next;
Node() {
this.val = null;
this.next = null;
}
public Node(U val, Node<U> next) {
this.val = val;
this.next = next;
}
}
private int size;//声音队列的长度
Node<T> front;//指向队列的头引用
Node<T> rear;//指向队列末尾的引用
public Queue() {
Node<T> p = new Node<T>();
p.val = null;
p.next = null;
front = rear = p; //很重要，开始时将指向队列头尾的引用指向同一个结点。不然后面进队，出队会报空指针异常。
size = 0;
}
public void enqueue(T val) {
// Node<T> s = new Node<T>(val, null);
Node<T> s = new Node<T>();
s.val = val;
s.next = null;
rear.next = s; //新加入的结点放在末尾的后一位
rear = s; //将末尾引用指向新加入的结点
size++;
}
public T dequeue() {
if (size == 0)
return null;
else {
size--;
Node<T> p = front.next; //取出头结点，一开始头结点是空的，在构造函数初始化里面头尾引用指向一个空结点。因此第一个结点的front.next
front.next = p.next;
if (rear == p) { //相当于回到初始状态
rear = front;
}
}
return p.val;
}
public static void main(String[] args) {
String str = "Happy Weekend We are family";
Queue<String> queue = new Queue<String>();
for (String s : str.split(" ")) {
queue.enqueue(s);
}
while (queue.size > 0) {
System.out.println(queue.dequeue());
}
}
}
运行结果如下(先进先出FIFO)：
Happy
Weekend
We
are
family
三、实现链式栈
public class LinkedStack<T> {
public static class Node<U> {
private U val;
private Node<U> next;
Node() {
this.val = null;
this.next = null;
}
Node(U val, Node<U> next) {
this.val = val;
this.next = next;
}
boolean isEnd() {return this.next == null && this.val == null;}
}
public Node<T> top = new Node<>();
public void push(T val) {
top = new Node(val, top);
}
public T pop() {
if (top.isEnd())
return null;
else {
T val = top.val;
top = top.next;
return val;
}
}
public static void main(String[] args) {
String str = "Happy Weekend We are family";
LinkedStack<String> linkedStack = new LinkedStack<String>();
for (String s : str.split(" ")) {
linkedStack.push(s);
}
while (!linkedStack.top.isEnd()) {
System.out.println(linkedStack.pop());
}
}
}
运行结果如下(先进后出FILO)：
family
are
We
Weekend
Happy
代码比较简单，部分给出了说明，欢迎交流讨论~
写的不好的地方欢迎指出 （怎么调行间距，知道的求指导~）