数据结构：单链表

  • 开发
  • 20

1、单链表

一个节点指向另一个节点

2、实现

2.1、Node类

public class Node {

    private String data;

    private Node nextNode;

    public Node(){}

    public Node(String data){
        this.data=data;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public Node getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node nextNode) {
        this.nextNode = nextNode;
    }
}

2.2、单链表

import java.util.LinkedList;

public class LinkedListTest {

    private  Node headNode;

    public LinkedListTest(){
        this.headNode=new Node();
    }

    public LinkedListTest(Node node){
        this.headNode=node;
    }

    public Node getHeadNode() {
        return headNode;
    }

    public void setHeadNode(Node headNode) {
        this.headNode = headNode;
    }

    public  boolean insertIntoHead(Node node){

        if (node==null){
            System.out.print("插入的节点为null！");
            return false;
        }

        System.out.println("开始头部新增节点---");
        if (this.headNode.getNextNode()==null){
            this.headNode.setNextNode(node);
            return true;
        }else {
            node.setNextNode(this.headNode.getNextNode());

            this.headNode.setNextNode(node);

            return true;
        }
    }

    public  boolean insertIntoTail(Node node){

        if (node==null){
            System.out.print("插入的节点为null！");
            return false;
        }

        System.out.println("开始尾部新增节点---");
        if (this.headNode.getNextNode()==null){
            this.headNode.setNextNode(node);
            return true;
        }else {
            Node currentNode=this.getHeadNode().getNextNode();
            Node lastNode = currentNode;
            while (currentNode.getNextNode()!=null){
                currentNode=currentNode.getNextNode();
                lastNode=currentNode;
            }

            lastNode.setNextNode(node);
            return true;
        }
    }

    public  int traverseLinkedList(){
        int count=0;
        if (this.getHeadNode().getNextNode()==null){
            System.out.println("遍历的链表为空！");
        }

        System.out.println("开始正向遍历链表---");
        Node currentNode=this.getHeadNode().getNextNode();
        while (currentNode!=null){
            System.out.println("遍历的节点是：【"+currentNode.getData()+"】");
            currentNode=currentNode.getNextNode();
            ++count;
        }

        System.out.println("结束正向遍历链表---");
        return count;
    }

    public  int traverseLinkedList2(){
        int count=0;
        if (this.getHeadNode().getNextNode()==null){
            System.out.println("遍历的链表为空！");
        }

        System.out.println("开始反向遍历链表---");
        Node currentNode=this.getHeadNode().getNextNode();

        final LinkedList<Node> nodesList = new LinkedList<>();
        while (currentNode!=null){
            nodesList.addFirst(currentNode);
            currentNode=currentNode.getNextNode();
        }

        for (Node node : nodesList) {
            System.out.println("遍历的节点是：【" + node.getData() + "】");
            ++count;
        }

        System.out.println("结束反向遍历链表---");
        return count;
    }


    public void insertIntoAppoint(Node appoint,Node node){
        if (node==null){
            System.out.println("新增的节点不能为空！");
            return;
        }

        if (appoint==null){
            System.out.println("指定新增节点不能为空！");
            return;
        }

        Node currentNode=this.getHeadNode();
        if (currentNode.getNextNode()==null){
            System.out.println("链表为空！");
            return;
        }

        int count=0;
        //找到第一个和指定节点相同的值，在其后面新增
        while (currentNode!=null && !appoint.getData().equals(currentNode.getData())){
            currentNode=currentNode.getNextNode();
            if (currentNode!=null){
                ++count;
            }

        }

        if (count==this.getSize()){
            System.out.println("不存在和指定值一样的节点！");
            return;
        }

        if (currentNode.getNextNode()==null){
            currentNode.setNextNode(node);
            return;
        }

        node.setNextNode(currentNode.getNextNode());

        currentNode.setNextNode(node);

    }

    private int getSize() {
        return this.traverseLinkedList();
    }
}

2.3、测试类

实现头部新增和尾部新增，以及正向遍历和反向遍历

