数据结构链表之单链表-阿里云开发者社区

1.链表是以节点的方式来存储的

2.每个节点包含data域，next域，next域指向下一节点

3.链表的各个节点不一定是连续存储的(内存中不一定是连续存储的，但是我们为了学习，通常树上画出来的是有顺序的）

4.链表分为带头节点的链表和不带头节点的链表

头节点不存放数据，它只用来表示单链表的头

单链表的创建,显示

　创建：1，先创建头节点，作用是表示单链表的头

　　　　 2.后面每添加一个节点，就直接加入到链表的最后，需要用一个辅助指针

　遍历：通过一个辅助指针，帮助遍历整个单链表

下面是一个添加梁山好汉的例子：

package Queue.linkedlist;
public class SingleLinkedList{
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode = new HeroNode(1,"宋江","及时雨");
        HeroNode heroNode1 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode heroNode2 = new HeroNode(3,"无用","智多星");
        //创建单链表
        SingleLinkedListTest test = new SingleLinkedListTest();
        test.addHeroNode(heroNode);
        test.addHeroNode(heroNode1);
        test.addHeroNode(heroNode2);
        test.list();
    }
}
class SingleLinkedListTest{
    //初始化头节点,不存放数据
    HeroNode head = new HeroNode(0,"","");
    //添加节点,需要传入节点
    public void addHeroNode(HeroNode heroNode){
        //用一个辅助指针指向头节点
        HeroNode temp = head;
        //遍历链表
        while (true){
            //如果头节点指向的下一个为空，就是空链表
            if (temp.next == null){
                break;
            }
            //让辅助指针指向下一个链表
            temp = temp.next;
        }
        //当退出while循环时，temp指向链表的最后，然后将temp指向新的节点就ok
        temp.next = heroNode;
    }
    //遍历链表
    public void  list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //用一个辅助指针来试探，如果指针指向的下一个节点不为空，指针后移，如果为空，则试探到了尾节点
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将指针temp后移
            temp = temp.next;
        }
    }
}
//节点
class HeroNode{
    int no;//编号
    String name;//名字
    String nickName;//昵称
    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 + '\'' +
                '}';
    }
}

但是上述添加没有添加到指定的位置

按照顺序添加

　　1，首先找到新添加的节点的位置（应该放在什么地方的位置，通过辅助指针）

　2.新的节点.next = temp.next

　　3.将temp.next = 新的节点

