2.链表

1.链表介绍

  链表是有序的列表，但是他在内存中的存储如下：

。

小结：

• 链表是以节点的方式存储
• 每个节点包含data域和next域(指向下一个节点)
• 如图:发现每个节点并不是一定连续的
• 链表分带头节点的链表和没有头节点的链表，根据实际情况而定

场景：创建一个链表

  链表新增：

package cn.com.linkedList;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
        singleLinkedList.add(heroNode1);
        singleLinkedList.add(heroNode2);
        singleLinkedList.add(heroNode3);
        singleLinkedList.add(heroNode4);
        singleLinkedList.list();
    }
}

//管理英雄
class SingleLinkedList {
    //1.定义一个头元素，只是表明头元素
    HeroNode head = new HeroNode(0, "", "");

    /**
     * 添加
     *
     * @param node
     */
    public void add(HeroNode node) {
        //定义一个临时变量，因为head不能变化，所以定义一个中间变量
        HeroNode tmp = head;
        //找到队列的最后一个元素，最后一个元素的next=null
        while (tmp.getNext() != null) {
            tmp = tmp.getNext();
        }
        tmp.setNext(node);
    }

    /**
     * 遍历输出
     */
    public void list() {
        if (head.getNext() == null) {
            System.out.println("链表为空！");
            return;
        }
        HeroNode tmp = head.getNext();
        //找到队列的最后一个元素，最后一个元素的next=null
        while (true) {
            if (tmp == null) {
                break;
            }
            System.out.println(tmp.toString());
            tmp = tmp.getNext();
        }
    }
}

class HeroNode {
    //英雄编号
    private int no;
    //英雄名称
    private String name;
    //艺名
    private String nickName;
    //下一个
    private HeroNode next;

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

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickName() {
        return nickName;
    }

    public void setNickName(String nickName) {
        this.nickName = nickName;
    }

    public HeroNode getNext() {
        return next;
    }

    public void setNext(HeroNode next) {
        this.next = next;
    }

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

package cn.com.linkedList;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
        singleLinkedList.add(heroNode1);
        singleLinkedList.add(heroNode2);
        singleLinkedList.add(heroNode3);
        singleLinkedList.add(heroNode4);
        singleLinkedList.list();
    }
}

//管理英雄
class SingleLinkedList {
    //1.定义一个头元素，只是表明头元素
    HeroNode head = new HeroNode(0, "", "");

    /**
     * 添加
     *
     * @param node
     */
    public void add(HeroNode node) {
        //定义一个临时变量，因为head不能变化，所以定义一个中间变量
        HeroNode tmp = head;
        //找到队列的最后一个元素，最后一个元素的next=null
        while (tmp.getNext() != null) {
            tmp = tmp.getNext();
        }
        tmp.setNext(node);
    }

    /**
     * 遍历输出
     */
    public void list() {
        if (head.getNext() == null) {
            System.out.println("链表为空！");
            return;
        }
        //head一定不为空，tmpp就是第一个有效数据
        HeroNode tmp = head.getNext();
        //找到队列的最后一个元素，最后一个元素的next=null
        while (true) {
            if (tmp == null) {
                break;
            }
            System.out.println(tmp.toString());
            tmp = tmp.getNext();
        }
        
        上述判断也可以这么写：
        HeroNode tmp = head;
        //找到队列的最后一个元素，最后一个元素的next=null
        while ((tmp=tmp.getNext())!=null) {
            System.out.println(tmp.toString());
        }
    }
}

class HeroNode {
    //英雄编号
    private int no;
    //英雄名称
    private String name;
    //艺名
    private String nickName;
    //下一个
    private HeroNode next;

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

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickName() {
        return nickName;
    }

    public void setNickName(String nickName) {
        this.nickName = nickName;
    }

    public HeroNode getNext() {
        return next;
    }

    public void setNext(HeroNode next) {
        this.next = next;
    }

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

输出：

HeroNode{no=1, name='宋江', nickName='及时雨'}
HeroNode{no=2, name='卢俊义', nickName='玉麒麟'}
HeroNode{no=3, name='吴用', nickName='智多星'}
HeroNode{no=4, name='林冲', nickName='豹子头'}