看动画学算法之Java实现doublyLinkedList

简介：

和LinkedList相比，doublyLinkedList中的节点除了next指向下一个节点之外，还有一个prev之前的一个节点。所以被称为doublyLinkedList。 doublyLinkedList是一个双向链表，我们可以向前或者向后遍历list。

今天我们来学习一下doublyLinkedList的基本操作和概念。

1、doublyLinkedList的构建

和linkedList一样，doublyLinkedList是由一个一个的节点构成的。而每个节点除了要存储要保存的数据之外，还需要存储下一个节点和上一个节点的引用。

doublyLinkedList需要一个head节点，我们看下怎么构建：

public class DoublyLinkedList {

  Node head; // head 节点

  //Node表示的是Linked list中的节点，包含一个data数据，上一个节点和下一个节点的引用
  class Node {
      int data;
      Node next;
      Node prev;
      //Node的构造函数
      Node(int d) {
          data = d;
      }
  }
}

2、doublyLinkedList的操作

接下来，我们看一下doublyLinkedList的一些基本操作。

2.1 头部插入

头部插入的逻辑是：将新插入的节点作为新的head节点，并且将newNode.next指向原来的head节点。

同时需要将head.prev指向新的插入节点。

看下java代码：

  //插入到linkedList的头部
  public void push(int newData) {
      //构建要插入的节点
      Node newNode = new Node(newData);
      //新节点的next指向现在的head节点
      //新节点的prev指向null
      newNode.next = head;
      newNode.prev = null;

      if (head != null)
          head.prev = newNode;

      //现有的head节点指向新的节点
      head = newNode;
  }

2.2 尾部插入

尾部插入的逻辑是：找到最后一个节点，将最后一个节点的next指向新插入的节点，并且将新插入的节点的prev指向最后一个节点。

//新节点插入到list最后面
  public void append(int newData) {
      //创建新节点
      Node newNode = new Node(newData);
      //如果list是空，则新节点作为head节点
      if (head == null) {
          newNode.prev = null;
          head = newNode;
          return;
      }

      newNode.next = null;
      //找到最后一个节点
      Node last = head;
      while (last.next != null) {
          last = last.next;
      }
      //插入
      last.next = newNode;
      newNode.prev = last;
      return;
  }

2.3 插入给定的位置

如果要在给定的位置插入节点，我们需要先找到插入位置的前一个节点，然后将前一个节点的next指向新节点。新节点的prev指向前一个节点。

同时我们需要将新节点的next指向下一个节点，下一个节点的prev指向新的节点。

 //插入在第几个元素之后
  public void insertAfter(int index, int newData) {
      Node prevNode = head;
      for (int i = 1; i < index; i++) {
          if (prevNode == null) {
              System.out.println("输入的index有误，请重新输入");
              return;
          }
          prevNode = prevNode.next;
      }
      //创建新的节点
      Node newNode = new Node(newData);
      //新节点的next指向prevNode的下一个节点
      newNode.next = prevNode.next;
      //将新节点插入在prevNode之后
      prevNode.next = newNode;
      //将新节点的prev指向prevNode
      newNode.prev = prevNode;

      //newNode的下一个节点的prev指向newNode
      if (newNode.next != null)
          newNode.next.prev = newNode;
  }

2.4 删除指定位置的节点

删除节点的逻辑是：找到要删除节点的前一个节点，和下一个节点。前一个节点的next指向下一个节点，下一个节点的prev指向前一个节点。

//删除特定位置的节点
  void deleteNode(int index)
  {
      // 如果是空的，直接返回
      if (head == null)
          return;

      // head节点
      Node temp = head;

      // 如果是删除head节点
      if (index == 1)
      {
          head = temp.next;
          return;
      }

      // 找到要删除节点的前一个节点
      for (int i=1; temp!=null && i<index-1; i++)
          temp = temp.next;

      // 如果超出范围
      if (temp == null || temp.next == null)
          return;

      // temp->next 是要删除的节点，删除节点
      Node next = temp.next.next;
      temp.next = next;
      Node prev = temp.next.prev;
      prev.prev = prev;
  }

到此这篇关于看动画学算法之Java实现doublyLinkedList的文章就介绍到这了,更多相关Java实现doublyLinkedList内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://juejin.cn/post/7013539673838452767