单链表深拷贝的实现

相比于顺序表的深拷贝，单链表的原理就简单多了。只需要构造一个空的单链表、一个空的结点数组，然后将被拷贝的单链表的数据域依次赋值到结点数组的数据域上，最后再将结点数组依次连接到单链表上即可。
代码实例：

public class SinglyList<T> {
    public Node<T> head;                //头指针，指向单链表的头结点
    //（1）构造方法
    public SinglyList() {               //构造空单链表
        this.head = new Node<T>();
    }
    public SinglyList(T[] values) {     //构造单链表，由values数组提供元素
        this();                         //创建空链表，只有头结点
        Node<T> rear = this.head;       //rear指向头结点
        for(int i = 0; i < values.length; i++) {
            rear.next = new Node<T>(values[i], null);//尾插入，创建结点链入rear结点之后
            rear = rear.next;           //rear指向新的链尾结点
        }
    }
    public SinglyList(SinglyList<T> list) {  //单链表的深拷贝
        this();                              //构造空的单链表
        Node<T> p = list.head.next;
        Node<T>[] B = new Node[list.size()]; //构建一个长度与list相等的结点数组
        for(int i = 0; i < list.size(); i++) { //为结点数组中的每个结点添加数据
            B[i] = new Node<T>();              //这里注意要为每一个结点新建Node空间，否则会抛出NullPointerException异常
            B[i].data = p.data;
            p = p.next;
        }
        Node<T> front = this.head;
        for(int j = 0; j < list.size(); j++) { //将结点数组依次连接到链表中
            front.next = B[j];
            front = front.next;
        }
    }
}

测试代码：

public static void main(String[] args) {
    String[] x = {"asdf", "sdfsf", "oihiu"};
    SinglyList<String> A = new SinglyList<String>(x);
    SinglyList<String> B = new SinglyList<String>(A);
    System.out.println(B.toString());
    B.remove(1);
    System.out.println(A.toString());
    System.out.println(B.toString());
}

输出结果：

可见对B进行的remove操作对A没有产生影响，说明深拷贝成立。