数据结构_用java实现单链表

数据结构_用ＪＡＶＡ实现单链表

一、先创建一个节点类

    package com.vnv;

//数据结构与算法JAVA语言版-单向链表例子笔记

//定义链表节点

public class IntNode {
    public int info; // 记录信息

    public IntNode next;// 指向下一节点的指针

    public IntNode(int i) { // 创建一个节点并把它的info定义并且把它的下一个指
        // 针指向null
        this(i, null);
    }

    public IntNode(int i, IntNode n) { // 这是初使化的地点，this(i,null)就指它
        info = i;
        next = n;
    }
}


  二、再创建下单链表类

package com.vnv;

public class IntSLList {
    private IntNode head, tail; // 定义指向头和尾的指针 注：此处的head和tail是IntNode类型的变量
                                //head 引用IntNode对象实例或持有IntNode对象实例的句柄

    public IntSLList() {
        head = tail = null; // 定义一开始使head和tail都为空，定义一个空链表
    }

    public boolean isEmpty() { // 判断链表是否为空，这算法偶是佩服了！
        return head == null;
    }

    public void addToHead(int el) { // 创建头指针，该方法只用一次！
        head = new IntNode(el, head); // 此时head的指为null进而初使化，我看为
        // 了节约代码才这么写！要不也可以写成head=new IntNode(el);
        // 拥有了指向第一个元素的指针咯！
        if (tail == null) // 若只有一个元素的化那么其尾指针指向头指针
            tail = head;// 第一次初使化的时候尾也有了！头也是它尾也是它！
    }

    public void addToTail(int el) { // 添加尾指针，该方法使用多次
        if (!isEmpty()) { // 若链表非空那么将尾指针的next初使化为一个新的元素
            tail.next = new IntNode(el); // 然后将尾指针指向现在它自己的下一个元素
            tail = tail.next;
        } else { // 如果为空则创建一个新的！并将头尾同时指向它！
            head = tail = new IntNode(el);// 这句可以有多种写法
        }
    }

    public int deleteFromHead() { // 删除头并且返回它的信息
        int el = head.info;
        if (head == tail) { // 如果只有一个元素或没有元素则一律清空为空链表
            head = tail = null;
        } else
            head = head.next; // 否则就把头指针后移
        return el;
    }

    public int deleteFromTail() { // 删除尾并返回它的info
        int el = tail.info;
        if (head == tail) // 和上面一样
            head = tail = null;
        else { // 如果不是上面那种情况就把tail设置到原来tail的上一个元素
            IntNode temp; // 这个是临时的
            for (temp = head; temp.next != tail; temp = temp.next)
                // 这循环很特殊咯！
                tail = temp; // 循环的目的自己想
            tail.next = null; // 把原来的尾设置为null
        }
        return el; // 返回
    }

    public void printAll() { // 输出所有的元素竟然没用Iterator强！
        for (IntNode temp = head; temp != null; temp = temp.next)
            System.out.println(temp.info + " ");
    }

    public boolean isInList(int el) { // 判断链表内是否有元素的info与参数相等
        IntNode temp; // 有个缺陷！只能判断出离head进的那一个！有多个就不行
        for (temp = head; temp != null && temp.info != el; temp = temp.next)
            ;// 仔细理解
        return temp != null; // 这个分号的作用
    }

    public void delete(int el) { // 通过el删除元素（有缺陷）
        if (!isEmpty()) // 若非空并且只有一个元素且头元素的info和el等
            if (head == tail && head.info == el) // 那么就删除头
                head = tail = null;
            else if (el == head.info) // 若非空并且el和头元素的info相等那么删除头
                head = head.next;
            else {
                IntNode pred, temp;
                for (pred = head, temp = head.next; temp != null
                        && temp.info != el; pred = pred.next, temp = temp.next)
                    ;// 又是分号咯！判断其el是否在表内！
                if (temp != null) { // 若非空则删除元素
                    pred.next = temp.next;
                    if (temp == tail) // 若为尾则删除尾
                        tail = pred;
                    tail.next = null;
                }
            }
    }
   
    public static void main(String [] args){
        IntSLList test=new IntSLList();
        test.addToHead(3);
        test.addToTail(5);
        test.addToTail(7);
        test.addToTail(9);
        test.deleteFromHead();
        test.delete(7);
        test.printAll();
    }
}