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

Java實現(xiàn)雙鏈表的示例代碼

 更新時間：2022年09月26日 09:10:37   作者：熬夜磕代碼丶  
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結點中都有兩個指針，分別指向直接后繼和直接前驅。本文將用Java語言實現(xiàn)雙鏈表，需要的可以參考一下

一、雙向鏈表是什么

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環(huán)鏈表。

LinkedList底層就是一個雙向鏈表，我們來實現(xiàn)一個雙向鏈表。

這里多一個尾指針，方便我們對尾插操作從O(n)降到O(1).每個結點多了前驅結點，方便我們對鏈表進行操作。

二、具體方法實現(xiàn)

定義結點

class ListNode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }

下標訪問異常

public class IndexWrongException extends RuntimeException{
    public IndexWrongException() {
    }

    public IndexWrongException(String message) {
        super(message);
    }
}

獲取鏈表長度

class ListNode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }

打印鏈表

class ListNode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }

清空鏈表

public void clear(){
        if(this.head == null) {
            return;
        }
        ListNode cur = this.head;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        head = null;
        tail = null;
    }

頭插法

public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }

尾插法

public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        tail.next = node;
        node.prev = tail;
        tail = node;
    }

指定位置插入

public void addIndex(int index,int data) throws IndexWrongException{
        if(index < 0 || index > size()) {
            throw new IndexWrongException("輸入下標不合法");
        }
        ListNode node = new ListNode(data);
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = this.head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

查找元素

public boolean contains(int key){
        if(head == null) {
            return false;
        }
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.value == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

刪除第一次出現(xiàn)的關鍵字

public void remove(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                        }
                    }
                return;
                }
            cur = cur.next;
            }
        }

刪除所有值為key的節(jié)點

public void removeAllKey(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                    }
                }
            }
            cur = cur.next;
        }
    }

三、完整代碼

public class LinkedList {
    static class ListNode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }
    ListNode head;
    ListNode tail;
    //頭插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        tail.next = node;
        node.prev = tail;
        tail = node;
    }
    //任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標
    public void addIndex(int index,int data) throws IndexWrongException{
        if(index < 0 || index > size()) {
            throw new IndexWrongException("輸入下標不合法");
        }
        ListNode node = new ListNode(data);
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = this.head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }
    //查找是否包含關鍵字key是否在單鏈表當中
    public boolean contains(int key){
        if(head == null) {
            return false;
        }
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.value == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //刪除第一次出現(xiàn)關鍵字為key的節(jié)點
    public void remove(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                        }
                    }
                return;
                }
            cur = cur.next;
            }
        }
    //刪除所有值為key的節(jié)點
    public void removeAllKey(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                    }
                }
            }
            cur = cur.next;
        }
    }
    //得到單鏈表的長度
    public int size(){
        ListNode cur = head;
        int count = 0;
        while(cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }
    public void display(){
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.value+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void clear(){
        if(this.head == null) {
            return;
        }
        ListNode cur = this.head;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        head = null;
        tail = null;
    }
}

到此這篇關于Java實現(xiàn)雙鏈表的示例代碼的文章就介紹到這了,更多相關Java雙鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

  • Java中的LinkedHashMap及LRU緩存機制詳解

    Java中的LinkedHashMap及LRU緩存機制詳解

    這篇文章主要介紹了Java中的LinkedHashMap及LRU緩存機制詳解,LinkedHashMap繼承自HashMap,它的多種操作都是建立在HashMap操作的基礎上的,同HashMap不同的是,LinkedHashMap維護了一個Entry的雙向鏈表,保證了插入的Entry中的順序,需要的朋友可以參考下
    2023-09-09
  • Java隊列數(shù)據(jù)結構的實現(xiàn)

    Java隊列數(shù)據(jù)結構的實現(xiàn)

    這篇文章主要介紹了Java隊列數(shù)據(jù)結構的實現(xiàn),隊列是一種特殊的線性表,只允許在表的隊頭進行刪除操作，在表的后端進行插入操作，隊列是一個有序表先進先出，想了解更多相關資料的小伙伴可以參考下面文章的詳細內容
    2021-12-12
  • Java8中使用流方式查詢數(shù)據(jù)庫的方法

    Java8中使用流方式查詢數(shù)據(jù)庫的方法

    這篇文章主要介紹了Java8中使用流方式查詢數(shù)據(jù)庫的相關資料,需要的朋友可以參考下
    2016-01-01
  • java如何用Processing生成馬賽克風格的圖像

    java如何用Processing生成馬賽克風格的圖像

    這篇文章主要介紹了如何用java如何用Processing生成馬賽克風格的圖像,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
    2020-03-03
  • 淺談java中的移動位運算：,>>>

    淺談java中的移動位運算：,>>>

    這篇文章主要介紹了java中的移動位運算：,>>>文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
    2019-03-03
  • 詳解JAVA中implement和extends的區(qū)別

    詳解JAVA中implement和extends的區(qū)別

    這篇文章主要介紹了詳解JAVA中implement和extends的區(qū)別的相關資料,extends是繼承接口，implement是一個類實現(xiàn)一個接口的關鍵字，需要的朋友可以參考下
    2017-08-08
  • java自帶的MessageDigest實現(xiàn)文本的md5加密算法

    java自帶的MessageDigest實現(xiàn)文本的md5加密算法

    這篇文章主要介紹了java自帶的MessageDigest實現(xiàn)文本的md5加密算法,需要的朋友可以參考下
    2015-12-12
  • 淺談Java鎖機制

    淺談Java鎖機制

    在多線程環(huán)境下，程序往往會出現(xiàn)一些線程安全問題，為此，Java提供了一些線程的同步機制來解決安全問題，比如：synchronized鎖和Lock鎖都能解決線程安全問題。下面小編就來詳細介紹該知識點,需要的朋友可以參考一下
    2021-09-09
  • IDEA運行Tomcat中文亂碼出現(xiàn)的各種問題

    IDEA運行Tomcat中文亂碼出現(xiàn)的各種問題

    這篇文章主要介紹了IDEA運行Tomcat中文亂碼的各種問題及解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-11-11
  • 教你怎么用Java開發(fā)掃雷游戲

    教你怎么用Java開發(fā)掃雷游戲

    我們那時候上機經(jīng)常玩掃雷,試想如果我當年可以用 java 寫個掃雷出來,那場面不用我多說了吧,大家讓開,我要開始裝逼了,之前用JavaScript寫過了一個掃雷,這次我用java再寫了一遍,權當是復習咯.文中有非常詳細的代碼示例,需要的朋友可以參考下
    2021-05-05

最新評論