public static void main(String[] args) {

        LinkedListTest linkedListTest=new LinkedListTest();

        int count=0;
        for (int i = 0; i < NUMBER; i++) {
            boolean insertStatus= linkedListTest.insertIntoHead(new Node(String.valueOf(i)));

            if (insertStatus){
                ++count;
            }
        }

        for (int i = 0; i < NUMBER; i++) {
            boolean insertStatus= linkedListTest.insertIntoTail(new Node(String.valueOf(i)));

            if (insertStatus){
                ++count;
            }
        }

        if (count==NUMBER){
            System.out.println("全部新增成功！");
        }

        linkedListTest.traverseLinkedList();
        System.out.println("反向遍历");
        linkedListTest.traverseLinkedList2();
}

3、线程问题

由于上面没有对链表的属性进行控制，所以是线程不安全的。在多线程的情况下，会出现很多问题。所以为了解决这个问题，我们在单链表的所有方法上加上关键字synchronized。这样就能保证线程安全，代码如下

3.1、实现

import java.util.LinkedList;

public class ThreadSafeLinkedList {

    private final Node headNode;

    public ThreadSafeLinkedList() {
        this.headNode = new Node();
    }

    public synchronized boolean insertIntoHead(Node node) {
        if (node == null) {
            System.out.printf("插入的节点为null！");
            return false;
        }

        System.out.println("开始头部新增节点---");
        if (this.headNode.getNextNode() == null) {
            this.headNode.setNextNode(node);
            return true;
        } else {
            node.setNextNode(this.headNode.getNextNode());
            this.headNode.setNextNode(node);
            return true;
        }
    }

    public synchronized boolean insertIntoTail(Node node) {
        if (node == null) {
            System.out.printf("插入的节点为null！");
            return false;
        }

        System.out.println("开始尾部新增节点---");
        if (this.headNode.getNextNode() == null) {
            this.headNode.setNextNode(node);
            return true;
        } else {
            Node currentNode = this.headNode.getNextNode();
            Node lastNode = currentNode;
            while (currentNode.getNextNode() != null) {
                currentNode = currentNode.getNextNode();
                lastNode = currentNode;
            }
            lastNode.setNextNode(node);
            return true;
        }
    }

    public synchronized void traverseLinkedList() {
        if (this.headNode.getNextNode() == null) {
            System.out.println("遍历的链表为空！");
            return;
        }

        System.out.println("开始正向遍历链表---");
        Node currentNode = this.headNode.getNextNode();
        while (currentNode != null) {
            System.out.println("遍历的节点是：【" + currentNode.getData() + "】");
            currentNode = currentNode.getNextNode();
        }
        System.out.println("结束正向遍历链表---");
    }

    public synchronized void traverseLinkedList2() {
        if (this.headNode.getNextNode() == null) {
            System.out.println("遍历的链表为空！");
            return;
        }

        System.out.println("开始反向遍历链表---");
        Node currentNode = this.headNode.getNextNode();
        final LinkedList<Node> nodesList = new LinkedList<>();
        while (currentNode != null) {
            nodesList.addFirst(currentNode);
            currentNode = currentNode.getNextNode();
        }
        for (Node node : nodesList) {
            System.out.println("遍历的节点是：【" + node.getData() + "】");
        }
        System.out.println("结束反向遍历链表---");
    }
}

3.2、测试

  • 测试线程不安全的
final LinkedListTest linkedListTest = new LinkedListTest();

final ExecutorService executorService1 = Executors.newFixedThreadPool(2);

executorService1.execute(()->{
    System.out.println("线程1-执行头插入");
    final Node node = new Node("1");
    final boolean b = linkedListTest.insertIntoHead(node);
    System.out.println("线程1-开始遍历");
    linkedListTest.traverseLinkedList();
    System.out.println("线程1-结束遍历");
});

executorService1.execute(()->{
    System.out.println("线程2-执行尾插入");
    final Node node = new Node("2");

    final boolean b = linkedListTest.insertIntoTail(node);
    System.out.println("线程2-开始遍历");
    linkedListTest.traverseLinkedList();
    System.out.println("线程2-结束遍历");
});

结果显示，在两个线程新增节点之后，遍历的时候，显示的结果，有时显示4个，2个。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  • 测试线程安全的
final ThreadSafeLinkedList threadSafeLinkedList = new ThreadSafeLinkedList();

final ExecutorService executorService2 = Executors.newFixedThreadPool(2);

