问一个面试题，undo 和 redo

Question

如何实现一个可以增加一个节点、删除某个区间的节点、修改某个节点、undo和redo的链表？
前面三个不难，但是这个undo和redo怎么实现？请大家指点

Answer 1

package com.meran.memento;public class MementoDemo {
public static void main(String [] args){
Memento<String> m=new Memento<String>();
CareTaker<String> c=new CareTaker<String>(m);
Originator<String> o=new Originator(c);
o.insert("插入1");
o.insert("插入2");
o.state.display();
o.creteMemento();
System.out.println("创建备份点");
o.insert("插入3");
o.insert("插入4");
o.state.display();
System.out.println("恢复到上一个备份点");
o.undo();
o.state.display();
}}
class Originator<T>{
CareTaker<T> taker;
List<T> state ;
public Originator(CareTaker<T> taker){
state=new List<T>();
this.taker=taker;
}

public void creteMemento(){
Memento<T> mem=new Memento<T>();
mem.setState(state.clone());
taker.setMemento(mem);
}
public void SetState(List<T> state){this.state=state;}

public List<T> getState(){
return state;
}
public void undo(){
state=taker.mem.getState();
}
public void insert(T value){
state.insert(value);
}}
class List<T> implements Cloneable{

Node<T> header;
public List(){ header=new Node<T>();
header.next=header;
}
public List(Node<T> node){
header=node;
header.next=header;
}
public void insert(T value){
if(header.next==header){
Node<T> n=new Node<T>(value);
header.next=n;
n.next=header;


}
else{
Node<T> temp=new Node<T>(value);
Node<T> node=header.next;
header.next=temp;
temp.next=node;
}
}
public void display(){
for(Node<T> n=header.next;n!=header;n=n.next)
System.out.println(n.value+" "); }
@ Override
public List<T> clone(){
List<T> list=new List<T>();
list.header=new Node<T>();   
Node <T>  temp;
temp=list.header;
for(Node<T> n=header.next ;n!=header;n=n.next)
{   

temp.next=new Node<T>(n.value);
temp=temp.next;  
}
temp.next=list.header;
    
return  list;
} class Node<T>{
Node<T> next;
T value;
public Node(){
value=null;
}
public Node(T value){
this.value=value;

}
}
}
class Memento<T>{
List<T> state;
public void setState(List<T> state){
this.state=state;
}
public List<T> getState(){
return state;
}

}
class CareTaker<T>{
    Memento<T> mem;

    public CareTaker(Memento<T> mem){
     this.mem=mem;
    }
public void setMemento(Memento<T> mem){
this.mem=mem;
 
}
public Memento<T> getMemento(){
return mem;
}
}
给你个demo

Answer 2

undo应该是一个历史的版本回滚，redo应该是一个操作记录日志。

Answer 3

state设计模式，可以用一个Queue保存操作，然后可以恢复。

Answer 4

不是用Queue，而是用 Stack

Answer 5

用一个索引index记录当前的操作，undo就减1，redo就加1，操作一次节点index就加1

Answer 6

state 模式意图：
允许一个对象在其内部状态改变时候改变他的行为，看起来似乎修改了它的类。你用state 写个 demo 出来看看用 备忘录好 还是 state 好？ 

Answer 7

命令模式
http://www.cnblogs.com/springyangwc/archive/2011/04/13/2015456.html

Answer 8

command模式可以实现do、undo功能，可以看bob大叔的《敏捷软件开发-原则、模式与实践》里command模式章节有述

Answer 9

http://blog.csdn.net/zhai4902176/article/details/6934819
我的博客有详细代码