欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java雙向鏈表的操作

 更新時間：2022年06月22日 16:16:31   作者：蘿詩粉  
這篇文章主要介紹了Java雙向鏈表的操作，雙向鏈表，對于該鏈表中的任意節(jié)點(diǎn)，既可以通過該節(jié)點(diǎn)向前遍歷，也可以通過該節(jié)點(diǎn)向后遍歷，雙向鏈表在實(shí)際工程中應(yīng)用非常廣泛，是使用鏈表這個結(jié)構(gòu)的首選

前言

我們之前學(xué)的單鏈表，默認(rèn)只能從鏈表的頭部遍歷到鏈表的尾部，在實(shí)際中應(yīng)用太少見，太局限；而雙向鏈表，對于該鏈表中的任意節(jié)點(diǎn)，既可以通過該節(jié)點(diǎn)向前遍歷，也可以通過該節(jié)點(diǎn)向后遍歷，雙向鏈表在實(shí)際工程中應(yīng)用非常廣泛，是使用鏈表這個結(jié)構(gòu)的首選。

一、認(rèn)識雙向鏈表

單向鏈表不僅保存了當(dāng)前的結(jié)點(diǎn)值，還保存了下一個結(jié)點(diǎn)的地址

在這里插入圖片描述

雙向鏈表不僅保存了當(dāng)前節(jié)點(diǎn)的值，還保存了上一個結(jié)點(diǎn)的地址和下一個結(jié)點(diǎn)的地址

在這里插入圖片描述

定義一個雙向鏈表的結(jié)點(diǎn)類：

結(jié)點(diǎn)中既要保存當(dāng)前節(jié)點(diǎn)的值，還要保存此節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的地址和此節(jié)點(diǎn)的后繼節(jié)點(diǎn)的地址

class DoubleNode{
    public DoubleNode next;
    DoubleNode prev;
    int val;
    DoubleNode tail;

    public DoubleNode() {}

    public DoubleNode(int val) {
        this.val = val;
    }

    public DoubleNode(DoubleNode prev, int val, DoubleNode tail) {
        this.prev = prev;
        this.val = val;
        this.tail = tail;
    }
}

定義一個雙向鏈表類：

既可以從前向后，也可以從后向前，所以在這個類中，即保存一下頭結(jié)點(diǎn)，也保存一下尾結(jié)點(diǎn)的值

public class DoubleLinkedList {
    private int size;
    private DoubleNode head;
    private DoubleNode tail;
}

二、雙向鏈表的增刪改查

1.插入

頭插

在當(dāng)前鏈表的頭部插入一個節(jié)點(diǎn)，讓當(dāng)前鏈表的頭結(jié)點(diǎn)head前驅(qū)指向要插入的節(jié)點(diǎn)node，然后讓node的后繼指向head，然后讓head = node，讓node成為鏈表的頭結(jié)點(diǎn)

在這里插入圖片描述

代碼如下：

/**
     * 頭插
     */
    public void addFirst(int val){
        DoubleNode node = new DoubleNode(val);
        if (head == null){
            head = tail = node;
        }else{
            node.next = head;
            head.prev = node;
            head = node;
        }
        size++;
    }

尾插

和頭插一樣，只不過在鏈表的尾部插入

在這里插入圖片描述

