【Java学习—

【Java学习—,第1张

(点击跳转即可哦)

java学习专栏

单链表

单链表:每个节点只保存了下个节点的地址,只能从头节点开始向后遍历,这种链表结构称为单向链表,简称单链表。

我们可以把单链表 类比 为火车,火车的不同车厢之间,都是通过一个挂钩连结的,当这两个车厢脱钩后,这两个车厢就没有任何关系了。

单链表在逻辑上是连续的。

节点类是什么呢?

每个链表的节点,就好比火车的每节车厢。由若干个链表节点构成的对象就是链表


节点类

假设现在每个节点上存储一个int 的值,那么它们之间的“挂钩”是什么啊,就是它们下节车厢的地址。

class Node{
    int val; //存储当前节点保存的值
    Node next;  //存储下一个节点的地址(若是不懂,继续看下面)
}


这些节点对象组成的一个大实体就是链表对象。

class SingleLinedList{
    Node head; //头节点,
    int size;  //存储的节点个数
}

在实际中,用户只需要使用单链表提供的增删改查即可。链表内部节点如何连接,如何遍历等细节用户都不关心,所以链表类的成员变量设为私有的。

节点类

class Node{  //什么都没有写,属于包权限,包内可见
    int val; //当前节点存储的值
    Node next; //下个节点的地址
}

链表类

public class SingleLineList{
    private Node head; //头节点的地址
    private int size;  //链表内的节点个数
}

增删改查等用户使用的方法就写在链表类的内部。

public void add(int val){
    Node node = new Node();
    node.val = val;
    if(head == null){ //此时链表内部没有节点,头节点为默认值null
        head = node;  //将第一个添加的节点地址设为头节点
    }else{  //此时链表内部已经有节点,头节点 head 不为空
        //使用单链表的头插法,新添加的节点成为新的头节点,旧的头节点逻辑上排在新节点的后面
        //将新添加的节点内的 next属性 写入旧的节点地址,也就是新节点未插入前的头节点地址
        node.next = head;
        //新的节点变为头节点
        head = node;
    }
    //增加了一个节点
    size++;
}

要注意else语句里面的顺序不能改变,否则就会丢失原先的链表头


查看链表

要注意的是,不能直接使用head来进行引用,否则遍历完一遍链表后,链表就会丢失。

public String toString(){
    String ret = "";
    //使用x来拷贝head保存的头节点地址,对x进行 *** 作,不会影响head
    Node x = head; 
    while(x != null){
        ret += x.val;
        ret += "->";
        //将保存的下个节点的地址传给x
        x = x.next;
    }
    return ret;
}

无头链表完整代码:

package dynamic_array;

public class SingleLinkedList {
    private Node head; //当前链表的头节点
    private int size; //存储节点的个数

    /**
     * z(头节点插入)
     *
     * @param val
     */
    public void addHead(int val) {
        Node node = new Node();
        node.val = val;
//        if(head == null){
//            head = node;
//        }else { //此时链表内不为空
//            //此时,head存储的是之前的头节点的地址,将上一个节点的地址传给新插入的头节点的next属性
//            node.next = head;
//            //将新的节点变为新的头节点
//            head = node;
//        }
        //优化
        if (head != null) { // 若链表内不为空地址,则把旧的头节点存入新节点的next
            node.next = head;
        }
        head = node;  //不管链表内空不空,都要将新插入的节点变为新的头节点
        size++;
    }

    /**
     * 在链表的index位置插入一个值val
     *
     * @param index
     * @param val
     */
    public void addIndex(int index, int val) {
        if (index < 0 || index > size) {  //当index == size,就是尾插
            System.out.println("index位置不合法");
            return;
        }
        if (index == 0) {  //index在头部
            addHead(val);
        } else {   //index不在头部,寻找index位置的前驱节点
            Node newNode = new Node();
            newNode.val = val;

            Node x = head;
            for (int i = 0; i < index - 1; i++) {
                x = x.next;
            } //x就是前驱节点
            newNode.next = x.next;
            x.next = newNode;
            size++;
        }

    }

    /**
     * 在链表的尾部进行插入,调用前面的 addIndex 方法
     *
     * @param val
     */
    public void addLast(int val) {
        addIndex(size, val);
    }

    /**查询方法
     *1 查询索引为 index 的元素值为多少
     *索引不合法时,输出索引不合法,并返回-1
     * @param index
     */
    public int find(int index) {
        if (pdIndexLegal(index)) {  //index 合法
            Node x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x.val;
        } else {
            System.out.print("index 索引不合法");
            return -1;
        }
    }