package Queue.linkedlist;
public class SingleLinkedList{
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode = new HeroNode(1,"宋江","及时雨");
        HeroNode heroNode1 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode heroNode2 = new HeroNode(3,"无用","智多星");
        //创建单链表
        SingleLinkedListTest test = new SingleLinkedListTest();
        test.addByOrder(heroNode);
        test.addByOrder(heroNode2);
        test.addByOrder(heroNode1);
        test.list();
    }
}
class SingleLinkedListTest{
    //初始化头节点,不存放数据
    HeroNode head = new HeroNode(0,"","");
    //添加节点,需要传入节点
    public void addHeroNode(HeroNode heroNode){
        //用一个辅助指针指向头节点
        HeroNode temp = head;
        //遍历链表
        while (true){
            //如果头节点指向的下一个为空，就是空链表
            if (temp.next == null){
                break;
            }
            //让辅助指针指向下一个链表
            temp = temp.next;
        }
        //当退出while循环时，temp指向链表的最后，然后将temp指向新的节点就ok
        temp.next = heroNode;
    }
    //按顺序添加
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;//标志编号是否存在
        while (true){
            if (temp.next== null){
                break;
            }
            if (temp.next.no > heroNode.no){//找到位置
                break;
            }
            else if (temp.next.no == heroNode.no){
                flag = true;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("插入的编号已经存在");
        }
        else {
            //插入到temp后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
    //遍历链表
    public void  list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //用一个辅助指针来试探，如果指针指向的下一个节点不为空，指针后移，如果为空，则试探到了尾节点
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将指针temp后移
            temp = temp.next;
        }
    }
}
//节点
class HeroNode{
    int no;//编号
    String name;//名字
    String nickName;//昵称
    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 Queue.linkedlist;
public class SingleLinkedList{
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode = new HeroNode(1,"宋江","及时雨");
        HeroNode heroNode1 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode heroNode2 = new HeroNode(3,"无用","智多星");
        //创建单链表
        SingleLinkedListTest test = new SingleLinkedListTest();
//        test.addHeroNode(heroNode);
//        test.addHeroNode(heroNode2);
//        test.addHeroNode(heroNode1);
        test.addByOrder(heroNode);
        test.addByOrder(heroNode2);
        test.addByOrder(heroNode1);
        test.list();
        //测试修改
        HeroNode newHeroNode = new HeroNode(2,"卢俊义","小义");
        test.update(newHeroNode);
        test.list();
    }
}
class SingleLinkedListTest{
    //初始化头节点,不存放数据
    HeroNode head = new HeroNode(0,"","");
    //添加节点,需要传入节点
    public void addHeroNode(HeroNode heroNode){
        //用一个辅助指针指向头节点
        HeroNode temp = head;
        //遍历链表
        while (true){
            //如果头节点指向的下一个为空，就是空链表
            if (temp.next == null){
                break;
            }
            //让辅助指针指向下一个链表
            temp = temp.next;
        }
        //当退出while循环时，temp指向链表的最后，然后将temp指向新的节点就ok
        temp.next = heroNode;
    }
    //按顺序添加
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;//标志编号是否存在
        while (true){
            if (temp.next== null){
                break;
            }
            if (temp.next.no > heroNode.no){//找到位置
                break;
            }
            else if (temp.next.no == heroNode.no){
                flag = true;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("插入的编号已经存在");
        }
        else {
            //插入到temp后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
    //修改节点信息，根据和编号no,no不能修改
    public void update(HeroNode newHeroNode){
        //判空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //辅助指针
        HeroNode temp = head.next;
        boolean flag = false;
        while (true){
            if (temp == null){
                break;//遍历完了
            }
            if (temp.no == newHeroNode.no){
                flag = true;//找到
                break;
            }
            //继续遍历
            temp = temp.next;
        }
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }
        else {
            //没找到
            System.out.println("没有找到修改的编号");
        }
    }
    //遍历链表
    public void  list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //用一个辅助指针来试探，如果指针指向的下一个节点不为空，指针后移，如果为空，则试探到了尾节点
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将指针temp后移
            temp = temp.next;
        }
    }
}
//节点
class HeroNode{
    int no;//编号
    String name;//名字
    String nickName;//昵称
    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 + '\'' +
                '}';
    }
}

还要会单链表反转，获取倒数第k个节点，逆序打印单链表等

代码：

