簡介：

和LinkedList相比，doublyLinkedList中的節(jié)點(diǎn)除了next指向下一個(gè)節(jié)點(diǎn)之外，還有一個(gè)prev之前的一個(gè)節(jié)點(diǎn)。所以被稱為doublyLinkedList。 doublyLinkedList是一個(gè)雙向鏈表，我們可以向前或者向后遍歷list。

今天我們來學(xué)習(xí)一下doublyLinkedList的基本操作和概念。

1、doublyLinkedList的構(gòu)建

和linkedList一樣，doublyLinkedList是由一個(gè)一個(gè)的節(jié)點(diǎn)構(gòu)成的。而每個(gè)節(jié)點(diǎn)除了要存儲要保存的數(shù)據(jù)之外，還需要存儲下一個(gè)節(jié)點(diǎn)和上一個(gè)節(jié)點(diǎn)的引用。

doublyLinkedList需要一個(gè)head節(jié)點(diǎn)，我們看下怎么構(gòu)建：

public class DoublyLinkedList {

  Node head; // head 節(jié)點(diǎn)

  //Node表示的是Linked list中的節(jié)點(diǎn)，包含一個(gè)data數(shù)據(jù)，上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的引用
  class Node {
      int data;
      Node next;
      Node prev;
      //Node的構(gòu)造函數(shù)
      Node(int d) {
          data = d;
      }
  }
}

2、doublyLinkedList的操作

接下來，我們看一下doublyLinkedList的一些基本操作。

2.1 頭部插入

頭部插入的邏輯是：將新插入的節(jié)點(diǎn)作為新的head節(jié)點(diǎn)，并且將newNode.next指向原來的head節(jié)點(diǎn)。

同時(shí)需要將head.prev指向新的插入節(jié)點(diǎn)。

看下java代碼：

  //插入到linkedList的頭部
  public void push(int newData) {
      //構(gòu)建要插入的節(jié)點(diǎn)
      Node newNode = new Node(newData);
      //新節(jié)點(diǎn)的next指向現(xiàn)在的head節(jié)點(diǎn)
      //新節(jié)點(diǎn)的prev指向null
      newNode.next = head;
      newNode.prev = null;

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

      //現(xiàn)有的head節(jié)點(diǎn)指向新的節(jié)點(diǎn)
      head = newNode;
  }

2.2 尾部插入

尾部插入的邏輯是：找到最后一個(gè)節(jié)點(diǎn)，將最后一個(gè)節(jié)點(diǎn)的next指向新插入的節(jié)點(diǎn)，并且將新插入的節(jié)點(diǎn)的prev指向最后一個(gè)節(jié)點(diǎn)。

//新節(jié)點(diǎn)插入到list最后面
  public void append(int newData) {
      //創(chuàng)建新節(jié)點(diǎn)
      Node newNode = new Node(newData);
      //如果list是空，則新節(jié)點(diǎn)作為head節(jié)點(diǎn)
      if (head == null) {
          newNode.prev = null;
          head = newNode;
          return;
      }

      newNode.next = null;
      //找到最后一個(gè)節(jié)點(diǎn)
      Node last = head;
      while (last.next != null) {
          last = last.next;
      }
      //插入
      last.next = newNode;
      newNode.prev = last;
      return;
  }

2.3 插入給定的位置

如果要在給定的位置插入節(jié)點(diǎn)，我們需要先找到插入位置的前一個(gè)節(jié)點(diǎn)，然后將前一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)。新節(jié)點(diǎn)的prev指向前一個(gè)節(jié)點(diǎn)。

同時(shí)我們需要將新節(jié)點(diǎn)的next指向下一個(gè)節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)的prev指向新的節(jié)點(diǎn)。

 //插入在第幾個(gè)元素之后
  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;
      }
      //創(chuàng)建新的節(jié)點(diǎn)
      Node newNode = new Node(newData);
      //新節(jié)點(diǎn)的next指向prevNode的下一個(gè)節(jié)點(diǎn)
      newNode.next = prevNode.next;
      //將新節(jié)點(diǎn)插入在prevNode之后
      prevNode.next = newNode;
      //將新節(jié)點(diǎn)的prev指向prevNode
      newNode.prev = prevNode;

      //newNode的下一個(gè)節(jié)點(diǎn)的prev指向newNode
      if (newNode.next != null)
          newNode.next.prev = newNode;
  }

2.4 刪除指定位置的節(jié)點(diǎn)

刪除節(jié)點(diǎn)的邏輯是：找到要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，和下一個(gè)節(jié)點(diǎn)。前一個(gè)節(jié)點(diǎn)的next指向下一個(gè)節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)的prev指向前一個(gè)節(jié)點(diǎn)。

//刪除特定位置的節(jié)點(diǎn)
  void deleteNode(int index)
  {
      // 如果是空的，直接返回
      if (head == null)
          return;

      // head節(jié)點(diǎn)
      Node temp = head;

      // 如果是刪除head節(jié)點(diǎn)
      if (index == 1)
      {
          head = temp.next;
          return;
      }

      // 找到要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
      for (int i=1; temp!=null && i<index-1; i++)
          temp = temp.next;

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

      // temp->next 是要?jiǎng)h除的節(jié)點(diǎn)，刪除節(jié)點(diǎn)
      Node next = temp.next.next;
      temp.next = next;
      Node prev = temp.next.prev;
      prev.prev = prev;
  }

到此這篇關(guān)于看動(dòng)畫學(xué)算法之Java實(shí)現(xiàn)doublyLinkedList的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn)doublyLinkedList內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！

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