链表的实现

java 代码

/**
 *
 */
package link;

/**
 * @author sunxboy
 *
 */
public class Node {

    /**
     * 链表结构的特征：
     * 分二部分：
     * 第一部分为数据
     * 第二部分为地址，它指下一个节点
     */
    public int data;
    public Node next;

    public Node(int data) {
        this.data=data;
    }
}

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
java 代码

/**
 * 数据结构之链表
 */
package link;

/**
 * @author sunxboy
 *
 */
public class LinkTable {

    private Node head;

    /**
     * 在链表的最前面插入一个值
     * @param data 要插的数据
     * @return 是否成功
     */
    public boolean insertFirst(int data) {
        Node node= new Node(data);
        if(isEmpty()) {
            head = node;
            return true;
        }
        //将新插入的数的地址指向原来的第一位数
        node.next = head;
        //更新插入值后的新链表的头
        head = node;
        return true;
    }

    /**
     * 在链表的最末插入一个值
     * @param data 要插入的数据
     * @return 是否成功
     */
    public boolean insertLast(int data) {
        Node node = new Node(data);
        if(isEmpty()) {
            node = head;
            return true;
        }
        Node p = head;
        Node pre = head;
        //遍历整个链表,从而最终得到一个最后的节点
        while(!isEnd(p)) {
            // 在向后移动之前得到一个节点
            pre = p;
            // 逐次向后移动
            p = p.next;
        }
        // 将要插入的值插入到最后一个节点上
        pre.next = node;
        return false;
    }

    /**
     * 在某节点前插入一新数据
     * @param oldData 原节点
     * @param newData 新节点
     * @return 是否插入成功
     */
    public boolean insert(int oldData,int newData) {
        Node preNode = find(oldData,true);
        if(preNode==null) {
            return false;
        }
        Node newNode = new Node(newData);
        if(preNode==head) {
            newNode.next=head;
            head = newNode;
        } else {
            Node pNode = preNode.next;
            newNode.next=pNode;
            preNode.next=newNode;
        }

        return true;
    }

    /**
     * 删除某一节点
     * @param data 节点数据
     * @return 是否删除成功
     */
    public boolean delete(int data) {
        if(isEmpty()) {
            return false;
        }
        Node preNode = find(data, true);
        if(preNode == head) {
            head = head.next;
        }else {
            Node pNode = preNode.next;
            preNode.next=pNode.next;
        }
        return true;
    }

    /**
     * 将某节点数据更新为新的数据
     * @param oldData
     * @param newData
     * @return
     */
    public boolean update(int oldData,int newData) {
        Node pNode = find(oldData, false);
        if(pNode!=null) {
            pNode.data = newData;
            return true;
        }
        return false;
    }

    /**
     * 查找数值为data的节点
     * @param flag 为false时表示返回要找数据的节点,
     *             为true时表示返回要找数据之前的节点
     * @param data 要查找的数值
     * @return
     */
    public Node find(int data,boolean flag) {

        Node p = head;
        Node pre = head;
        while(!isEnd(p)&& p.data!= data) {

            // 保存之前的信息
            pre = p;
            //逐次向后移动
            p = p.next;
        }
        if(isEnd(p)) {
            return null;
        }
        if(flag) return pre;
        else return p;
    }

    /**
     * 链表是否为空
     * @return
     */
    public boolean isEmpty() {
        return head==null;
    }

    /**
     * 此节点是否是最后一个节点
     * @param node 要判断的节点
     * @return 是否是最后一个节点
     */
    public boolean isEnd(Node node) {
        return node==null;
    }

    /**
     * 显示链表所有节点信息
     *
     */
    public void display() {
        Node pNode = head;
        while(pNode!=null) {
            System.out.println(pNode.data);
            pNode = pNode.next;
        }

    }

    public static void main(String[] args) {
        LinkTable lt=new LinkTable();
        lt.insertFirst(1);
        lt.insertFirst(2);
        lt.insertFirst(3);
        lt.insertLast(4);
        lt.insertLast(5);
        lt.insertLast(6);
        lt.insert(4, -2);
        lt.delete(6);
        lt.delete(3);
        lt.delete(4);
        lt.update(1, 100000);
        lt.display();
    }
}