单向链表的介绍和实现思路

链表的介绍

链表在内存中的存储

特点

• 链表是以节点的方式来存储,是链式存储
• 每个节点包含 data 域 和 next 域。next域用来指向下一个节点
• 链表的各个节点不一定是连续存储的
• 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

带头结点的逻辑示意图

实现思路

创建（添加）

• 先创建一个Head头节点，表示单链表的头
• 后面我们每添加一个节点，就放在链表的最后

遍历

• 通过一个辅助变量，来遍历整个链表

有序插入

• 先遍历链表，找到应该插入的位置
• 要插入的节点的next指向插入位置的后一个节点
• 插入位置的前一个节点的next指向要插入节点
  • 插入前要判断是否在队尾插入

根据某个属性节点修改值

• 先遍历节点，找到修改的位置
  • 如果未找到修改节点，则不修改

删除某个节点

• 先遍历节点，找到要删除节点的前一个节点
• 进行删除操作

求倒数第n个节点的信息

• 遍历链表，求出链表的有效长度length（不算头结点）
• 遍历链表到第length-n的节点

翻转链表

• 创建一个新的头结点，作为新链表的头
• 从头遍历旧链表，将遍历到的节点插入新链表的头结点之后
• 注意需要用到两个暂存节点
  • 一个用来保存正在遍历的节点
  • 一个用来保存正在遍历节点的下一个节点

逆序打印

• 遍历链表，将遍历到的节点入栈
• 遍历完后，进行出栈操作，同时打印出栈元素

代码

public class Demo1 {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.traverseNode();
        System.out.println();
        //创建学生节点，并插入链表
        StudentNode student1 = new StudentNode(1, "Nyima");
        StudentNode student3 = new StudentNode(3, "Lulu");
        linkedList.addNode(student1);
        linkedList.addNode(student3);
        linkedList.traverseNode();
        System.out.println();
 
        //按id大小插入
        System.out.println("有序插入");
        StudentNode student2 = new StudentNode(0, "Wenwen");
        linkedList.addByOrder(student2);
        linkedList.traverseNode();
        System.out.println();
 
        //按id修改学生信息
        System.out.println("修改学生信息");
        student2 = new StudentNode(1, "Hulu");
        linkedList.changeNode(student2);
        linkedList.traverseNode();
        System.out.println();
 
        //根据id删除学生信息
        System.out.println("删除学生信息");
        student2 = new StudentNode(1, "Hulu");
        linkedList.deleteNode(student2);
        linkedList.traverseNode();
        System.out.println();
 
        //获得倒数第几个节点
        System.out.println("获得倒数节点");
        System.out.println(linkedList.getStuByRec(2));
        System.out.println();
 
        //翻转链表
        System.out.println("翻转链表");
        LinkedList newLinkedList = linkedList.reverseList();
        newLinkedList.traverseNode();
        System.out.println();
 
        //倒叙遍历链表
        System.out.println("倒序遍历链表");
        newLinkedList.reverseTraverse();
 
    }
}
 
/**
 * 创建链表
 */
class LinkedList {
    //头节点，防止被修改，设置为私有的
    private StudentNode head = new StudentNode(0, "");
 
    /**
     * 添加节点
     * @param node 要添加的节点
     */
    public void addNode(StudentNode node) {
        //因为头节点不能被修改，所以创建一个辅助节点
        StudentNode temp = head;
        //找到最后一个节点
        while (true) {
            //temp是尾节点就停止循环
            if(temp.next == null) {
                break;
            }
            //不是尾结点就向后移动
            temp = temp.next;
        }
        //现在temp是尾节点了，再次插入
        temp.next = node;
    }
 
