theme: condensed-night-purple

线性数据结构

节点是众多计算机科学中的基本构建单元数据结构，它们构成了链表、栈、队列、树等的基础。

单个节点包含数据以及与其他节点的链接。每种数据结构通过在这些特性上添加额外的约束或行为来创建所需的结构。

考虑图中所示的节点。此节点（ node_a ）包含一个数据片段（数字 5 ）以及指向另一个节点（ node_b ）的链接。

• 你认为节点为何如此普遍？
• 它们增加了哪些语言内置功能所不具备的特性？

节点详情

节点中包含的数据可以是多种类型，具体取决于您使用的语言。在前面的示例中，它是一个整数（数字 5 ），但它也可以是（ "five" ），小数（ 5.1 ），一个（ [5,3,4] ）或无（ null ）。节点内的链接有时被称为指针，因为它们“指向”另一个节点。通常，实现具有一个或多个链接的节点。如果这些链接是 null ，则表示您已到达之前跟随的特定节点或链接路径的末端。图表中展示了许多不同类型的节点实现。请检查数据的类型以及某些节点是如何链接的。

• node_c有什么不同之处？

节点连接

通常，由于数据结构的特性，节点可能仅能从一个其他节点进行链接。这使得在实现修改或从数据结构中移除节点时，必须慎重考虑。

如果你不慎移除了指向某个节点的唯一链接，该节点的数据及其所有链接的节点可能会对你的应用程序“失联”。当这种情况发生在一个节点上时，该节点被称为孤立节点。

观察下图中的节点。 node_c 仅由 node_b 链接。如果你想移除 node_b 但保留 node_c ，不能简单地删除从 node_a 到 node_b 的链接。

最直接的方法以保留 node_c 的方式是在 node_a 中更改链接，使其指向 node_c 而非 node_b 。然而，某些数据结构可能会采取不同的处理方式。

• 当我们改变 node_a 以引用 node_c 时，是否还需要“删除” node_b ？

节点：

• 包含数据，数据类型多样
• 包含指向其他节点的链接。如果一个节点没有链接，或者所有链接都为 null ，则表示您已到达所追踪路径的终点。
• 如果没有任何现有链接指向它们，则可能成为孤立节点

实践

让我们一起看看我们 Node 类的所有方法是如何运作的！

设想我们在一家冰淇淋店工作，这里售卖三种口味：草莓、香蕉和椰子。招牌水果圣代由这三种口味组成，但新员工很难记住顺序。

为了帮助他们记忆，我们的 Java 节点或许能派上用场。让我们开始吧…

1.在主方法中，实例化三个节点：

• 第一个将代表我们的草莓冰淇淋，名称为 "Berry Tasty" 。将其赋值给变量 strawberry 。
• 第二个将代表我们的香蕉冰淇淋，值为 "Banana-rama" 。将其赋值给变量 banana 。
• 第三个将代表我们的椰子冰淇淋，值为 "Nuts for Coconut" 。将其赋值给变量 coconut 。

2.现在让我们按顺序排列这些冰淇淋节点。

• strawberry 排在首位，然后 banana 紧随 strawberry 之后。
• 最后,coconut 排在 banana 之后。
• 在新创建的节点下方，使用你的 .setNextNode() 方法，使得：
• banana 是 strawberry 的 next 节点
• coconut 是 banana 的 next 节点

3.让我们遍历这些冰淇淋节点，确保它们按正确顺序链接。

• 创建一个新的 currentNode 变量，并将其设置为 strawberry 。
• 创建一个 while 循环，仅在 currentNode 不为 null 时迭代。在 while 循环内部，打印 currentNode 的 data ，然后将 currentNode 更新为其下一个节点。
• 我们应该在终端中按草莓、香蕉和椰子的顺序看到这些冰淇淋口味。

代码如下

public class Node {
   

    // 每个节点包含的冰淇淋名称数据
    public String data;

    // 指向下一个节点的引用，用于形成链表结构
    private Node next;

    // 构造方法，用于初始化节点的数据
    public Node(String data) {
   
        this.data = data; // 将传入的数据赋值给当前节点的 data
        this.next = null; // 初始化时没有下一个节点，将 next 设置为 null
    }

    // 设置当前节点的下一个节点
    public void setNextNode(Node node) {
   
        this.next = node; // 将当前节点的 next 指向传入的节点
    }

    // 获取当前节点的下一个节点
    public Node getNextNode() {
   
        return this.next; // 返回当前节点的下一个节点
    }

