我这样写个链表，不知道合理不？

Question

class Node{
String data;
Node next;
public Node(){}
public Node(String data, Node next) {
this.data = data;
this.next = next;
}
}

public class List {
private Node head;
private int size=0;
public List(){
head = new Node(null,null);
}

[color=red] public void add(String data){
if(head.next==null){
head.data=data;
head.next = new Node(null,null);
}
Node temp=head;
while(temp.next!=null){
temp=temp.next;
}
temp.data=data;
temp.next=new Node(null,null);
size++;
}[/color]

public int getSize(){
    return size;
}

public void getNode(int i){
    int n=0;
    Node temp = head;   
    if (head.next != null) {   
        do {   
            temp = temp.next;
            n++;
        } while (n!=i);   
    }
    System.out.println(temp.data);
}


public void print(){
    Node temp=head;
    for(int i=0;temp!=null && i<size;i++){   
        temp=temp.next;   
        System.out.println(temp.data);
    }
}

public static void main(String[] args){
    List l = new List();
    l.add("a");
    l.add("b");
    l.add("c");
    l.add("d");
    l.print();
    l.getNode(4);
    System.out.println(l.getSize());
}

}

没有任何问题，但不知道这样写是不是正路子，呵呵。

Answer 1

[code="java"]public void add(String data){
if(head.next==null){
head.data=data;
head.next = new Node(null,null);
}
Node temp=head;
while(temp.next!=null){
temp=temp.next;
}
temp.data=data;
temp.next=new Node(null,null);
size++;
} [/code]

这样写不妥，集体可以参考LinkList类的实现，LinkList实现的双向链表，但是思想是一样的。

好的做法是插入的时候直接在链表头后面插入节点，这样插入节点在O(1)次就可以完成，而你的做法是在链表末尾插入节点，需要O(n)次。