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

Java中LinkedList的模擬實現(xiàn)

 更新時間:2022年06月20日 10:04:54   作者:XH學(xué)Java  
本文主要介紹了Java中LinkedList的模擬實現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

??關(guān)于LinkedList

LinkedList的底層是用一個雙向鏈表實現(xiàn)的,即一個結(jié)點中除了有一個引用指向下一個結(jié)點的地址,還有一個引用指向前一個結(jié)點的地址

LinkedList還有三個成員變量:

  • ??size,表示該鏈表中結(jié)點的個數(shù)
  • ??first,指向鏈表首結(jié)點
  • ??last,指向鏈表尾結(jié)點

模擬實現(xiàn)LinkedList

??準(zhǔn)備工作

??創(chuàng)建靜態(tài)內(nèi)部類ListNode,后續(xù)創(chuàng)建結(jié)點都需要ListNode來創(chuàng)建新的結(jié)點

    private static class ListNode<E> {
        ListNode<E> pre;  //指向前一個結(jié)點
        ListNode<E> next; //指向下一個結(jié)點
        E val;  //結(jié)點的值
 
        public ListNode(E val){
            this.val = val;
        }
    }

??創(chuàng)建成員變量:first,last,size

    private ListNode<E> first;  //指向鏈表首結(jié)點
    private ListNode<E> last;  //指向鏈表尾結(jié)點
    private int size;  //鏈表結(jié)點的個數(shù)

??重寫toString()方法,在進(jìn)行測試方法的時候需要將鏈表打印出來

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        if(first == null){
            sb.append("]");
        }else {
            ListNode<E> cur = first;
            while(cur.next != null){
                sb.append(cur.val);
                sb.append(",");
                cur = cur.next;
            }
            sb.append(cur.val);
            sb.append("]");
        }
        return sb.toString();
    }

??頭插

??在鏈表的頭部插入結(jié)點,這里分兩種情況:鏈表為空,鏈表不為空

??鏈表為空:直接將first,last指向該結(jié)點,因為這個結(jié)點既是第一個結(jié)點,也是最后一個結(jié)點
??鏈表不為空:將first的pre執(zhí)行該結(jié)點,再將該結(jié)點的next指向first,更新first位置

??在結(jié)點頭插完后,更新size的長度,進(jìn)行size++

    public void addFirst(E e){
        ListNode<E> newNode = new ListNode<>(e);
        if(first == null){
            first = newNode;
            last = newNode;
        }else {
            first.pre = newNode;
            newNode.next = first;
            first = newNode;
        }
        size++;
    }

??進(jìn)行測試:依次頭插入1,2,3,4,打印list

        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addFirst(1);
        list.addFirst(2);
        list.addFirst(3);
        list.addFirst(4);
        System.out.println(list);

??打印結(jié)果:因為是頭插,所以打印4,3,2,1

尾插

  • ??在鏈表的尾部插入結(jié)點,分兩種情況:鏈表為空,鏈表不為空
  • ??鏈表為空:直接將first,last指向該結(jié)點,該結(jié)點既是鏈表的首結(jié)點,又是最后一個結(jié)點
  • ??鏈表不為空last的next執(zhí)行該節(jié)點,該節(jié)點的pre指向last,更新last位置
  • ??在結(jié)點尾插完后,更新size的長度,進(jìn)行size++
    public void addLast(E e){
        ListNode<E> newNode = new ListNode<>(e);
        if(first == null){
            first = newNode;
            last = newNode;
        }else {
            last.next = newNode;
            newNode.pre = last;
            last = newNode;
        }
        size++;
    }

??進(jìn)行測試:依次尾插入1,2,3,4,打印list

        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        System.out.println(list);

??打印結(jié)果:因為是尾插,所以打印1,2,3,4 

??在任意位置插入

這里分三種情況討論:在第一個位置插入,在最后一個位置插入,在其他位置插入

??在第一個位置插入:相當(dāng)于頭插,調(diào)用addFirst()方法
??在最后一個位置插入:相當(dāng)于尾插,調(diào)用addLast()方法

??在其他位置插入看下圖解析

    public boolean addIndex(int index,E e){
        ListNode<E> newNode = new ListNode<>(e);
        if(index < 0 && index > size){
            throw new IndexOutOfBoundsException("addIndex:下標(biāo)越界");
        }
        if(index == size){
            addLast(e);
        }else if(index == 0){
            addFirst(e);
        }else {
            ListNode<E> cur = first;
            for(int i = 0;i < index;i++){
                cur = cur.next;
            }
            newNode.pre = cur.pre;
            newNode.next = cur;
            newNode.pre.next = newNode;
            cur.pre = newNode;
            size++;
        }
        return true;
    }