    // 主方法，程序的入口
    public static void main(String[] args) {
   

        // 1. 在主方法中实例化三个节点
        // 第一个节点代表草莓冰淇淋，名称为 "Berry Tasty"，并赋值给变量 strawberry
        Node strawberry = new Node("Berry Tasty");

        // 第二个节点代表香蕉冰淇淋，名称为 "Banana-rama"，并赋值给变量 banana
        Node banana = new Node("Banana-rama");

        // 第三个节点代表椰子冰淇淋，名称为 "Nuts for Coconut"，并赋值给变量 coconut
        Node coconut = new Node("Nuts for Coconut");

        // 2. 将冰淇淋节点按顺序排列
        // strawberry 排在首位，banana 紧随其后
        // 将 banana 设置为 strawberry 的 next 节点
        strawberry.setNextNode(banana);

        // 将 coconut 设置为 banana 的 next 节点
        banana.setNextNode(coconut);

        // 3. 遍历这些冰淇淋节点，确保它们按正确顺序链接
        // 创建一个新的 currentNode 变量，并将其设置为 strawberry
        Node currentNode = strawberry;

        // 创建一个 while 循环，循环条件是 currentNode 不为 null
        while (currentNode != null) {
   
            // 打印当前节点的 data（冰淇淋名称）
            System.out.println(currentNode.data);

            // 将 currentNode 更新为其下一个节点
            currentNode = currentNode.getNextNode();
        }
        // 循环结束时，将在终端中按顺序输出冰淇淋名称："Berry Tasty", "Banana-rama", "Nuts for Coconut"
    }
}

链表

既然你已经熟悉了节点，下一步就是实际利用它们来构建一些东西！通过节点的 next 属性将节点链接在一起，就形成了一个单向链表。单向链表极为灵活且实用，其简洁之美同样令人赞叹。与节点类似，这些链表是未来数据结构的基石，并且在以线性方式存储信息时，是数组的替代方案。

public class LinkedList {
   

  // 主方法，程序的入口
  public static void main(String []args) {
   
    // 此处可以编写测试代码来检查 LinkedList 的功能
  }

  // 链表的头部节点
  public Node head;

  // 构造方法，初始化链表，设置头节点为 null
  public LinkedList() {
   
    this.head = null;
  }

  // 将新的节点添加到链表的头部
  public void addToHead(String data) {
   
    // 创建一个新的节点，数据为传入的 data
    Node newHead = new Node(data);

    // 当前头部节点
    Node currentHead = this.head;

    // 将新节点设置为链表的头部
    this.head = newHead;

    // 如果当前链表不是空的，将原来的头节点链接到新节点之后
    if (currentHead != null) {
   
      this.head.setNextNode(currentHead);
    }
  }

  // 将新的节点添加到链表的尾部
  public void addToTail(String data) {
   
    // 定义一个尾部节点指向链表的头部
    Node tail = this.head;

    // 如果链表为空，直接将新的节点设为头部
    if (tail == null) {
   
      this.head = new Node(data);
    } else {
   
      // 如果链表不为空，遍历链表找到最后一个节点
      while (tail.getNextNode() != null) {
   
        tail = tail.getNextNode();
      }
      // 将新的节点添加到链表的尾部
      tail.setNextNode(new Node(data));
    }
  }  

  // 移除链表的头节点，并返回被移除节点的数据
  public String removeHead() {
   
    // 将当前头节点赋值给 removedHead
    Node removedHead = this.head;

    // 如果链表为空，返回 null
    if (removedHead == null) {
   
      return null;
    }

    // 将链表的头节点更新为原头节点的下一个节点
    this.head = removedHead.getNextNode();

    // 返回被移除节点的数据
    return removedHead.data;
  }

  // 打印链表中的所有节点数据
  public String printList() {
   
    // 定义输出字符串，并初始化为 <head> 以标记链表的开始
    String output = "<head> ";

    // 定义当前节点从头节点开始
    Node currentNode = this.head;

    // 遍历链表中的每个节点，依次将节点的数据添加到输出字符串中
    while (currentNode != null) {
   
      output += currentNode.data + " ";
      currentNode = currentNode.getNextNode(); // 移动到下一个节点
    }

    // 链表结束标记为 <tail>
    output += "<tail>";

    // 输出链表数据
    System.out.println(output);

    // 返回链表的字符串表示
    return output;
  }  

}