executorService2.execute(()->{
    System.out.println("线程1-执行头插入");
    final Node node = new Node("1");
    final boolean b = threadSafeLinkedList.insertIntoHead(node);
    System.out.println("线程1-开始遍历");
    threadSafeLinkedList.traverseLinkedList();
    System.out.println("线程1-结束遍历");
});

executorService2.execute(()->{
    System.out.println("线程2-执行尾插入");
    final Node node = new Node("2");

    final boolean b = threadSafeLinkedList.insertIntoTail(node);
    System.out.println("线程2-开始遍历");
    threadSafeLinkedList.traverseLinkedList();
    System.out.println("线程2-结束遍历");
});

结果，多次测试显示的结果都是预期的，且一致
在这里插入图片描述

4、ArrayList

ArrayList也是线程不安全的，那为什么我们项目中还使用很多？
在项目中基本使用 ArrayList 而不是线程安全的集合类（如 Vector 或 CopyOnWriteArrayList）的原因主要有以下几点：

  1. 性能考虑：线程安全的集合类通常会增加额外的同步机制来保证线程安全，这可能会对性能造成一定的影响。而 ArrayList 是非线程安全的，但在单线程环境下性能更高，因此在不需要考虑线程安全的情况下可以选择使用它来获得更好的性能。

  2. 并发需求：在很多项目中，并不是所有的数据结构都需要线程安全。如果应用场景中并发要求不高，或者可以通过其他方式保证数据的一致性，那么使用非线程安全的集合类可能更加合适。

  3. 开发成本：使用线程安全的集合类会增加代码的复杂度和维护成本。在一些小型项目或者高并发场景并不重要的项目中，可能会选择使用非线程安全的集合类来简化开发。

尽管 ArrayList 是线程不安全的，但在很多简单的应用场景中，可以通过正确的使用方式来保证数据的一致性。在需要考虑线程安全的情况下，可以考虑使用 Collections.synchronizedList(new ArrayList<>()) 或者 CopyOnWriteArrayList 等线程安全的替代方案。在实际开发中，根据具体的需求和场景选择最适合的集合类是很重要的。

5、为什么单链表要有头节点？

单链表中的头节点是一个虚拟节点，不存储实际的数据，主要作用是方便对链表的操作和处理。以下是几个使用头节点的好处：

  1. 简化操作：有了头节点，链表的操作会更加统一和简化。无论是插入、删除还是遍历操作，都可以通过头节点统一处理，无需特殊处理头节点为空的情况。

  2. 避免特殊情况处理：如果链表没有头节点，那么需要额外处理链表为空、头节点为空等特殊情况。有了头节点，可以统一处理，避免特殊情况的出现，使代码更加简洁。

  3. 方便插入和删除：有了头节点，可以在链表头部插入或删除节点时，无需额外处理边界情况，操作更加方便。

  4. 使链表操作一致：有了头节点，链表的操作变得更加统一，比如遍历链表时从头节点开始，插入节点时可以保持操作的一致性。

  5. 提高代码可读性：头节点可以使操作链表的代码更具可读性，因为可以清晰地了解链表的结构和操作方式。

总的来说，使用头节点可以简化链表操作，避免特殊情况的处理，统一链表操作的方式，并提高代码的可读性，因此在设计单链表时常常会使用头节点。

阅读全部

相关推荐

  6. 数据结构:单链表

    2024-06-15 10:08:01       49 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-06-15 10:08:01       98 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-06-15 10:08:01       106 阅读

  9. 在Django里面运行非项目文件

    2024-06-15 10:08:01       87 阅读

  19. Python语言-面向对象

    2024-06-15 10:08:01       96 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-06-15 10:08:01       91 阅读

热门阅读

  18. pytorch 源代码目录作用归纳备忘

    2024-06-15 10:08:01       35 阅读

  19. 升级Oracle SQLcl

    2024-06-15 10:08:01       28 阅读

  21. iOS接入Flutter

    2024-06-15 10:08:01       30 阅读

  26. Windows OpenVPN的安装之服务器自动启动连接

    2024-06-15 10:08:01       35 阅读

  30. 泛微E9 流程附件发送第三方系统

    2024-06-15 10:08:01       28 阅读