当前位置: 老葡京网站娱乐 > 编程语言 > 算法 > 正文

Java中单向链表的实现:增删查改功能

时间:2014-07-11

老葡京网站娱乐 www.sdguanhua.com 写一个大家都比较熟悉的数据结构:单向链表。

不过先告诉大家一个小秘密,java的API里面已经提供了单向链表的类,大家可以直接拿来用,不过学习数据结构课程的时候想必大家也已经知道,虽然系统会给我们提供一些常用的数据结构,但是自定义的总是能够带来不同的喜感的,而且通过自己的编写也更能够让我们了解其中实现的过程,而且我们还可以写一些比较个性化的方法作为属于自己的数据结构。这里主要是介绍一些常用结构里面都会用到的方法,以及链表具体是如何操作的。

首先,单链表相对于队列的优势在于存储地址不是连续的,这样的意义在于,操作其中的某一个位置的元素时不需要对之前的其他元素都进行内存操作,大大的为我们的计算机减压了。下面直接进入正题:

先要定义一个结点类,如下:

Java代码

public class Node {  
        Node next;//下一个结点的引用  
        Object obj;//结点元素  
        public Node(Object obj){  
            this.obj=obj;  
        }  
}

然后就是我们的LinkedList类,先要定义一个空链表:

Node head=null;//创建一个空链表,头结点

Node last=head;//尾结点

打印链表有两种方法,可以采用递归,也可以使用非递归的方法,如下:

Java代码

/** 
* 非递归打印元素的方法 
*/
public void print(Node head){  
    while(head!=null){  
        System.out.println(head.obj);  
        head=head.next;//索引向后移位  
    }  
}  
/** 
 * 递归打印链表元素的方法 
 */
public void printNode(Node head){  
    if(head!=null){  
        System.out.println(head.obj);  
        Node node=head.next;  
        printNode(node);//递归调用  
    }  
}

非递归方法有一个致命的缺陷,打印的同时改变了头结点的位置,所以我们应该倾向于使用递归方法。

说了这么多,增删查改正式开始:

向链表中添加元素。判断一个链表已经到达末尾的依据是该结点的next引用已经为Null,所以要向末尾添加一个结点,先要把新增结点放在最后,再把末尾结点向后移位,具体操作过程如下图:      

代码如下:

Java代码

/** 
 * 向指定链表添加元素的方法 
 * @param obj   插入的元素 
*/
public void add(Object obj){  
    Node node=new Node(obj);//新建结点   
    if(head==null){//如果链表为空  
        head = node;  
    }else{  
        last.next=node;//先把新增结点放在最后  
    }  
    last=node;//再把最后一个结点向后移位  
}