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

更新時(shí)間：2022年06月20日 10:04:54 作者：XH學(xué)Java

本文主要介紹了Java中LinkedList的模擬實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

??關(guān)于LinkedList

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

LinkedList還有三個(gè)成員變量：

??size，表示該鏈表中結(jié)點(diǎn)的個(gè)數(shù)
??first，指向鏈表首結(jié)點(diǎn)
??last，指向鏈表尾結(jié)點(diǎn)

模擬實(shí)現(xiàn)LinkedList

??準(zhǔn)備工作

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

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

??創(chuàng)建成員變量：first，last，size

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

??重寫(xiě)toString()方法，在進(jìn)行測(cè)試方法的時(shí)候需要將鏈表打印出來(lái)

    @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é)點(diǎn)，這里分兩種情況：鏈表為空，鏈表不為空

??鏈表為空：直接將first，last指向該結(jié)點(diǎn)，因?yàn)檫@個(gè)結(jié)點(diǎn)既是第一個(gè)結(jié)點(diǎn)，也是最后一個(gè)結(jié)點(diǎn)
??鏈表不為空：將first的pre執(zhí)行該結(jié)點(diǎn)，再將該結(jié)點(diǎn)的next指向first，更新first位置

??在結(jié)點(diǎn)頭插完后，更新size的長(zhǎng)度，進(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)行測(cè)試：依次頭插入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é)果：因?yàn)槭穷^插，所以打印4，3，2，1

尾插

??在鏈表的尾部插入結(jié)點(diǎn)，分兩種情況：鏈表為空，鏈表不為空
??鏈表為空：直接將first，last指向該結(jié)點(diǎn)，該結(jié)點(diǎn)既是鏈表的首結(jié)點(diǎn)，又是最后一個(gè)結(jié)點(diǎn)
??鏈表不為空：last的next執(zhí)行該節(jié)點(diǎn)，該節(jié)點(diǎn)的pre指向last，更新last位置
??在結(jié)點(diǎn)尾插完后，更新size的長(zhǎng)度，進(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)行測(cè)試：依次尾插入1，2，3，4，打印list

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

??打印結(jié)果：因?yàn)槭俏膊?，所以打?，2，3，4

??在任意位置插入

這里分三種情況討論：在第一個(gè)位置插入，在最后一個(gè)位置插入，在其他位置插入

??在第一個(gè)位置插入：相當(dāng)于頭插，調(diào)用addFirst()方法
??在最后一個(gè)位置插入：相當(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)行測(cè)試：原來(lái)鏈表為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

這里分為三種情況：刪除的是第一個(gè)元素，刪除的是最后一個(gè)元素，刪除其他元素

??刪除一個(gè)元素：將first指向first的next，再將first的pre指向null
??刪除最后一個(gè)元素：將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)行測(cè)試：原鏈表為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

這個(gè)與刪除一次出現(xiàn)元素e的做法差不多，只是在找到第一次出現(xiàn)元素e時(shí)，將它刪掉，繼續(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)行測(cè)試：鏈表為1，2，1，3，1，將所有的1全部刪掉

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

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

找元素下標(biāo)indexOf

創(chuàng)建一個(gè)下標(biāo)index，從0開(kāi)始增加，每遍歷一個(gè)元素進(jìn)行index++，如果遍歷的元素是要找的元素則返回index，當(dāng)遍歷完鏈表沒(méi)有要找的元素時(shí)，返回-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)行測(cè)試：鏈表為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

這個(gè)從鏈表尾部往前遍歷，創(chuàng)建index值為size-1，當(dāng)元素不為我們要找的元素時(shí)，index--，找到返回index，當(dāng)遍歷完整個(gè)鏈表都沒(méi)有找到時(shí)，返回-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)行測(cè)試：鏈表為1，2，3，3，4，5，找3的位置和6的位置

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

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

??判斷鏈表是否包含某個(gè)元素

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

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

??進(jìn)行測(cè)試：鏈表為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不在鏈表中

獲得鏈表長(zhǎng)度

直接返回size即可

    public int size(){
        return size;
    }

??進(jìn)行測(cè)試：返回空鏈表的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)行測(cè)試：看有元素的鏈表是否為空，和空鏈表是否為空

        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)行測(cè)試：執(zhí)行清空操作，打印list

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

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

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

您可能感興趣的文章:

解析Java中的隊(duì)列和用LinkedList集合模擬隊(duì)列的方法

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

軟件下載

源碼下載

軟件編程

網(wǎng)絡(luò)編程

在線(xiàn)工具

數(shù)據(jù)庫(kù)

CMS

常用工具