java中的链表（之单链表）

   最近开始学习java的数据结构（确切地说，是用java实现的数据结构），首先，很大的感触是，和C实现链表的思想是相通的啊。数据结构本来就一样嘛。
  
   闲话少扯，直奔主题！
   先说链表吧，链表不同于以前我们学过的队列或数组，它是非线性的，即不是在内存中连续存储的。链表可以理解成由很多结点组成，很多人会把链表比喻为自行车的链条，窃以为，这样比喻是欠妥的，因为链条是连续的（哈哈哈哈，这个牛角尖钻的），或许可以将其理解为你手机里存的亲友手机号码，我们可以通过这个号码和那个人取得联系。我们一般将链表的一个结点分成两个部分：Data filed和Pointer field（这些是作者沿用C里的叫法），数据域用来存储数据，后面的指针域用来存放下一个结点的地址。
   结点的定义如下:
public class Node {

// local declaration
private Object obj;
private Node next;

// getters and setters
public Object getObj() {
return obj;
}
public void setObj(Object obj) {
this.obj = obj;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}

} // end class Node
   这段代码很清晰的表明了结点的组成内容。

   我的队列之链表实现版实现了以下几个功能：创建、增加、删除、插入、修改、打印、取指定位置的值以及取队列的大小。
   先选取其中的几个阐述一下，希望大家指正！
  1.删除：先上代码
// delete an item from list
public void del(int index){

     // counters
     int count = 0;

     // delete item
     if(index < 0 || index >= size()){
        throw new RuntimeException("Out of index:" + index);
     }else{
         if(index == 0){
    root = null;
}else{
    Node node = root.getNext();
    while(node != null){
count ++;
if(index == count){
    node.setNext(node.getNext().getNext());
}
node = node.getNext();
    } // end loop while
          } // end if-else
      } // end if-else

} // end method del
   删除的实现的一个难点是如何确认到达指定的index位置进行下一步操作。这里是首先定义了一个计数器，用以判断是否到达指定位置，当index==count时，就可以进行删除操作了，删除就是将index-1处得结点的next指向index+1处的结点，java的一个优点是，你不用像C一样人为地用free()函数释放空间，JVM会自动回收。个人强烈建议，在学数据结构时，拿支笔在纸上画画，这样可以将抽象的东西具体化，有利于理解。向链表中增加一个元素就是删除的逆过程了。此处不再赘述。

   2.插入：代码如下
// insert an item to list (follow item NO.index)
public void insert(int index, Object obj){

// counters
int count = 0;

if(index < 0 || index >= size()){
     throw new RuntimeException("Out of index: " + index);
}else{
     // insert
     if(index == 0){
        root.setObj(obj);
     }else{
        // create a new node
        Node insert = new Node();
        insert.setObj(obj);

        // insert it into the list
        Node node = root.getNext();
        while(node != null){
             count ++;
             if(index == count){
                insert.setNext(node.getNext());
                node.setNext(insert);
             }
             node = node.getNext();
        } // end loop while
     } // end if-else

} // end if-else

} // end method insert
   这段代码其实和删除的很像，只是在判断之间先创建一个insert结点并setObj了，而且，有一个很值得注意的地方是：必须先insert.setNext(node.getNext());否则就会出错，大道理上是和程序时自上而下执行是有关的。相信你懂的。
   这两段代码都得先比较index和size()进行比较，这是为了保持代码的健壮性。防止溢出。

   写这个的时候，我就在想，我写的东西很大一种程度上是给未来的自己看的，可以用作复习，可以用来找回忆，所以，总希望以一种轻松和谐的姿态行文。

   既然写了这么多，就继续扯点其他的吧，最近才发现，随着时间的推移，最初那种经常将C和Java搅在一起的局面已经一去不复返了，现在开始学着用Java解决一些以前用C解决的问题，通过这个过程，开始更加了解C和Java，二者的相似点和不同的地方也已经有点眉目了。欣慰啊，最开始同时学习的时候，总是有点担心，但是后来转念一想：C和Java都是计算机语言，没有必要将其完全分开，这才坚持了下来。过程虽然有点痛苦，但是结果还是有点满意。
   现在这个阶段，发现自己的C和java还是属于大菜阶段，但是，我一直固执地以为，只要我坚持了，就没有办不到的事，至少过去20年的经验这样告诉我的。编程的天才都是训练出来的！我是一个不相信天才的人（尽管曾经有人这样叫过我 ）。

   最后，以我桌面上的一句话结束这次对话吧：The minute you think of giving up, think of the reason why you held on so long.

评论

3 楼 cs小伙 2011-11-21  

The minute you think of giving up, think of the reason why you held on so long，记下这句话了

2 楼 Technoboy 2011-05-26  

the more you read, the more you gain

1 楼 kowloonchen 2011-05-26