双向链表

虽然单向链表由节点组成，每个节点指向下一节点，但双向链表还包含指向其前一节点的链接。这些 previous 链接，连同增加的 tail 属性，使得你可以像在单向链表中向前遍历一样轻松地向后遍历。

从链表头部和尾部移除元素

由于额外的指针和尾部属性，从双向链表中移除头部比从单向链表中移除头部稍微复杂一些。然而，前驱指针和尾部属性使得移除链表尾部变得简单得多，因为我们不需要遍历整个链表就能做到这一点。

移除头部

移除头部涉及更新链表开头的指针。我们将把新头部（当前头部直接后面的元素）的前驱指针设置为 null ，并更新链表的头部属性。如果头部同时也是尾部，那么尾部移除过程也会发生。

移除尾部

同样地，移除尾部涉及更新链表末尾的指针。我们将把新尾部（尾部直接前面的元素）的下一个指针设置为 null ，并更新链表的尾部属性。如果尾部同时也是头部，那么头部移除过程也会发生。

public class DoublyLinkedList {
   

  // 主方法，程序入口
  public static void main(String[] args) {
   
    // 创建一个 DoublyLinkedList 对象
    DoublyLinkedList way = new DoublyLinkedList();

    // 将一个数据为 "hello" 的节点添加到链表头部
    way.addToHead("hello");

    // 打印链表内容
    way.printList();
  }

  // 链表的头部和尾部节点
  public Node head;
  public Node tail;

  // 构造方法，初始化双向链表，头尾节点设置为 null
  public DoublyLinkedList() {
   
    this.head = null;
    this.tail = null;
  }

  // 将一个新节点添加到链表的头部
  public void addToHead(String data) {
   
    // 创建一个新的头节点
    Node newHead = new Node(data);
    // 当前的头节点
    Node currentHead = this.head;

    // 如果链表不为空，将新节点链接到当前头节点的前面
    if (currentHead != null) {
   
      currentHead.setPreviousNode(newHead);  // 设置当前头节点的前一个节点为新节点
      newHead.setNextNode(currentHead);      // 设置新节点的下一个节点为当前头节点
    }
    this.head = newHead;  // 将新节点设置为链表的头节点

    // 如果链表为空，新节点也同时是尾节点
    if (this.tail == null) {
   
      this.tail = newHead;
    }
  }

  // 将一个新节点添加到链表的尾部
  public void addToTail(String data) {
   
    // 创建一个新的尾节点
    Node newTail = new Node(data);
    // 当前的尾节点
    Node currentTail = this.tail;

    // 如果链表不为空，将新节点链接到当前尾节点的后面
    if (currentTail != null) {
   
      currentTail.setNextNode(newTail);      // 设置当前尾节点的下一个节点为新节点
      newTail.setPreviousNode(currentTail);  // 设置新节点的前一个节点为当前尾节点
    }
    this.tail = newTail;  // 将新节点设置为链表的尾节点

    // 如果链表为空，新节点也同时是头节点
    if (this.head == null) {
   
      this.head = newTail;
    }
  }

  // 移除链表的头节点，并返回该节点的数据
  public String removeHead() {
   
    // 保存当前头节点
    Node removedHead = this.head;

    // 如果链表为空，返回 null
    if (removedHead == null) {
   
      return null;
    }

    // 将链表的头节点更新为当前头节点的下一个节点
    this.head = removedHead.getNextNode();

    // 如果新的头节点不为空，将它的前一个节点设置为 null
    if (this.head != null) {
   
      this.head.setPreviousNode(null);
    }

    // 如果移除的头节点也是尾节点，则更新尾节点
    if (removedHead == this.tail) {
   
      this.removeTail();
    }
    return removedHead.data;
  }

  // 移除链表的尾节点，并返回该节点的数据
  public String removeTail() {
   
    // 保存当前尾节点
    Node removedTail = this.tail;

    // 如果链表为空，返回 null
    if (removedTail == null) {
   
      return null;
    }

    // 将链表的尾节点更新为当前尾节点的前一个节点
    this.tail = removedTail.getPreviousNode();

    // 如果新的尾节点不为空，将它的下一个节点设置为 null
    if (this.tail != null) {
   
      this.tail.setNextNode(null);
    }

    // 如果移除的尾节点也是头节点，则更新头节点
    if (removedTail == this.head) {
   
      this.removeHead();
    }
    return removedTail.data;
  }

  // 根据数据内容移除链表中的一个节点
  public Node removeByData(String data) {
   
    // 要移除的节点初始化为空
    Node nodeToRemove = null;
    // 从头节点开始遍历链表
    Node currentNode = this.head;

    // 查找数据匹配的节点
    while (currentNode != null) {
   
      if (currentNode.data.equals(data)) {
   
        nodeToRemove = currentNode;
        break;
      }
      currentNode = currentNode.getNextNode();
    }

    // 如果未找到该节点，返回 null
    if (nodeToRemove == null) {
   
      return null;
    }

    // 根据节点的位置进行移除
    if (nodeToRemove == this.head) {
   
      this.removeHead();
    } else if (nodeToRemove == this.tail) {
   
      this.removeTail();
    } else {
   
      // 若节点在链表中间，将前后节点相连
      Node nextNode = nodeToRemove.getNextNode();
      Node previousNode = nodeToRemove.getPreviousNode();
      nextNode.setPreviousNode(previousNode);
      previousNode.setNextNode(nextNode);
    }
    return nodeToRemove;
  }

  // 打印链表中的所有节点数据
  public String printList() {
   
    // 从头节点开始遍历
    Node currentNode = this.head;
    String output = "<head> ";

    // 遍历每个节点，将节点数据加入到输出字符串中
    while (currentNode != null) {
   
      output += currentNode.data + " ";
      currentNode = currentNode.getNextNode();
    }
    output += "<tail>";  // 链表结束标记为 <tail>

    // 输出链表内容
    System.out.println(output);
    return output;
  }

}

队列

队列是一种线性数据结构，它按照先入先出的原则（FIFO）来管理元素。新的元素只能添加在队尾（入队），而移除操作只能在队首进行（出队）。我们可以用多种底层数据结构来实现队列，其中一种常见且高效的实现方式是使用单链表。

队列的结构类似于现实生活中的排队场景，比如在超市收银台前的队伍。排在最前面的人会最先离开队伍，而每个新加入的人只能排在队尾。这种设计保证了元素的顺序性，使得队列在处理按顺序访问数据的场景中非常实用。

队列：

• 包含数据节点
• 支持三种主要操作：
• 入队将数据添加到队列尾部
• 出队移除并提供队列前端的数据
• 查看提供队列前端的数据
• 可以使用链表或数组实现
• 有界队列具有有限的尺寸。
• 将元素加入已满的队列会导致队列溢出
• 队列按先进先出（FIFO）的方式处理数据

public class RestaurantOrders {
   

    // 定义三个队列对象：分别用于主厨（headChef）、副厨（sousChef）、和等待列表（waitingList）
    public Queue headChef;
    public Queue sousChef;
    public Queue waitingList;

    // 构造函数：用于初始化每个厨师的队列和等待列表的队列
    public RestaurantOrders() {
   
        // 初始化主厨队列，最大容量为3
        this.headChef = new Queue(3);
        // 初始化副厨队列，最大容量为3
        this.sousChef = new Queue(3);
        // 初始化等待列表队列，未指定容量，因此假设容量不限
        this.waitingList = new Queue();
    }

    /**
     * 将一组订单分配给主厨、副厨，或等待列表
     * @param orders 包含订单名称的字符串数组
     */
    public void assign(String[] orders) {
   
        // 遍历传入的订单数组，每个订单逐个进行分配
        for (String order : orders) {
   
            try {
   
                // 首先尝试将订单加入主厨队列
                this.headChef.enqueue(order);
                // 如果成功，则输出订单已被主厨接收
                System.out.println("Order for " + order + " taken by Head Chef.");

            } catch (Error e) {
    // 如果主厨队列已满，触发异常
                // 检查副厨队列是否有空位
                if (this.sousChef.hasSpace()) {
   
                    // 如果副厨队列有空间，则将订单分配给副厨
                    this.sousChef.enqueue(order);
                    System.out.println("Head Chef is busy! Assign " + order + " order to Sous Chef.");
                } else {
   
                    // 如果副厨队列也已满，将订单放入等待列表
                    this.waitingList.enqueue(order);
                    System.out.println("Both chefs are busy! Add " + order + " order to the waiting list.");
                }
            }
        }

        // 输出当前等待列表中的订单数量，以便工作人员掌握当前积压情况
        System.out.println("-----------------");
        System.out.println("You've got " + this.waitingList.size() + " orders on the waiting list. Keep up the hard work, chefs!");
    }