package linkedlist;
import java.util.Stack;
public class SingleLinkedList{
    public static void main(String[] args) {
        //测试
        //创建节点
        HeroNode heroNode = new HeroNode(1,"宋江","及时雨");
        HeroNode heroNode1 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode heroNode2 = new HeroNode(3,"无用","智多星");
        //创建单链表
        SingleLinkedListTest test = new SingleLinkedListTest();
//        test.addHeroNode(heroNode);
//        test.addHeroNode(heroNode2);
       // test.addHeroNode(heroNode1);
        test.addByOrder(heroNode);
        test.addByOrder(heroNode2);
        test.addByOrder(heroNode1);
        //打印链表
        System.out.println("打印链表------");
        test.list();
        //测试修改
//        HeroNode newHeroNode = new HeroNode(2,"卢俊义","小义");
//        test.update(newHeroNode);
//        test.list();
//        int length = test.getLinkedLength(SingleLinkedListTest.head);
//        System.out.println("length "+length);
//
//        HeroNode k = test.getKLiinkedList(SingleLinkedListTest.head , 5);
//        System.out.println("倒数第k个节点为  "+k);
//
        //反转链表
//        test.reverseLinkedList(SingleLinkedListTest.head);
//        System.out.println("反转后的链表");
//        test.list();
        //利用栈反转链表
        test.linkedStack();
    }
}
class SingleLinkedListTest{
    //初始化头节点,不存放数据
    static HeroNode head = new HeroNode(0,"","");
    //单链表反转,传入头节点
    public void reverseLinkedList(HeroNode head){
        //判空
        if (head.next == null || head.next.next == null){
            System.out.println("链表为空");
            return;
        }
        //定义辅助指针
        HeroNode temp = head.next;
        //指向当前节点的下一个节点的指针,因为在你取出当前节点的时候，需要另外一个指针指向下一个节点，不然链表断了
        HeroNode next = null;
        //定义一个新的节点
        HeroNode reverseNode = new HeroNode(0,"","");
        //遍历单链表,如果temp为空，则已经遍历完了
        while (temp != null){
            //指向下一个节点
            next = temp.next;
            //将temp的下一个节点指向新节点的最前端
            temp.next = reverseNode.next;
            //将当前节点指向新节点
            reverseNode.next = temp;
            //辅助指针temp后移
            temp = next;
        }
        //把原链表的头节点指向新链表的头节点
        head.next = reverseNode.next;
    }
    //从栈中取出，就达到了逆序打印单链表
    public void linkedStack(){
        Stack stack = printLinkedList(head);
        System.out.println("stack size() "+stack.size());
       while (stack.size() > 0){
            System.out.println("反转后的链表  "+stack.pop());
        }
    }
    //从尾到头打印单链表(利用栈），先将链表遍历，然后加入栈中
    public Stack printLinkedList(HeroNode head){
        Stack stack = new Stack();
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return null;
        }
        //用一个辅助指针来试探，如果指针指向的下一个节点不为空，指针后移，如果为空，则试探到了尾节点
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            //入栈
            stack.add(temp);
            //将指针temp后移
            temp = temp.next;
        }
        return stack;
    }
    //求链表的倒数第k个节点,传入头节点和倒数第几个
    public HeroNode getKLiinkedList(HeroNode head , int index){
        if (head.next == null){
            System.out.println("空链表");
            return null;
        }
        //链表长度
        int length = getLinkedLength(head);
        if (index > length || index <= 0){
            System.out.println("节点不存在");
            return null;
        }
        HeroNode temp = head.next;
        for (int i = 0 ; i < length - index ; i++){
            temp = temp.next;
        }
        return temp;
    }
    //求链表的长度,传入头节点
    public static int getLinkedLength(HeroNode head){
        //判断头节点的下一个节点是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return 0;
        }
        int length = 0;
        //定义一个辅助指针
        HeroNode temp = head.next;
        while (temp != null){
            length++;
            temp = temp.next;
        }
        return length;
    }
    //添加节点,需要传入节点
    public void addHeroNode(HeroNode heroNode){
        //用一个辅助指针指向头节点
        HeroNode temp = head;
        //遍历链表
        while (true){
            //如果头节点指向的下一个为空，就是空链表
            if (temp.next == null){
                break;
            }
            //让辅助指针指向下一个链表
            temp = temp.next;
        }
        //当退出while循环时，temp指向链表的最后，然后将temp指向新的节点就ok
        temp.next = heroNode;
    }
    //按顺序添加
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;//标志编号是否存在
        while (true){
            if (temp.next== null){
                break;
            }
            if (temp.next.no > heroNode.no){//找到位置
                break;
            }
            else if (temp.next.no == heroNode.no){
                flag = true;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("插入的编号已经存在");
        }
        else {
            //插入到temp后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
    //修改节点信息，根据和编号no,no不能修改
    public void update(HeroNode newHeroNode){
        //判空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //辅助指针
        HeroNode temp = head.next;
        boolean flag = false;
        while (true){
            if (temp == null){
                break;//遍历完了
            }
            if (temp.no == newHeroNode.no){
                flag = true;//找到
                break;
            }
            //继续遍历
            temp = temp.next;
        }
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }
        else {
            //没找到
            System.out.println("没有找到修改的编号");
        }
    }
    //遍历链表
    public void  list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //用一个辅助指针来试探，如果指针指向的下一个节点不为空，指针后移，如果为空，则试探到了尾节点
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将指针temp后移
            temp = temp.next;
        }
    }
}
//节点
class HeroNode{
    int no;//编号
    String name;//名字
    String nickName;//昵称
    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 + '\'' +
                '}';
    }
}

数据结构链表之单链表

热门文章

最新文章

相关课程

相关电子书