    /**
     *2 查询是否包含指定值是节点,若有,返回ture,没有返回false
     * @param val
     * @return
     */
    public boolean contains(int val){
        Node x = head;
        while (x != null){
            if(x.val == val){
                return true;
            }
            x = x.next;
        }
        return false;
    }

    /**
     *3 查询第一个值为 val 的索引为多少
     * @param val
     * @return
     */
    public int findOneVal(int val){
        Node x = head;
        int index = 0;
        while (x != null){
            if(x.val == val){
                return index;
            }
            x = x.next;
            index++;
        }
        return -1;
    }

    /** 修改方法
     * 修改索引值为 index 的节点值为 val
     * @param index
     * @param val
     */
    public void set(int index, int val){
        if(pdIndexLegal(index)){
            Node x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            x.val = val;
        }else {
            System.out.println("index不合法");
        }
    }

    /**删除方法
     * 1 删除索引为index 位置的元素,
     * @param index
     */
    public boolean delIndex(int index){
        if(pdIndexLegal(index)){
            if(index == 0){
                Node x = head;
                head = head.next;
                x.next = null;
                size--;
                return true;
            }else{
                Node x = head;
                for (int i = 0; i < index-1; i++) {
                    x = x.next;
                }//x 就是index的前驱节点
                Node indexNode = x.next;
                x.next = indexNode.next;
                indexNode.next = null;
                size--;
                return true;
            }
        }
        System.out.println("索引不合法");
        return false;
    }

    /**
     * 2 删除第一个值为 val 的元素
     * @param val
     * @return
     */
    public boolean delOneval(int val){
        if(findOneVal(val) != -1){
            int index = findOneVal(val);
            if(index == 0){
                Node x = head;
                head = head.next;
                x.next = null;
                size--;
            return true;
            }else {
                Node x = head;
                for (int i = 0; i < index-1; i++) {
                    x = x.next;
                }
                Node nextNode = x.next;
                x.next = nextNode.next;
                nextNode.next = null;
                return true;
            }
        }else {
            System.out.println("没有这个值");
            return false;
        }
    }
//    public boolean delOneVal(int val){
//        if(head == null){
//            System.out.println("链表为空");
//            return false;
//        }
//        if(head.val == val){
//            Node x = head;
//            head = head.next;
//            x.next = null;
//            size--;
//            return true;
//        }else{ //头节点元素不是val
//            Node x = head;
//            while(x.next != null){ //此节点后面还有节点
//                if(x.next.val == val){
//                    Node nextNode = x.next;
//                    x.next = nextNode.next;
//                    nextNode.next = null;
//                    size--;
//                    return true;
//                }
//                x = x.next;
//            }
//            System.out.println("没有val这个数");
//            return false;
//        }
//    }

    /**
     * 3 删除链表中所有值为 val 的元素
     * @param val 要删除的值
     * @return  返回boolean
     */
    public boolean delAllVal(int val){
        if(findOneVal(val) == -1){
            System.out.println("链表中没有这个值");
            return false; // 表示 链表中没有这个元素
        }
        while(head != null && head.val == val){
            Node x = head;
            head = head.next;
            x.next = null;
            size--;
        }
        if(head == null){
            return true;
        }else{
            Node x = head;
            while (x.next != null){
                if(x.next.val == val){
//                    Node nextNode = x.next;
//                    x.next = nextNode.next;
//                    nextNode.next = null;
                    x.next = x.next.next;
                    size--;
                }else {
                    x = x.next;
                }
            }
            return true;
        }

    }

    /**
     * 4 删除第一个链表的元素
     * @return 返回一个boolean ,删除成功返回 true
     */
    public boolean delfirst(){
        return delIndex(0);
    }

    /**
     * 5 删除链表的最后一个元素
     * @return 返回一个boolean ,删除成功返回 true
     */
    public boolean dellast(){
        return delIndex(size-1);
    }
    /**
     * 判断index是否合法,
     * @param index
     * @return
     */
    private boolean pdIndexLegal(int index){
        if(index < 0 || index >= size){
            return false;
        }
        return true;
    }


    @Override
    public String toString() {
        String ret = "";
        Node x = head;
        while (x != null){
            ret += x.val;
            ret += "->";
            x = x.next;
        }
        ret += null;
        return ret;
    }
    /**
     * 查看链表
     */

    public void show(){
        System.out.println(this); //指向了toString
    }
}
/**
 * 节点类
 */
class Node{
    int val;  //当前节点存储的值
    Node next; //存储下一个节点的地址
    public Node(){}

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

    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/729172.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-27
下一篇 2022-04-27

发表评论

登录后才能评论

评论列表(0条)

保存