基本数据结构——数组和链表

      数组的这个可以说是大家最广泛使用的数据结构了。数组的最主要的特点是可以支持随机存取，也就是说，我们查询一个值时，可以在O(1)时间内完成。如果我们在数组中删除一个元素，一般都是把后面元素向前移动，返回被删除的元素，如果插入一个新元素，我们把元素向后移动，留出一个空位，插入新元素。可见，删除和插入的时间复杂度为O(n)。 
      数组的特点是，我们在使用时需要先指定空间的大小（其实，我也可以采用一些变相的操作，来达到动态扩展空间的目的）。然而，使用链表，则可以动态的增加新的内存空间以保存新的元素。其实链表就像用一根绳子把一些珠子串起来。要访问链表中的一个元素时，必须顺着链表进行，直到找到我们要访问的元素，时间复杂度为O(n)，但是插入元素时，我们可以在O（1）时间内完成，比如直接插入到链表头的位置，再更新头指针位置。删除元素时，我们也可以在O(1)时间内完成，我们只需要修改删除元素前后元素的指针，使他们连接起来就可以了。 
      因此，如果是对于经常访问元素时，我们采用数组的方式来实现；如果是经常插入和删除元素时，我们采用链表来实现。

 
深入分析几个操作：
1）链表的反转 
      链表的反转可以采用递归的方式，当然也可以采用非递归的方式实现了。我这里说一下非递归的方式实现链表反转，非常简单，其实在面试过程中，经常遇到这个问题，我也遇到过好几次。使用3个指针就可以了。 
      returnNode表示反转链表的头指针，初始值为null 
      currentNode表示正在处理的节点，我们应该将此节点的指针反转，指向反转链表的头指针。其初始值为原来链表的头指针。 
      nextNode即将进行反转操作的下一个节点。

Java代码

public static Node reverse(Node head){
    Node returnNode=null,currentNode=head,next=null;

    while(currentNode!=null){
        //记录将要处理的下一个节点
    next=currentNode.next;
    //处理当前节点的指针
    currentNode.next=returnNode;
    //改变反转链表的头指针
    returnNode=currentNode;
    //继续处理下一个节点
    currentNode=next;
}

return returnNode;
}

 

2）两个有序链表的合并

Java代码

public static Node merge(Node a,Node b){
    //先建立一个哑节点
    Node dummy=new Node();
//head指向返回链表的头节点,c是指向返回链表的正在处理的节点；
Node head=dummy,c=head;
    while((a!=null)&&(b!=null)){
    if(less(a.value,b.value)){
    c.next=a;c=a;a=a.next;
}else{
    c.next=b;c=b;b=b.next;
}
}
c.next=(a= =null)?b:a;
return head.next;
}

 

      上面的操作就可以把两个有序的链表（我们假定都是升序）合并成一个有序的链表。注意，其实上面的代码也并是总能正确的工作，例如，若两个有序链表是相交的或者是有环的，需要进一步进行细腻的处理。

3）在链表上进行递归操作
例如，我们计算链表的元素的个数：

int count(Node h){
    if(h= = null) return 0;
    return 1+count(h.next);
}

      我们知道，递归操作其实是由系统在为我们维护一个栈，因此，如果链表非常长时，我们堆栈的深度为非常深，这样会导致堆栈的溢出，所以在链表上进行递归操作时，要特别注意这种情况，我们可以改成非递归的实现方式。