单链表(Java--尚硅谷)

基础知识

大体结构和C++的链表差不多

补充之前不知道的：链表分两类，带和不带头结点的链表现在才知道，Java没有像C/C++那样的指针

首先创建一个LinkList类，然后把链表的各个功能添加进去

创建结点

//当不考虑编号顺序时，找到当前链表最后节点，将最后节点next指向新节点

public void add(PersonNode node) {

    //因为头节点不能动，先需要一个辅助遍历节点temp

    PersonNode temp = head;

    while (true) {//遍历链表，找到最后

        if (temp.next == null) {

            break;

        }

        temp = temp.next;//如果没到最后，就继续找下去

    }//当退出while循环时，temp指向链表的最后

    temp.next = node;

}

添加结点(乱序)

public void addByOrder(PersonNode node) {

    //因为头节点不移动，仍通过一个辅助变量来找添加的位置

    //因为是单链表，所以找的temp时位于添加位置的前一个结点，否则不能插入

    PersonNode temp = head;

    boolean flag = false;//标识添加的编号是否存在

    while (true) {

        if (temp.next == null) //说明temp在链表最后

            break;

        if (temp.next.no > node.no) {//位置找到了，就在temp后面

            break;

        } else if (temp.next.no == node.no) {//希望添加的编号已存在

            flag = true;

            break;

        }

        temp = temp.next;

    }

    if (flag) {//编号已存在，不能添加

        System.out.println("already exist no." + node.no + ", you can't add it.=====");

    } else {

        node.next = temp.next;

        temp.next = node;

    }

}//最终还是按照序号来排列

编辑结点

public void edit(PersonNode node) {//这里直接引入外部结点，根据node.no来寻找需要修改的结点

    if (head.next == null) {

        System.out.println("empty LinkList====");

        return;

    }

    PersonNode temp;

    temp = head.next;

    boolean flag = false;//判断是否找到该结点

    while (true) {

        if (temp == null)

            break;//到了链表最后

        if (temp.no == node.no) {

            flag = true;//找到

            break;

        }

        temp = temp.next;

    }

    //根据flag判断是否找到

    if (flag) {

        temp.name = node.name;

        temp.score = node.score;

    } else {

        System.out.println("not found no." + node.no + "====");

    }

    System.out.println("=======");

}

删除结点

public void delete(int no) {

    if (head.next == null) {

        System.out.println("empty LinkList===");

        return;

    }

    PersonNode temp = head;//temp指向待删除结点的前一个结点

    boolean flag = false;

    while (true) {

        if (temp.next == null) {

            break;//已经到链表最后

        }

        if (temp.next.no == no) {

            flag = true;//找到了待删除结点的前一个结点temp

            break;

        }

        temp = temp.next;

    }

    if (flag) {

        temp.next = temp.next.next;

    //Java会自动回收未被访问的数据

    } else {

        System.out.println("not found====");

    }

    System.out.println("====");

}

打印链表

public void list() {

    //判断链表是否为空

    if (head.next == null) {

        System.out.println("empty LinkList=====");

        return;

    }

    //头节点不动，需要一个辅助变量来遍历

    PersonNode temp = head.next;

    while (true) {

        //判断是否到链表最后

        if (temp == null) {

            break;

        }

        //输出节点信息

        System.out.println(temp);

        //由于之前重写了toString，这里直接打印temp就可以打印出节点的所有信息

        temp = temp.next;

    }

}

主函数

public static void main(String[] args) {

    PersonNode person1 = new PersonNode(1, "Jordan", 56);

    PersonNode person2 = new PersonNode(2, "Kobe", 81);

    PersonNode person3 = new PersonNode(3, "James", 61);

    PersonNode person4 = new PersonNode(4, "Melo", 60);

    LinkList list = new LinkList();

//按照顺序添加

    // System.out.println("====add====");

    // list.add(person1);

    // list.add(person2);

    // list.add(person3);

    // list.add(person4);

//不按照顺序添加

    System.out.println("====add by order====");

    list.addByOrder(person1);

    list.addByOrder(person4);

    list.addByOrder(person3);

    list.addByOrder(person2);

    list.list();

    // list.addByOrder(person2);

    System.out.println("====edit====");

    PersonNode newNode = new PersonNode(3, "Ivring", 57);

    list.edit(newNode);

    list.list();

//删除结点

    System.out.println("====delete====");

    list.delete(4);

    list.list();

}