代碼如下：

 public void addLast(int val){
        DoubleNode node = new DoubleNode(val);
        if (head == null){
            head = tail =node;
        }else{
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        size++;
    }

在index位置插入

在索引為index的位置插入值為val的節(jié)點(diǎn)：

插入還是要找前驅(qū)節(jié)點(diǎn)，但雙向鏈表找前驅(qū)節(jié)點(diǎn)比單向鏈表找前驅(qū)節(jié)點(diǎn)要靈活很多，單向鏈表只能從頭走到尾，假如此時有100個節(jié)點(diǎn)，要在索引為98的位置插入節(jié)點(diǎn)，那么雙向鏈表就可以從尾結(jié)點(diǎn)開始找，會方便很多

如何判斷從前向后找，還是從后向前找？

  • 1.index < size / 2 – >從前向后找，插入位置在前半部分
  • 2.index > size / 2 – >從后向前找，插入位置在后半部分

在這里插入圖片描述

代碼如下：

/**
     * 在index位置插入
     * @param index
     * @param val
     */
    public void add(int index,int val){
        DoubleNode cur = new DoubleNode(val);
        if (index < 0 || index > size){
            System.err.println("add index illegal");
            return;
        }else{
            if (index == 0){addFirst(val);}
            else if (index == size){addLast(val);}
            else{
                DoubleNode prev = node(index-1);
                DoubleNode next = prev.next;
                cur.next = next;
                next.prev = cur;
                prev.next = cur;
                cur.prev = prev;
            }
        }
        size++;
    }
/**
     * 根據(jù)索引值找到對應(yīng)的結(jié)點(diǎn)
     * @param index
     * @return
     */
    private DoubleNode node(int index){
        DoubleNode x = null;
        if (index < size/2){
            x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
        }else{
            x = tail;
            for (int i = size - 1; i > index ; i--) {
                x = x.prev;
            }
        }
        return x;
    }

2.修改

代碼如下：

/**
     * 修改雙向鏈表index位置的結(jié)點(diǎn)值為newVal
     */
    public int set(int index,int newVal){
        DoubleNode dummyHead = new DoubleNode();
        dummyHead.next = head;
        DoubleNode prev = dummyHead;
        DoubleNode cur = prev.next;
        if (index < 0 || index > size - 1){
            System.err.println("set index illegal");
        }else{
            for (int i = 0; i < index; i++) {
                prev = prev.next;
                cur = cur.next;
            }
        }
        int oldVal = cur.val;
        cur.val = newVal;
        return oldVal;
    }

3.查詢

代碼如下：

 /**
     * 查詢index位置的結(jié)點(diǎn)值
     */
    public int get(int index){
        DoubleNode dummyHead = new DoubleNode();
        dummyHead.next = head;
        DoubleNode prev = dummyHead;
        DoubleNode cur = prev.next;
        if (index < 0 || index > size - 1){
            System.err.println("get index illegal");
        }else{
            for (int i = 0; i < index; i++) {
                prev = prev.next;
                cur = cur.next;
            }
        }
        return cur.val;
    }

4.刪除

刪除index位置的節(jié)點(diǎn)

代碼如下：

//刪除鏈表index位置的結(jié)點(diǎn)
    public void removeIndex(int index){
        if (index < 0 || index > size - 1){
            System.err.println("remove index illegal");
            return;
        }
        DoubleNode cur = node(index);
        unlink(cur);
    }
 /**
     * 刪除當(dāng)前雙向鏈表的node結(jié)點(diǎn)
     * 分治法
     * @param node
     */
    private void unlink (DoubleNode node){
        DoubleNode prev = node.prev;
        DoubleNode successor = node.next;
        //1.先處理node的前半部分
        if (prev == null){
            head = successor;
        }else{
            //前驅(qū)不為空的情況
            prev.next = successor;
            node.prev = null;
        }
        if (successor == null){
            tail = prev;
        }else{
            successor.prev = prev;
            node.next = null;
        }
        size--;
    }

頭刪

調(diào)用刪除任意位置的節(jié)點(diǎn)即可

代碼如下：

//頭刪
    public void removeFirst(){
      removeIndex(0);
    }

尾刪

調(diào)用刪除任意位置的節(jié)點(diǎn)即可

代碼如下：

//尾刪
    public void removeLast(){
        removeIndex(size - 1);
    }

刪除第一個值為val的節(jié)點(diǎn)

代碼如下：

//刪除第一個值為val的結(jié)點(diǎn)
    public void removeValOnce(int val){
        if (head == null){
            return;
        }
        for (DoubleNode x = head;x != null;x = x.next){
            if (x.val == val){
                unlink(x);
                break;
            }
        }
    }

 /**
     * 刪除當(dāng)前雙向鏈表的node結(jié)點(diǎn)
     * 分治法
     * @param node
     */
    private void unlink (DoubleNode node){
        DoubleNode prev = node.prev;
        DoubleNode successor = node.next;
        //1.先處理node的前半部分
        if (prev == null){
            head = successor;
        }else{
            //前驅(qū)不為空的情況
            prev.next = successor;
            node.prev = null;
        }
        if (successor == null){
            tail = prev;
        }else{
            successor.prev = prev;
            node.next = null;
        }
        size--;
    }

刪除所有值為val的值

代碼如下：

//刪除鏈表中所有值為val的結(jié)點(diǎn)
    public void removeAllVal(int val){
        for (DoubleNode x = head;x != null;){
            if (x.val == val){
                //暫存一下x的下一個結(jié)點(diǎn)
                DoubleNode next = x.next;
                unlink(x);
                x = next;
            }else{
                //val不是待刪除的元素
                x = x.next;
            }
        }
    }
 /**
     * 刪除當(dāng)前雙向鏈表的node結(jié)點(diǎn)
     * 分治法
     * @param node
     */
    private void unlink (DoubleNode node){
        DoubleNode prev = node.prev;
        DoubleNode successor = node.next;
        //1.先處理node的前半部分
        if (prev == null){
            head = successor;
        }else{
            //前驅(qū)不為空的情況
            prev.next = successor;
            node.prev = null;
        }
        if (successor == null){
            tail = prev;
        }else{
            successor.prev = prev;
            node.next = null;
        }
        size--;
    }

總結(jié)

本篇博客帶大家了解了一下什么是雙向鏈表，和單鏈表有什么區(qū)別，已經(jīng)雙向鏈表的一些基本的增刪改查的操作，

到此這篇關(guān)于Java雙向鏈表的操作的文章就介紹到這了,更多相關(guān)Java雙向鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • java兩個數(shù)組合并為一個數(shù)組的幾種方法

    java兩個數(shù)組合并為一個數(shù)組的幾種方法

    這篇文章主要給大家介紹了關(guān)于java兩個數(shù)組合并為一個數(shù)組的幾種方法,最近在寫代碼時遇到了需要合并兩個數(shù)組的需求,文中將每種方法都介紹的非常詳細(xì),需要的朋友可以參考下
    2023-07-07
  • 一篇文章弄懂Java8中的時間處理

    一篇文章弄懂Java8中的時間處理

    Java8以前Java處理日期、日歷和時間的方式一直為社區(qū)所詬病,將 java.util.Date設(shè)定為可變類型,以及SimpleDateFormat的非線程安全使其應(yīng)用非常受限,下面這篇文章主要給大家介紹了關(guān)于Java8中時間處理的相關(guān)資料,需要的朋友可以參考下
    2022-01-01
  • java實(shí)現(xiàn)日期拆分的方法

    java實(shí)現(xiàn)日期拆分的方法

    這篇文章主要介紹了java實(shí)現(xiàn)日期拆分的方法,基于java日期類實(shí)現(xiàn)對日期字符串的拆分功能,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-07-07
  • 淺談SpringBoot集成Redis實(shí)現(xiàn)緩存處理(Spring AOP實(shí)現(xiàn))

    淺談SpringBoot集成Redis實(shí)現(xiàn)緩存處理(Spring AOP實(shí)現(xiàn))

    這篇文章主要介紹了淺談SpringBoot集成Redis實(shí)現(xiàn)緩存處理(Spring AOP實(shí)現(xiàn))，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
    2017-12-12
  • JAVA異常體系結(jié)構(gòu)詳解

    JAVA異常體系結(jié)構(gòu)詳解

    Java把異常當(dāng)作對象來處理，并定義一個基類java.lang.Throwable作為所有異常的超類，下面通過本文給大家分享JAVA異常體系結(jié)構(gòu)，感興趣的朋友一起看看吧
    2017-11-11
  • 解決Java?API不能遠(yuǎn)程訪問HBase的問題

    解決Java?API不能遠(yuǎn)程訪問HBase的問題

    這篇文章主要介紹了解決Java?API不能遠(yuǎn)程訪問HBase的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2022-06-06
  • Java程序包不存在的三種解決方法

    Java程序包不存在的三種解決方法

    有時候我們在導(dǎo)入程序之后,系統(tǒng)會給出錯誤提示:Java:程序包xxxx不存在,本文主要介紹了Java程序包不存在的三種解決方法,具有一定的參考價值,感興趣的可以了解一下
    2024-02-02
  • SpringBoot?ApplicationContext接口深入分析

    SpringBoot?ApplicationContext接口深入分析

    ApplicationContext是Spring應(yīng)用程序中的中央接口，由于繼承了多個組件，使得ApplicationContext擁有了許多Spring的核心功能，如獲取bean組件，注冊監(jiān)聽事件，加載資源文件等
    2022-11-11
  • ThreadLocal原理介紹及應(yīng)用場景

    ThreadLocal原理介紹及應(yīng)用場景

    本文詳細(xì)講解了ThreadLocal原理介紹及應(yīng)用場景，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-12-12
  • Java多線程編程之CountDownLatch同步工具使用實(shí)例

    Java多線程編程之CountDownLatch同步工具使用實(shí)例

    這篇文章主要介紹了Java多線程編程之CountDownLatch同步工具使用實(shí)例,需要的朋友可以參考下
    2015-05-05

最新評論