??進(jìn)行測試:原來鏈表為1,2,3,4,在位置0插入1,在位置5插入5,在位置3插入3 

        list.addIndex(0,1);
        list.addIndex(4,5);
        list.addIndex(3,3);
        System.out.println(list);

??打印結(jié)果:打印為1,1,2,3,3,4,5

??刪除remove

這里分為三種情況:刪除的是第一個元素,刪除的是最后一個元素,刪除其他元素

  • ??刪除一個元素:將first指向first的next,再將first的pre指向null
  • ??刪除最后一個元素:將last更新為last的pre位置,再將last的next指向null

??刪除其他位置元素:參照下圖解析

??刪除完后,進(jìn)行size--操作 

    public void remove(E e){
        ListNode<E> cur = first;
        while(cur != null){
            if(e.equals(cur.val)){
                break;
            }
            cur = cur.next;
        }
        if(cur == first){
            first = first.next;
            first.pre = null;
        }else if(cur == last){
            last = last.pre;
            last.next = null;
        }else {
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;
        }
        size--;
    }

??進(jìn)行測試:原鏈表為1,2,3,4,5,刪除1,刪除5,刪除3

        list.remove(1);
        list.remove(5);
        list.remove(3);
        System.out.println(list);

??打印結(jié)果:打印2,4

??刪除removeAll

這個與刪除一次出現(xiàn)元素e的做法差不多,只是在找到第一次出現(xiàn)元素e時,將它刪掉,繼續(xù)遍歷鏈表

    public void removeAll(E e){
        ListNode<E> cur = first;
        while(cur != null){
            if(cur.val.equals(e)){
                if(cur == first){
                    first = first.next;
                    first.pre = null;
                }else if(cur == last){
                    last = last.pre;
                    last.next = null;
                }else {
                    cur.pre.next = cur.next;
                    cur.next.pre = cur.pre;
                }
                size--;
            }
            cur = cur.next;
        }
    }

??進(jìn)行測試:鏈表為1,2,1,3,1,將所有的1全部刪掉

        list.removeAll(1);
        System.out.println(list);

??打印結(jié)果:鏈表中的元素只剩下2,3 

找元素下標(biāo)indexOf

創(chuàng)建一個下標(biāo)index,從0開始增加,每遍歷一個元素進(jìn)行index++,如果遍歷的元素是要找的元素則返回index,當(dāng)遍歷完鏈表沒有要找的元素時,返回-1

    public int indexOf(E e){
        ListNode<E> cur = first;
        int index = 0;
        while(cur != null){
            if(e.equals(cur.val)){
                return index;
            }else {
                index++;
                cur = cur.next;
            }
        }
        return -1;
    }

??進(jìn)行測試:鏈表為1,2,3,4,5,找3的位置和6的位置

        System.out.println(list.indexOf(3));
        System.out.println(list.indexOf(6));

??打印結(jié)果:3在下標(biāo)為2的位置,6不在該鏈表中,故返回-1

??找元素下標(biāo)lastIndexOf

這個從鏈表尾部往前遍歷,創(chuàng)建index值為size-1,當(dāng)元素不為我們要找的元素時,index--,找到返回index,當(dāng)遍歷完整個鏈表都沒有找到時,返回-1

    public int lastIndexOf(E e){
        ListNode<E> cur = last;
        int index = size-1;
        while(cur != null){
            if(e.equals(cur.val)){
                return index;
            }else {
                cur = cur.pre;
                index--;
            }
        }
        return -1;
    }

??進(jìn)行測試:鏈表為1,2,3,3,4,5,找3的位置和6的位置

        System.out.println(list.lastIndexOf(3));
        System.out.println(list.lastIndexOf(6));

 ??打印結(jié)果:最后一個3的下標(biāo)為3,6不在該鏈表中

??判斷鏈表是否包含某個元素

這里可以調(diào)用indexOf方法,看返回的是不是-1,如果不是-1則說明鏈表包含該元素,如果返回的是-1,說明鏈表不包含該元素

    public boolean contains(E e){
        return -1 != indexOf(e);
    }

??進(jìn)行測試:鏈表為1,2,3,4,5,判斷該鏈表是否包含2和6

        boolean ret = list.contains(2);
        boolean ret1 = list.contains(6);
        System.out.println(ret);
        System.out.println(ret1);

??輸出結(jié)果:2在鏈表中,6不在鏈表中

獲得鏈表長度

直接返回size即可

    public int size(){
        return size;
    }

??進(jìn)行測試:返回空鏈表的size,和有元素的size

        list.clear();
        System.out.println(list.size());
        list.addFirst(1);
        System.out.println(list.size());

 ??打印結(jié)果:

鏈表判空