完整代码

//SingleLinkList.java

public class SingleLinkList {

    public static void main(String[] args) {

        PersonNode person1 = new PersonNode(1, "Jordan", 56);

        PersonNode person2 = new PersonNode(2, "Kobe", 81);

        PersonNode person3 = new PersonNode(3, "James", 61);

        PersonNode person4 = new PersonNode(4, "Melo", 60);

        LinkList list = new LinkList();

    //按照顺序添加

        // System.out.println("====add====");

        // list.add(person1);

        // list.add(person2);

        // list.add(person3);

        // list.add(person4);

    //不按照顺序添加

        System.out.println("====add by order====");

        list.addByOrder(person1);

        list.addByOrder(person4);

        list.addByOrder(person3);

        list.addByOrder(person2);

        list.list();

        // list.addByOrder(person2);

        System.out.println("====edit====");

        PersonNode newNode = new PersonNode(3, "Ivring", 57);

        list.edit(newNode);

        list.list();

    //删除结点

        System.out.println("====delete====");

        list.delete(4);

        list.list();

    }

}

//定义一个成员点

class PersonNode {

    String name;

    public int no;

    public int score;

    public PersonNode next;//指向下一个结点

    public PersonNode(int no, String name, int score) {

        this.no = no;

        this.name = name;

        this.score = score;

    }

    //为了显示方便，重写toString

    @Override

    public String toString() {

        return "[no=" + no + ",name=" + name + ",score=" + score + "]";

    }

}

//定义LinkList管理person

class LinkList {

    //初始化头节点，头节点不能动

    private PersonNode head = new PersonNode(0, "", 0);

    public PersonNode getHead(){

        return head;//返回私有成员head

    }

    //当不考虑编号顺序时，找到当前链表最后节点，将最后节点next指向新节点

    public void add(PersonNode node) {

        //因为头节点不能动，先需要一个辅助遍历节点temp

        PersonNode temp = head;

        while (true) {//遍历链表，找到最后

            if (temp.next == null) {

                break;

            }

            temp = temp.next;//如果没到最后，就继续找下去

        }//当退出while循环时，temp指向链表的最后

        temp.next = node;

    }

    public void addByOrder(PersonNode node) {

        //因为头节点不移动，仍通过一个辅助变量来找添加的位置

        //因为是单链表，所以找的temp时位于添加位置的前一个结点，否则不能插入

        PersonNode temp = head;

        boolean flag = false;//标识添加的编号是否存在

        while (true) {

            if (temp.next == null) //说明temp在链表最后

                break;

            if (temp.next.no > node.no) {//位置找到了，就在temp后面

                break;

            } else if (temp.next.no == node.no) {//希望添加的编号已存在

                flag = true;

                break;

            }

            temp = temp.next;

        }

        if (flag) {//编号已存在，不能添加

            System.out.println("already exist no." + node.no + ", you can't add it.=====");

        } else {

            node.next = temp.next;

            temp.next = node;

        }

    }

    public void edit(PersonNode node) {

        if (head.next == null) {

            System.out.println("empty LinkList====");

            return;

        }

        PersonNode temp;

        temp = head.next;

        boolean flag = false;//判断是否找到该结点

        while (true) {

            if (temp == null)

                break;//到了链表最后

            if (temp.no == node.no) {

                flag = true;//找到

                break;

            }

            temp = temp.next;

        }

        //根据flag判断是否找到

        if (flag) {

            temp.name = node.name;

            temp.score = node.score;

        } else {

            System.out.println("not found no." + node.no + "====");

        }

        System.out.println("=======");

    }

    public void delete(int no) {

        if (head.next == null) {

            System.out.println("empty LinkList===");

            return;

        }

        PersonNode temp = head;//temp指向待删除结点的前一个结点

        boolean flag = false;

        while (true) {

            if (temp.next == null) {

                break;//已经到链表最后

            }

            if (temp.next.no == no) {

                flag = true;//找到了待删除结点的前一个结点temp

                break;

            }

            temp = temp.next;

        }

        if (flag) {

            temp.next = temp.next.next;

        } else {

            System.out.println("not found====");

        }

        System.out.println("====");

        //Java会自动回收未被访问的数据

    }

