我的漫漫程序之旅

专注于JavaWeb开发
随笔 - 39, 文章 - 310, 评论 - 411, 引用 - 0
数据加载中……

单向链表的简单实现

要求:写一个示例程序,显示一个单链表.这个链表的功能:
1.在链表头插入一个数据项
2.在链表头删除一个数据项
3.遍历链表显示它的内容
实现代码如下:
package com;
/**
 * 结点类
 * @author zdw
 *
 */
class Link
{
    //数据区域
    public int data;
    //指针区域
    public Link next;
    //构造一个数据为data的结点,默认指针为空
    public Link(int data)
    {
        this.data = data;
        next = null;
    }
    //显示结点的数据
    public void displayLink()
    {
        System.out.println("Data:" + data);
    }
}
/**
 * 链表类
 * @author zdw
 *
 */
class LinkList
{
    //头结点
    private Link first;
    //构造一个空的链表
    public LinkList()
    {
        first = null;
    }
    
    public void insertLink(int data)
    {
        //构造一个内容为data的结点
        Link newLink = new Link(data);
        //将first中的地址赋予新建的结点指针区域中
        newLink.next = first;
        //让first结点的指针指向newLink
        first = newLink;
    }
    //判断LinkList是否为空
    public boolean isEmpty()
    {
        return first == null;
    }
    
    public Link deleteLink()
    {
        //将first中保存到临时变量temp中
        Link temp = first;
        //将下一个结点的指针地址转移到first中
        first = first.next;
        return temp;
    }
    
    public void displayLinkList()
    {
        Link current = first;
        while(current != null)
        {
            current.displayLink();
            current = current.next;
        }
        System.out.println();
    }
}
/**
 * 测试类
 * @author zdw
 *
 */
public class LinkListApp
{
    public static void main(String[] args)
    {
        LinkList ll = new LinkList();
        ll.insertLink(1);
        ll.insertLink(2);
        ll.insertLink(3);
        ll.insertLink(4);
        System.out.println("linkList中的内容是:");
        ll.displayLinkList();
        //LinkList不为空
        while(!ll.isEmpty())
        {
            //删除
            ll.deleteLink();
        }
        System.out.println("删除后的内容是:");
        ll.displayLinkList();
    }

}
现在要求为该程序加入按指定键查找和删除的方法.并加以测试.
代码如下:
package com;

/**
 * 结点类
 * 
 * @author zdw
 * 
 */
class Link
{
    // 数据区域
    public int data;
    // 指针区域
    public Link next;

    // 构造一个数据为data的结点,默认指针为空
    public Link(int data)
    {
        this.data = data;
        next = null;
    }

    // 显示结点的数据
    public void displayLink()
    {
        System.out.println("Data:" + data);
    }
}

/**
 * 链表类
 * 
 * @author zdw
 * 
 */
class LinkList
{
    // 头结点
    private Link first;

    // 构造一个空的链表
    public LinkList()
    {
        first = null;
    }

    public void insertLink(int data)
    {
        // 构造一个内容为data的结点
        Link newLink = new Link(data);
        // 将first中的地址赋予新建的结点指针区域中
        newLink.next = first;
        // 让first结点的指针指向newLink
        first = newLink;
    }

    // 判断LinkList是否为空
    public boolean isEmpty()
    {
        return first == null;
    }
    //查找
    public Link find(int key)
    {
        //从第一个开始查找
        Link current = first;
        while(current.data != key)
        {
            if(current.next == null)
                return null;
            else
                return current.next;    
        }
        return current;
    }
    //用指定key删除
    public Link delete(int key)
    {
        Link current = first;
        Link previous = first;
        while(current.data != key)
        {
            if(current.next == null)
                return null;
            else
            {
                previous = current;
                current = current.next;
            }
        }
        if(current == first)
        {
            first = first.next;
        }
        else
        {
            previous.next = current.next;
        }
        return current;
    }
    
    public Link deleteLink()
    {
        // 将first中保存到临时变量temp中
        Link temp = first;
        // 将下一个结点的指针地址转移到first中
        first = first.next;
        return temp;
    }

    public void displayLinkList()
    {
        Link current = first;
        while (current != null)
        {
            current.displayLink();
            current = current.next;
        }
        System.out.println();
    }
}

/**
 * 测试类
 * 
 * @author zdw
 * 
 */
public class LinkListApp
{
    public static void main(String[] args)
    {
        LinkList ll = new LinkList();
        ll.insertLink(1);
        ll.insertLink(2);
        ll.insertLink(3);
        ll.insertLink(4);
        System.out.println("linkList中的内容是:");
        ll.displayLinkList();
        // LinkList不为空
        Link f = ll.find(3);
        if(f != null)
        {
            System.out.println("已经找到:" + f.data);
        }
        else
        {
            System.out.println("没有该项");
        }
        Link d = ll.delete(3);
        if(d != null)
        {
            System.out.println("成功删除:" + d.data);
        }
        else
        {
            System.out.println("没有该项");
        }
        System.out.println("删除后的内容是:");
        ll.displayLinkList();
    }

}


posted on 2007-12-29 12:08 々上善若水々 阅读(1768) 评论(0)  编辑  收藏 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: