Like first, then look, make a habit!

Linked list as a common data structure, we still need to understand, if you do not know what is “linked list” can take a look at the previous article. Today let’s implement a “two-way linked list”.

The node class of a bidirectional list

public class Node {
  /** * data field */
  public String data;

  /** * pointer field (pointing to the next node) */
  public Node next;

  /** * pointer field (pointing to previous node) */
  public Node pre;

  /** * constructor */
  public Node(String data) {
    this.data = data; }}Copy the code

Bidirectional linked list (lead node) basic code

public class DoubleLinkedList {

  / / head node
  private Node herd = new Node("HerdNode");

  public Node getHerd(a) {
    return herd;
  }

  public void setHerd(Node herd) {
    this.herd = herd; }}Copy the code

Add nodes at the end of the list

public void addAfter(Node newNode) {
    // Define auxiliary variables to be used by traversing the list
    Node temp = herd;
    while (true) {// get to the end of the list
      if(temp.next == null) {break;
      }
      // Move the secondary node back
      temp = temp.next;
    }
    // Add a new node to the end of the list
    temp.next = newNode; // The next pointer field of the tail node of the original list points to the new node
    newNode.pre = temp; // Place the previous pointer field of the new node at the end of the original list
}
Copy the code

Inserts data after the specified node content

Before you start coding, look at the following image to help you understand the code.

/** * Insert data ** after specified node content@paramNodeData specifies the contents of the node (after which node is inserted) *@paramNewNode newNode */
public void insertAfterNode(String nodeData, Node newNode) {
    // Check parameters
    if (nodeData == null) {
      throw new RuntimeException("Wrong entry!");
    }
    // Define auxiliary variables to be used by traversing the list
    Node temp = herd;
    // Define a tag that identifies the node where the specified content is found
    boolean flag = false;
    while (true) {
      // reach the end of the list and end the loop.
      if (temp == null) {
        break;
      }
      // End the loop by finding the specified node.
      if (nodeData.equals(temp.data)) {
        flag = true;
        break;
      }
      // Move the secondary node back
      temp = temp.next;
    }
    if (flag) {
      // Note: Temp represents the need to insert a new node after the node
      // Add a node to the end of the list
      if(temp.next ! =null) {
        // Place the preceding pointer field of the next temp node to the new temp node.
        temp.next.pre = newNode;
        // The next pointer field of the new node points to the next node of the temp node.
        newNode.next = temp.next;
      }
      // The next pointer field of the temp node points to the new node.
      temp.next = newNode;
      // Point the previous pointer field of the new node to the temp node.
      newNode.pre = temp;
    } else {
      throw new RuntimeException("Cannot insert node without finding specified node!"); }}Copy the code

Delete a node based on the specified node content

To better understand the code, take a look at the following figure.

/** * Deletes the specified node **@paramData Specifies the node content (deleted node content) */
public void delete(String data) {
    // Check parameters
    if (data == null) {
      throw new RuntimeException("Wrong entry!");
    }
    // Define auxiliary variables to be used by traversing the list
    Node temp = herd;
    // Define a tag that identifies the node where the specified content is found
    boolean flag = false;
    while (true) {// Reach the end of the list and end the loop.
      if(temp == null) {break;
      }
      // Find the node to delete
      if(data.equals(temp.data)){
        flag = true;
        break;
      }
      // Move the secondary node back
      temp = temp.next;
    }
    // Determine whether to save the node to be deleted
    if (flag) {
      // The next pointer field of the previous node points to the next node of the node to be deleted.
      temp.pre.next = temp.next;
      // If the node to be deleted is the last one, the following operation is not required
      if(temp.next ! =null) {
        // Change the previous pointer field of the next node to be deleted to the previous node.temp.next.pre = temp.pre; }}else {
      System.out.println("Node to delete not found!"); }}Copy the code

Through the above code and picture I believe you will have a bidirectional linked list of their own cognition, modify and query relatively simple, I will not demonstrate. If you have any questions, you can point them out. Feel the article is written pretty good, remember to click “like” to go yo.