    //显示链表(遍历)

    public void list() {

        //判断链表是否为空

        if (head.next == null) {

            System.out.println("empty LinkList=====");

            return;

        }

        //头节点不动，需要一个辅助变量来遍历

        PersonNode temp = head.next;

        while (true) {

            //判断是否到链表最后

            if (temp == null) {

                break;

            }

            //输出节点信息

            System.out.println(temp);

            //由于之前重写了toString，这里直接打印temp就可以打印出节点的所有信息

            temp = temp.next;

        }

    }

}

面试题

求单链表中有效结点个数

//如果带头节点的链表，不统计头节点

public static int getLength(PersonNode head) {

    if (head.next == null)

        return 0;

    int length = 0;

    PersonNode current = head.next;//定义辅助变量

    while (current != null) {

        length++;

        current = current.next;

    }

    return length;

}

在主函数中测试

System.out.println(getLength(list.getHead()));

查找单链表中倒数第n个结点(新浪)

思路

编写一个方法，接收head结点，同时接收一个index
index表示是倒数第index个结点
先把链表从头到尾遍历，得到链表的总长度 getLength
得到size后，我们从链表第一个开始遍历(size-index)

public static PersonNode findLastIndexNode(PersonNode head, int index){

    if (head.next == null)

        return null;

    int size = getlength(head);//第一次遍历，获取链表大小

    if (index <= 0 || index > size)//判断倒数的序号是否超出容量

        return null;

    PersonNode current = head.next;

    for (int i = 0; i < size - index; i++) {

        current = current.next;//遍历size-index次

    }

    return current;

}

测试

PersonNode res = findLastIndexNode(list.getHead(), 1);

System.out.println(res);

单链表反转(腾讯)

思路

先定义一个结点reverseHead = new PersonNode();
从头到尾遍历原来的链表，每遍历一个链表，就将其取出，放在新链表最前端
原来链表的head.next = reverseHead.next;

public static void reverseList(PersonNode head) {

    if (head.next == null || head.next.next == null)

        return;

    // 定义一个辅助遍历，帮助遍历原来的链表

    PersonNode current = head.next;

    PersonNode next = null;//指向当前结点[current]的下一个结点

    PersonNode reverseHead = new PersonNode(0, "", 0);

    while (current != null) {

        next = current.next;//先暂时保存当前结点的下一个结点，后面会用到

        current.next = reverseHead.next;//把current的下一个结点指向新链表最前端

        reverseHead.next = current;//将current连接到新链表

        current = next;//让current后移

/*每一次循环，reverseHead.next都会按照原链表的顺序定位到current，遍历结束，刚到reverseHead.next定位到链表最后一个，

此时把reverseHead.next地址赋给head.next，这样就可以倒着来遍历链表*/

    }

    head.next = reverseHead.next;//头结点拼接，实现反转

}

测试

reverseList(list.getHead());

list.list();

从尾到头打印单链表(百度)

思路

1.先反转后再打印(有个问题：只要求逆序打印，不要求反转，这样会破坏原链表结构)
2.用栈的方法，利用栈先进后出的特点，实现逆序打印的效果

stack.java

下面是栈的实例

import java.util.Stack;

public class stack{

    public static void main(String[] args){

        Stack<String> stack = new Stack<>();

        stack.add("James");

        stack.add("Kboe");

        stack.add("Jordan");

        while(stack.size() > 0){

            System.out.println(stack.pop());

        }

    }

}

用栈的方法实现从头到尾打印单链表

public static void reversePrint(PersonNode head) {

    if (head.next == null)

        return;

    //创建一个栈，将各个结点压入栈

    Stack<PersonNode> stack = new Stack<PersonNode>();

    PersonNode current = head.next;

    while (current != null) {

        stack.push(current);

        current = current.next;

    }

    while (stack.size() > 0) {

        System.out.println(stack.pop());

    }

}

测试

reversePrint(list.getHead());

巴特西

单链表(Java--尚硅谷)

基础知识

创建结点

添加结点(乱序)

编辑结点

删除结点

打印链表

主函数

完整代码

面试题

求单链表中有效结点个数

查找单链表中倒数第n个结点(新浪)

单链表反转(腾讯)

从尾到头打印单链表(百度)

最新文章

热门文章