    /**
     * 主方法：测试 RestaurantOrders 类的功能
     */
    public static void main(String[] args) {
   
        // 创建一个 RestaurantOrders 对象
        RestaurantOrders orders = new RestaurantOrders();
        // 创建一个字符串数组，包含若干订单名称
        String[] newOrders = {
   "Pizza", "Pasta", "Salad", "Burger", "Sushi"};
        // 调用 assign 方法，将订单分配给厨师或等待列表
        orders.assign(newOrders);
    }
}

栈

栈是另一种数据结构，其名称非常形象。与队列类似，栈是一个线性节点集合，它将数据添加（压入）到栈顶。然而，与队列不同的是，栈从栈顶移除数据（弹出）。可以将其想象成一堆书，你只能拿起最上面的书，并将新书放在最上面。

堆栈（Stack）可以使用链表作为底层数据结构来实现，因为相比于列表或数组，这样的实现方式更加高效。

根据具体实现，堆栈的顶部相当于链表的头节点，而堆栈的底部则相当于链表的尾节点。

对堆栈可能会设置的一个限制是其大小。这样做的目的是限制和量化数据结构在“满”时占用的资源。

尝试向一个已满的堆栈中压入数据将导致堆栈溢出（stack overflow）。同样地，如果试图从一个空堆栈中弹出数据，则会导致堆栈下溢（stack underflow）。

栈（Stacks）：

• 包含数据节点
• 支持三种主要操作
  • 压入（Push）将数据添加到栈顶
  • 弹出（Pop）移除并提供栈顶数据
  • 查看（Peek）显示栈顶数据
• 实现方式包括链表或数组
• 可以有固定大小
• 向已满的栈压入数据会导致栈溢出（stack overflow）
• 栈处理数据遵循后进先出（Last In, First Out，LIFO）原则

public class PizzaDelivery {
   

    // 声明两个堆栈，分别表示送餐员和披萨店的堆栈
    public Stack deliveryGal; // 用于存储送餐员要送的披萨
    public Stack pizzaHouse;  // 用于存储多余的、等待配送的披萨

    public PizzaDelivery() {
   
        // 1. 实例化 deliveryGal 和 pizzaHouse 堆栈
        this.deliveryGal = new Stack(5); // 设置送餐员的堆栈容量为5
        this.pizzaHouse = new Stack();   // 披萨店的堆栈没有容量限制
    }

    public void assign(String[] pizzas) {
   
        // 遍历所有披萨，将它们分配到合适的堆栈中
        for (String pizza : pizzas) {
   
            try {
   
                // 检查 deliveryGal 堆栈是否还有空间
                if (this.deliveryGal.hasSpace()) {
   
                    // 如果有空间，将披萨压入 deliveryGal 堆栈
                    this.deliveryGal.push(pizza);
                    System.out.println(pizza + " pizza added to deliveryGal stack.");
                } else {
   
                    // 如果没有空间，抛出堆栈已满的异常
                    throw new Error("Stack is full!");
                }
            } catch (Error e) {
   
                // 3. 捕获异常，将披萨压入 pizzaHouse 堆栈，并打印信息
                this.pizzaHouse.push(pizza);
                System.out.println("deliveryGal left to make deliveries! " + pizza + " pizza added to pizzaHouse stack.");
            }
        }

        // 输出配送状态更新信息
        System.out.println("\nDELIVERIES ARE UNDERWAY...\n");
    }

    public void deliver() {
   
        // 获取 deliveryGal 堆栈中披萨的数量
        int numPizzas = this.deliveryGal.size;
        // 依次将 deliveryGal 堆栈中的披萨弹出并送达
        for (int i = 0; i < numPizzas; i++) {
   
            // 4. 从 deliveryGal 中弹出每个披萨，并打印送达信息
            String pizzaType = this.deliveryGal.pop();
            System.out.println(pizzaType + " pizza delivered!");
        }
    }

    public static void main(String[] args) {
   
        // 定义一个披萨列表
        String[] pizzas = {
   "pepperoni", "cheese", "veggie", "meat", "hawaiian", "margherita"};
        // 实例化 PizzaDelivery 对象
        PizzaDelivery pizzaDelivery = new PizzaDelivery();
        // 将披萨分配到合适的堆栈中
        pizzaDelivery.assign(pizzas);
        // 开始配送披萨
        pizzaDelivery.deliver();
    }
}