数据结构之（四）链表

1. 链表

小结
（1）链表是节点的方式存储的
（2）每个节点包含data域，next域（指向下一个节点）
（3）如图：发现链表的各个节点不一定连续
（4）链表分带头结点的链表和不带头结点的链表，根据实际需求来定
逻辑结构

单链表的应用实例

使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作。

无顺序插入

package com.datastruct.demo.structure.linked;

/**
 * 定义Hero,每个Hero对象就是一个节点
 * @author Administrator
 */
public class HeroNode {
    private int no;
    public String name;
    public String nickname;
    /**
     * 指向下一个节点
     */
    public HeroNode next;

    public HeroNode(int no,String name,String nickname){
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + "}" ;
    }
}

package com.datastruct.demo.structure.linked;

/**
 * 定义SingleLinkedList 用于管理英雄
 */
public class SingleLinkedList {
    // 先初始化一个头结点，头结点不要动，不存放具体的数据
    private HeroNode head = new HeroNode(1,"","");

    /** 将节点添加到链表最后
     * 不考虑编号顺序时
     * 1.找到当前链表的最后节点
     * 2.将这个最后节点的next域指向新的节点
     * @param node
     */
    public void add(HeroNode node){
        // 因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = this.head;
        // 循环找最后的节点
        while (true){
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    /**
     * 显示链表
     */
    public void show(){
        if (head.next == null){
            System.out.println("链表为空");
        }
        // 头结点不能动，只能借助辅助变量
        HeroNode temp = this.head;
        while (temp.next != null){
            System.out.println(temp.next.toString());
            temp = temp.next;
        }
    }
}

按顺序插入

    /** )第二种方式在添加英雄时,根据排名将英雄插入到指定位置(如果有这个排名,则添加失败,并给出提示)
     * 考虑编号顺序时
     * 1.遍历
     * 2.新的节点的next = temp.next
     * 3.temp.next = 新的节点
     * @param node
     */
    public void addByOrder(HeroNode node){
/*         因为head节点不能动，因此我们需要一个辅助遍历temp,来找到插入的位置
        因为是单链表，所以temp是插入位置的前一个节点*/
        HeroNode temp = this.head;

        // 标志添加的编号是否存在，默认为False;
        boolean flag = false;
        // 循环找最后的节点
        while (true){
            if (temp.next == null) {
                break;
            }
            // 如果当前的下一个节点的编号比要插入的编号大，则插入在当前编号后边，（因为是单链表，顺序遍历）
            if (temp.next.no > node.no){
                // 返回要插入的上一个位置
                break;
            }else {
                if (temp.next.no == node.no){
                    // 说明链表中存在相同编号的节点
                    flag = true;
                    break;
                }
            }
            temp = temp.next;
        }
        if (false){
            System.out.printf("插入的新节点的编号%d已经存在，不能加入",node.no);
        }else {
            // 先节火车尾，再拼火车头
            node.next = temp.next;
            temp.next = node;
        }
    }

修改功能节点

 /** 修改节点的信息，根据no来修改，即no编号不能改
     * 1.根据node的no来修改
     * @param node
     */
    public void updata(HeroNode node){
        // 判断是否为空
        if (head.next == null){
            System.out.println("链表为空~");
            return;
        }
        // 遍历根据no找修改的节点
        HeroNode temp = this.head;
        // 标志是否找到节点
        boolean flag = false;
        while (true){
            if (temp == null){
                // 遍历结束（注意这里并不是temp.next==null）
                break;
            }
            if (temp.no == node.no){
                // 找到节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据flag，是否要修改节点信息
        if (flag){
            temp.name = node.name;
            temp.nickname = node.nickname;
        } else {
            System.out.println("没有找到该节点");
        }
    }

删除节点

大厂面试题

（1）单链表查询有效节点

    /**
     * 获取单链表节点的个数（忽略头结点）
     * @return 返回单链表的具体个数
     */
    public int getLength(){
        int length = 0;
        if (head.next == null){
            return length;
        }
        // 遍历
        HeroNode cur = this.head.next;
        while (cur != null){
            length ++;
            cur = cur.next;
        }
        return length;
    }

（2）查找单链表中的倒数第K个节点

 /**
     * 查找倒数第几个节点
     * 1.获取链表的总长度
     * 2.得到长度后，我们从链表的第一个开始遍历（size-index）个，就可以得到
     * 因为导数，默认指向第一个，假如三个导数第一个这就是第一个节点加2，也就是size - index
     * 如果找到了就返回，否则为NUll
     * @param index 倒数第几个节点
     * @return
     */
    public HeroNode findLastIndexNode(int index){
        if (this.head.next == null){
            return null;
        }
        // 得到链表的长度
        int size = getLength();
        if (index <= 0 || index > size){
            return null;
        }
        // 定义给辅助变量，循环拿到定位在倒数的index
        HeroNode cur = this.head.next;
        for (int i = 0;i <size - index;i++){
            cur = cur.next;
        }
        return cur;
    }

（3）单链表的反转


（4）从尾到头打印单链表


栈

    /**
     * 逆序打印
     * 可以利用栈这个数据结构，将各个节点压入栈中，然后利用栈的先进后出的特点，就实现了逆序打印
     */
    public void reversePrint(){
        if (this.head.next == null){
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        // 将链表的所有节点压入栈
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        // 将栈中的节点进行打印pop出栈
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }

双向链表应用实例

单向列表存在以下问题

1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
2. 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点

双向链表的操作分析与实现

注意节点类加上了一个pre指针，下面说明遍历、修改、添加、删除
（1）遍历：方向和单链表一样，不过可以向前、也可以向后
（2）添加：默认（添加到双向链表的最后）
1.先找到双向链表最后的节点
2.temp.next = newNode
3.newNode.pre = temp
（3）修改和原来的思路一样
（4）删除：因为是双向链表，因此可以实现自我删除某个节点
1.直接遍历找到要删除的节点temp
2.temp.pre.next = temp.next
3.temp.next.pre = temp.pre

package com.datastruct.demo.structure.linked.doublelinked;

/**
 * 定义Hero,每个Hero对象就是一个节点
 * @author Administrator
 */
public class HeroDoubleNode {
    public int no;
    public String name;
    public String nickname;
    /**
     * 指向下一个节点
     */
    public HeroDoubleNode next;

    /**
     * 指向上一个节点
     */
    public HeroDoubleNode pre;

    public HeroDoubleNode(int no, String name, String nickname){
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + "}" ;
    }
}

package com.datastruct.demo.structure.linked.doublelinked;

import com.datastruct.demo.structure.linked.singlelinked.HeroNode;
import com.fasterxml.jackson.databind.node.DoubleNode;

import java.util.Stack;

/** 双向列表
 * DoubleLinkedList 用于管理英雄
 */
public class DoubleLinkedList {
    // 先初始化一个头结点，头结点不要动，不存放具体的数据
    private HeroDoubleNode head = new HeroDoubleNode(0,"","");

    /** 将节点添加到双向链表最后
     * 		1.先找到双向链表最后的节点
     * 		2.temp.next = newNode
     * 		3.newNode.pre = temp
     * @param node
     */
    public void add(HeroDoubleNode node){
        // 因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroDoubleNode temp = this.head;
        // 循环找最后的节点
        while (true){
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        //
        temp.next = node;
        node.pre = temp;
    }

    /** )第二种方式在添加英雄时,根据排名将英雄插入到指定位置(如果有这个排名,则添加失败,并给出提示)
     * 考虑编号顺序时
     * 1.遍历
     * 2.新的节点的next = temp.next
     * 3.temp.next = 新的节点
     * @param node
     */
    public void addByOrder(HeroDoubleNode node){
//         因为head节点不能动，因此我们需要一个辅助遍历temp,来找到插入的位置
        HeroDoubleNode temp = this.head;

        // 标志添加的编号是否存在，默认为False;
        boolean flag = false;
        // 循环找最后的节点
        while (true){
            if (temp.next == null) {
                break;
            }
            // 如果当前的下一个节点的编号比要插入的编号大，则插入在当前编号后边，（因为是链表，顺序遍历）
            if (temp.next.no > node.no){
                // 返回要插入的上一个位置
                break;
            }else {
                if (temp.next.no == node.no){
                    // 说明链表中存在相同编号的节点
                    flag = true;
                    break;
                }
            }
            temp = temp.next;
        }
        if (flag){
            System.out.printf("插入的新节点的编号%d已经存在，不能加入\n",node.no);
        }else {
            node.next = temp.next;
            temp.next = node;
            node.pre = temp;
            // 避免插入后的节点是最后一个造成空指针
            if (temp.next != null){
                temp.next.pre = node;
            }
        }
    }

    /** 修改节点的信息，根据no来修改，即no编号不能改
     * 1.根据node的no来修改
     * @param node
     */
    public void updata(HeroDoubleNode node){
        // 判断是否为空
        if (head.next == null){
            System.out.println("链表为空~");
            return;
        }
        // 遍历根据no找修改的节点
        HeroDoubleNode temp = this.head;
        // 标志是否找到节点
        boolean flag = false;
        while (true){
            if (temp == null){
                // 遍历结束（注意这里并不是temp.next==null）
                break;
            }
            if (temp.no == node.no){
                // 找到节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据flag，是否要修改节点信息
        if (flag){
            temp.name = node.name;
            temp.nickname = node.nickname;
        } else {
            System.out.println("没有找到该节点");
        }
    }

    /**
     * 删除节点
     1.直接遍历找到要删除的节点temp
     2.temp.pre.next = temp.next
     3.temp.next.pre = temp.pre
     *
     */
    public void delete(int no){
        // 删除标志
        boolean flag = false;
        HeroDoubleNode temp = this.head.next;
       if (temp == null){
           System.out.println("链表为空，不能删除");
           return;
       }
       while (true){
           if (temp == null){
               break;
           }
           if (temp.no == no){
               flag = true;
               break;
           }
           // 后移
           temp = temp.next;
       }
       // 判断flag
        if (flag){
            // 找到
            temp.pre.next = temp.next;
            // 注意这里为了避免删除最后一个节点，不需要修pre指针，不然会空指针
            if (temp.next != null){
                temp.next.pre = temp.pre;
            }
        }else {
            System.out.println("找不到该节点");
        }

    }

    /**
     * 获取单链表节点的个数（忽略头结点）
     * @return 返回单链表的具体个数
     */
    public int getLength(){
        int length = 0;
        if (head.next == null){
            return length;
        }
        // 遍历
        HeroDoubleNode cur = this.head.next;
        while (cur != null){
            length ++;
            cur = cur.next;
        }
        return length;
    }



    /**
     * 显示双链表
     */
    public void show(){
        if (head.next == null){
            System.out.println("链表为空");
        }
        // 头结点不能动，只能借助辅助变量
        HeroDoubleNode temp = this.head;
        while (temp.next != null){
            System.out.println(temp.next.toString());
            temp = temp.next;
        }
    }


}

package com.datastruct.demo.structure.linked.doublelinked;

import com.datastruct.demo.structure.linked.singlelinked.HeroNode;
import com.datastruct.demo.structure.linked.singlelinked.SingleLinkedList;

/** 测试类
 * SingleLinkedListDemo
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        HeroDoubleNode heroNode1 = new HeroDoubleNode(1,"zlx","zlx");
        HeroDoubleNode heroNode2 = new HeroDoubleNode(2,"zlx1","zlx");
        HeroDoubleNode heroNode3 = new HeroDoubleNode(3,"zlx2","zlx");
        HeroDoubleNode heroNode4 = new HeroDoubleNode(4,"zlx3","zlx");
        // 创建链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.addByOrder(heroNode1);
        doubleLinkedList.addByOrder(heroNode2);
        doubleLinkedList.addByOrder(heroNode3);
        doubleLinkedList.addByOrder(heroNode4);
        doubleLinkedList.show();
    }
}