    /**
     * 遍历链表
     */
    public void traverseNode() {
        System.out.println("开始遍历链表");
        if(head.next == null) {
            System.out.println("链表为空");
        }
        //创建辅助节点
        StudentNode temp = head.next;
        while(true) {
            //遍历完成就停止循环
            if(temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
 
    /**
     * 按id顺序插入节点
     * @param node
     */
    public void addByOrder(StudentNode node) {
        //如果没有首节点，就直接插入
        if(head.next == null) {
            head.next = node;
            return;
        }
        //辅助节点，用于找到插入位置和插入操作
        StudentNode temp = head;
        //节点的下一个节点存在，且它的id小于要插入节点的id，就继续下移
        while (temp.next!=null && temp.next.id < node.id) {
            temp = temp.next;
        }
        //如果temp的下一个节点存在，则执行该操作
        //且插入操作，顺序不能换
        if(temp.next != null) {
            node.next = temp.next;
        }
        temp.next = node;
    }
 
    /**
     * 根据id来修改节点信息
     * @param node 修改信息的节点
     */
    public void changeNode(StudentNode node) {
        if(head == null) {
            System.out.println("链表为空，请先加入该学生信息");
            return;
        }
        StudentNode temp = head;
        //遍历链表，找到要修改的节点
        while (temp.next!= null && temp.id != node.id) {
            temp = temp.next;
        }
        //如果temp已经是最后一个节点，判断id是否相等
        if(temp.id != node.id) {
            System.out.println("未找到该学生的信息，请先创建该学生的信息");
            return;
        }
        //修改学生信息
        temp.name = node.name;
    }
 
    /**
     * 根据id删除节点
     * @param node 要删除的节点
     */
    public void deleteNode(StudentNode node) {
        if(head.next == null) {
            System.out.println("链表为空");
            return;
        }
        StudentNode temp = head.next;
        //遍历链表，找到要删除的节点
        if(temp.next!=null && temp.next.id!=node.id) {
            temp = temp.next;
        }
        //判断最后一个节点的是否要删除的节点
        if(temp.next.id != node.id) {
            System.out.println("请先插入该学生信息");
            return;
        }
        //删除该节点
        temp.next = temp.next.next;
    }
 
    /**
     * 得到倒数的节点
     * @param index 倒数第几个数
     * @return
     */
    public StudentNode getStuByRec(int index) {
        if(head.next == null) {
            System.out.println("链表为空!");
        }
        StudentNode temp = head.next;
        //用户记录链表长度，因为head.next不为空，此时已经有一个节点了
        //所以length初始化为1
        int length = 1;
        while(temp.next != null) {
            temp = temp.next;
            length++;
        }
        if(length < index) {
            throw new RuntimeException("链表越界");
        }
 
        temp = head.next;
        for(int i = 0; i<length-index; i++) {
            temp = temp.next;
        }
        return temp;
    }
 
    /**
     * 翻转链表
     * @return 反转后的链表
     */
    public LinkedList reverseList() {
        //链表为空或者只有一个节点，无需翻转
        if(head.next == null || head.next.next == null) {
            System.out.println("无需翻转");
        }
        LinkedList newLinkedList = new LinkedList();
        //给新链表创建新的头结点
        newLinkedList.head = new StudentNode(0, "");
        //用于保存正在遍历的节点
        StudentNode temp = head.next;
        //用于保存正在遍历节点的下一个节点
        StudentNode nextNode = temp.next;
        while(true) {
            //插入新链表
            temp.next = newLinkedList.head.next;
            newLinkedList.head.next = temp;
            //移动到下一个节点
            temp = nextNode;
            nextNode = nextNode.next;
            if(temp.next == null) {
                //插入最后一个节点
                temp.next = newLinkedList.head.next;
                newLinkedList.head.next = temp;
                head.next = null;
                return newLinkedList;
            }
        }
    }
 
    public void reverseTraverse() {
        if(head == null) {
            System.out.println("链表为空");
        }
 
        StudentNode temp = head.next;
        //创建栈，用于存放遍历到的节点
        Stack<StudentNode> stack = new Stack<>();
        while(temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
 
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}
 
/**
 * 定义节点
 */
class StudentNode {
    int id;
    String name;
    //用于保存下一个节点的地址
    StudentNode next;
 
    public StudentNode(int id, String name) {
        this.id = id;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "StudentNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}