数据结构与算法（三）：单向链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法（三）：单向链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链表定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑是通过链表种的指针链接次序实现的。链表由一系列节点组成，每个节点包括两部分：一个是存储数据元素的数据域，一个是存储下一个节点地址的指针域。单向链表从头节点（也可以没有头节点）开始，指针指向下一个节点的位置，只能由上一个节点指向后面节点，后面节点不能指向前面节点。单向链表示意图：
数据结构与算法（三）：单向链表

节点结构

节点包含了数据域和指针域。数据域存放该节点存放的数据信息，指针域存放下一个节点的存储地址。no、nickName、name为该节点的数据内容，nextNode为下一个节点。

public class Node {
    private Integer no;
    private String name;
    private String nickName;
    private Node nextNode;
    public Node(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }
    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

链表操作

初始化单向链表

初始化链表的头节点，头节点数据域为空，指针域为下一个节点的位置。

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

遍历链表

因为单向链表的头节点不能移动，所以借助一个临时节点变量进行遍历。

public void showLinkList() {
    if (head.getNextNode() == null) {
        System.out.println("链表为空");
        return;
    }
    Node temp = head.getNextNode();
    while (true) {
        if (temp == null) {
            break;
        }
        System.out.println(temp);
        temp = temp.getNextNode();
    }
}

插入元素

该方法只是将新的节点放到节点的末尾去，并不考虑顺序等因素。

public void addNode(Node node) {
   // 因为head是不能动的，所以需要借助一个临时变量
   Node temp = head;
   while (true) {
       if (temp.getNextNode() == null) {
           break;
       }
       temp = temp.getNextNode();
   }
   temp.setNextNode(node);
}

该方法将新的节点放到节点中去，考虑节点的顺序（以节点的 no 属性为顺序）。

public void addSortNode(Node node) {
    Node temp = head;
    boolean isExist = false;
    while (true) {
        if (temp.getNextNode() == null) {
            break;
        }
        // 对应的序号已经存在
        if (temp.getNo().equals(node.getNo())) {
            isExist = true;
            break;
        }
        if (temp.getNextNode().getNo() > node.getNo()) {
            break;
        }
        temp = temp.getNextNode();
    }
    if (isExist) {
        System.out.println("插入的序号 " + node.getNo() + " 已存在");
    } else {
        node.setNextNode(temp.getNextNode());
        temp.setNextNode(node);
    }
}

更新节点

更新某一个节点的数据域内容

public void updateNode(Node node) {
    if (head.getName().equals("")) {
        System.out.println("链表为空");
    }
    Node temp = head.getNextNode();
    while (true) {
        if (temp == null) {
            break;
        }
        if (temp.getNo() == node.getNo()) {
            break;
        }
        temp = temp.getNextNode();
    }
    if (temp == null || temp.getNo() != node.getNo()) {
        System.out.println("没有找到对应的节点");
    } else {
        temp.setName(node.getName());
        temp.setNickName(node.getNickName());
    }
}

删除节点

找到要删除节点的上一个节点，将该节点的指针域设置成要删除节点的下一个节点，这样要删除的节点就没有指针指向了，就会被GC回收，达到删除节点的目的。

public void deleteNode(Integer no) {
    if (head.getNextNode() == null) {
        System.out.println("链表为空");
    }
    Node temp = head;
    while (true) {
        if (temp.getNextNode() == null) {
            break;
        }
        if (temp.getNextNode().getNo() == no) {
            break;
        }
        temp = temp.getNextNode();
    }
    if (temp.getNextNode() == null) {
        System.out.println("未找到节点");
        return;
    }
    temp.setNextNode(temp.getNextNode().getNextNode());
}

有效节点的个数

public Integer getListNodeConunt() {
    if (head.getNextNode() == null) {
        return 0;
    }
    Node temp = head.getNextNode();
    Integer count = 0;
    while (true) {
        if (temp == null) {
            break;
        }
        count++;
        temp = temp.getNextNode();
    }
    return count;
}

倒数{}个节点

因为单向链表的后一个节点是无法获取到前一个节点的位置的，所以我们先计算出该链表的有效节点个数，再用有效节点个数 - 倒数的节点个数就是正数的节点个数，这样可以达到同样的效果。

public Node getLastNode(SingleLinkList list, Integer index) {
    Integer count = list.getListNodeConunt();
    if (Optional.of(list).isEmpty()) {
        return null;
    }
    // 第几个元素
    Integer indexPosition = 0;
    Node temp = head.getNextNode();
    while (true) {
        if (temp == null) {
            break;
        }
        // 因为链表是单向的，只能从前往后找，倒数第几个=总数-倒数的数
        if (indexPosition == (count - index)) {
            return temp;
        }
        indexPosition++;
        temp = temp.getNextNode();
    }
    return null;
}

链表反转

遍历旧链表，第一个节点放入新链表的第一个节点，第二个节点的下一个节点设置成新链表的第一个节点，以此类推，旧链表的第一个就成了新链表的最后一个节点，第二个节点就成了新链表的倒数第二个节点...

public void getReverseList(Node head) {
    // 如果当前链表为空，或者只有一个节点，无需反转，直接返回
    if (head.getNextNode() == null || head.getNextNode().getNextNode() == null) {
        return;
    }
    // 定义一个辅助变量，帮助遍历原来的链表
    Node cur = head.getNextNode();
    // 指向当前节点cur的下一个节点
    Node next = null;
    Node reverseHead = new Node(0, "", "");
    // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
    while (cur != null) {
        // 先暂时保存当前节点的下一个节点，因为后面需要使用
        next = cur.getNextNode();
        // 将cur的下一个节点指向新的链表的最前端
        cur.setNextNode(reverseHead.getNextNode());
        reverseHead.setNextNode(cur);
        // 让cur后移
        cur = next;
    }
    // 将head.next 指向reverseHead.next，实现单链表的反转
    head.setNextNode(reverseHead.getNextNode());
}

逆序打印

利用栈结构先进后出的特点，将遍历的链表节点依次入栈，再打印栈中的节点，这样可以在不改变原来链表数据的情况下进行逆序打印输出。文章来源地址https://www.toymoban.com/news/detail-618693.html

public void reversePrint(Node head) {
    if (head.getNextNode() == null) {
        return;
    }
    // 创建一个栈，将各个节点压入栈
    Stack<Node> stack = new Stack<>();
    Node cur = head.getNextNode();
    while (cur != null) {
        stack.push(cur);
        cur = cur.getNextNode();
    }
    while (stack.size() > 0) {
        System.out.println(stack.pop());
    }
}

到了这里，关于数据结构与算法（三）：单向链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！