看動(dòng)畫學(xué)算法之Java實(shí)現(xiàn)doublyLinkedList
簡(jiǎn)介:
和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)除了要存儲(chǔ)要保存的數(shù)據(jù)之外,還需要存儲(chǔ)下一個(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有誤,請(qǐng)重新輸入"); 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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
實(shí)例解決Java異常之OutOfMemoryError的問題
在本篇文章中,我們給大家分享了關(guān)于解決Java異常之OutOfMemoryError的問題的方法,有此需要的朋友們學(xué)習(xí)下。2019-02-02淺談springboot之JoinPoint的getSignature方法
這篇文章主要介紹了springboot之JoinPoint的getSignature方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-06-06關(guān)于springboot 配置date字段返回時(shí)間戳的問題
這篇文章主要介紹了springboot 配置date字段返回時(shí)間戳的問題,在springboot2.0后,spring會(huì)將Date字段自動(dòng)給轉(zhuǎn)成UTC字符串了(在沒有配置的情況下),所以date需要轉(zhuǎn)換成時(shí)間戳還是yyyy-MM-dd HH:mm:ss,具體解決方法跟隨小編一起看看吧2021-07-07深入Java7的一些新特性以及對(duì)腳本語言支持API的介紹
本篇文章是對(duì)Java7的一些新特性以及對(duì)腳本語言支持API的概述,需要的朋友參考下2013-05-05