判斷鏈表為空有兩種方式:判斷size是否為0或者判斷first是否指向null

    public boolean isEmpty(){
        //return size==0;
        return first==null;
    }

??進(jìn)行測試:看有元素的鏈表是否為空,和空鏈表是否為空

        list.clear();
        list.addFirst(1);
        boolean ret1 = list.isEmpty();
        System.out.println(ret1);
        list.clear();
        boolean ret2 = list.isEmpty();
        System.out.println(ret2);

??打印結(jié)果:

清空鏈表

清空操作就是將first指向null,將last指向null,將size置0

    public void clear(){
        first = null;
        last = null;
        size = 0;
    }

??進(jìn)行測試:執(zhí)行清空操作,打印list

        list.clear();
        System.out.println(list);

??打印結(jié)果:鏈表中沒有元素

 到此這篇關(guān)于Java中LinkedList的模擬實現(xiàn)的文章就介紹到這了,更多相關(guān)Java中 LinkedList的模擬內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Spring?Boot整合持久層之JdbcTemplate多數(shù)據(jù)源

    Spring?Boot整合持久層之JdbcTemplate多數(shù)據(jù)源

    持久層是JavaEE中訪問數(shù)據(jù)庫的核心操作,SpringBoot中對常見的持久層框架都提供了自動化配置,例如JdbcTemplate、JPA 等,MyBatis 的自動化配置則是MyBatis官方提供的。接下來分別向讀者介紹Spring Boot整合這持久層技術(shù)中的整合JdbcTemplate
    2022-08-08
  • java 排序算法之選擇排序

    java 排序算法之選擇排序

    本文主要講解了java 排序算法之選擇排序,選擇排序是最簡單直觀的一種算法,想要了解相關(guān)知識的朋友快來看一看這篇文章吧
    2021-09-09
  • Spring Boot + Mybatis多數(shù)據(jù)源和動態(tài)數(shù)據(jù)源配置方法

    Spring Boot + Mybatis多數(shù)據(jù)源和動態(tài)數(shù)據(jù)源配置方法

    最近做項目遇到這樣的應(yīng)用場景,項目需要同時連接兩個不同的數(shù)據(jù)庫A, B,并且它們都為主從架構(gòu),一臺寫庫,多臺讀庫。下面小編給大家?guī)砹薙pring Boot + Mybatis多數(shù)據(jù)源和動態(tài)數(shù)據(jù)源配置方法,需要的朋友參考下吧
    2018-01-01
  • Spring Boot整合web層實現(xiàn)過程詳解

    Spring Boot整合web層實現(xiàn)過程詳解

    這篇文章主要介紹了Spring Boot整合web層實現(xiàn)過程詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-04-04
  • 詳解Maven多模塊打包遇到的問題解決方法

    詳解Maven多模塊打包遇到的問題解決方法

    這篇文章主要介紹了詳解Maven多模塊打包遇到的問題解決方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-09-09
  • 詳解最簡單易懂的Spring Security 身份認(rèn)證流程講解

    詳解最簡單易懂的Spring Security 身份認(rèn)證流程講解

    這篇文章主要介紹了詳解最簡單易懂的Spring Security 身份認(rèn)證流程講解,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2019-03-03
  • Java?BitMap源碼仿寫實現(xiàn)

    Java?BitMap源碼仿寫實現(xiàn)

    這篇文章主要介紹了Java?BitMap源碼仿寫實現(xiàn),所謂bitmap,就是用每一位來存放某種狀態(tài),適用于大規(guī)模數(shù)據(jù),但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來判斷某個數(shù)據(jù)存不存在的
    2022-12-12
  • 基數(shù)排序簡介及Java語言實現(xiàn)

    基數(shù)排序簡介及Java語言實現(xiàn)

    這篇文章主要介紹了基數(shù)排序簡介及Java語言實現(xiàn),涉及基數(shù)排序的基本思想簡單介紹和桶排序的分析,以及基數(shù)排序的Java實現(xiàn),具有一定借鑒價值,需要的朋友可以參考下。
    2017-11-11
  • 淺談Slf4j與其他日志系統(tǒng)兼容的使用方法

    淺談Slf4j與其他日志系統(tǒng)兼容的使用方法

    下面小編就為大家分享一篇淺談Slf4j與其他日志系統(tǒng)兼容的使用方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2017-12-12
  • Java?NIO?Buffer實現(xiàn)原理詳解

    Java?NIO?Buffer實現(xiàn)原理詳解

    本篇文章主要對NIO核心三件套:緩沖區(qū)(Buffer)、選擇器?(Selector)和通道(Channel),其中之一的緩沖區(qū)Buffer實現(xiàn)原理的學(xué)習(xí)總結(jié)。感興趣的小伙伴可以了解一下
    2021-11-11

最新評論