引出

1.linkedList的節(jié)點(diǎn)，當(dāng)前，上一個(gè)，下一個(gè)的思想；
2.根據(jù)index找node的方法，根據(jù)index確定從頭部還是尾部；
3.linkedlist的增刪改查的實(shí)現(xiàn)，本質(zhì)是改變節(jié)點(diǎn)的信息；
4.遞歸方法實(shí)現(xiàn)自定義鏈表的toString方法；文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-668374.html

從ArrayList到Linkedlist

手動(dòng)實(shí)現(xiàn)ArrayList

Java進(jìn)階（3）——手動(dòng)實(shí)現(xiàn)ArrayList & 源碼的初步理解分析 & 數(shù)組插入數(shù)據(jù)和刪除數(shù)據(jù)的問(wèn)題

從ArrayList到LinkedList

如果發(fā)生對(duì)表的一些插入和刪除操作，特別是對(duì)表的前端進(jìn)行，那么數(shù)組就不是一種好的選擇。另一種數(shù)據(jù)結(jié)構(gòu)：鏈表(linked list)。

鏈表由一系列節(jié)點(diǎn)組成，這些節(jié)點(diǎn)不必在內(nèi)存中相連。每一個(gè)節(jié)點(diǎn)均含有表元素和到包含該元素后繼元的節(jié)點(diǎn)的鏈(link)。我們稱(chēng)之為next鏈。最后一個(gè)單元的next鏈引用null。

鏈表的插入

讓每一個(gè)節(jié)點(diǎn)持有一個(gè)指向它在表中的前驅(qū)節(jié)點(diǎn)的鏈，我們稱(chēng)之為雙鏈表(doubly linked list)。

總體設(shè)計(jì)

在考慮設(shè)計(jì)方面，我們將需要提供三個(gè)類(lèi)：
1.MyLinkedList類(lèi)本身，它包含到兩端的鏈、表的大小以及一些方法。
2.Noe類(lèi)，它可能是一個(gè)私有的嵌套類(lèi)。一個(gè)節(jié)點(diǎn)包含數(shù)據(jù)以及到前一個(gè)節(jié)點(diǎn)的鏈和到下一個(gè)節(jié)點(diǎn)的鏈，還有一些適當(dāng)?shù)臉?gòu)造方法。
3.LinkedListIterator類(lèi)，該類(lèi)抽象了位置的概念，是一個(gè)私有類(lèi)，并實(shí)現(xiàn)接口Iterator。它提供了方法next、hasNext和remove的實(shí)現(xiàn)。

標(biāo)記節(jié)點(diǎn)：

前端創(chuàng)建一個(gè)額外的節(jié)點(diǎn)，邏輯上代表開(kāi)始的標(biāo)記。這些額外的節(jié)點(diǎn)有時(shí)候就叫作標(biāo)記節(jié)點(diǎn)(sentinel node)；特別地，在前端的節(jié)點(diǎn)有時(shí)候也叫作頭節(jié)點(diǎn)(header node),而在末端的節(jié)點(diǎn)有時(shí)候也叫作尾節(jié)點(diǎn)(tail node)

Node類(lèi)

私有的內(nèi)部類(lèi)

• 當(dāng)前節(jié)點(diǎn)，前置節(jié)點(diǎn)，后續(xù)節(jié)點(diǎn)；
• 表示鏈表中的一個(gè)基本元素；

/**
     * 內(nèi)部類(lèi)，節(jié)點(diǎn)；屬性，當(dāng)前節(jié)點(diǎn)，前置節(jié)點(diǎn)，后續(xù)節(jié)點(diǎn)
     * @param <T>
     */
    private static class Node<T> {
        T item; // 當(dāng)前的節(jié)點(diǎn)
        Node<T> next; // 下一個(gè)節(jié)點(diǎn)
        Node<T> prev; // 前置節(jié)點(diǎn)

        Node(Node<T> prev,T element,Node<T> next) {
            this.item = element;
            this.prev = prev;
            this.next = next;
        }

        @Override
        public String toString() {
            String nextStr = null;
            if (next!=null){
                nextStr = next.item.toString();
            }
            String prevStr = null;
            if (prev!=null){
                prevStr = prev.item.toString();
            }

            return "Node{" +
                    " prev=" + prevStr +
                    "，item=" + item +
                    ", next=" + nextStr +
                    '}';
        }
    }

Node的方法：根據(jù)index找node

思路：從頭部開(kāi)始找，進(jìn)行循環(huán)

    public Node<T> NodeByIndex(int index){
        Node<T> x = first; // 從頭部開(kāi)始找
        for (int i = 0; i<index;i++){
            x = x.next;
        }
        return x;
    }

源碼采用如下策略

• 1.根據(jù)index和list的size確定從頭部還是尾部找；
• 2.根據(jù)index找node節(jié)點(diǎn)；

分析：

降低了復(fù)雜度：

如果都從頭部找，時(shí)間復(fù)雜度就是O(i)，在最極端的情況下，根據(jù)index找最后一個(gè)，時(shí)間復(fù)雜度是O(N)；

如果是先確定從頭部找，還是從尾部找，則時(shí)間復(fù)雜度最大是O(N/2)；

增刪改查的實(shí)現(xiàn)

增加元素

最簡(jiǎn)單的情況，都是從尾部新增元素

• 1.新的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)為之前的尾部節(jié)點(diǎn)；
• 2.新的尾部節(jié)點(diǎn)為當(dāng)前新增的節(jié)點(diǎn)；
• 3.如果是第一個(gè)節(jié)點(diǎn)，則需要把first設(shè)置為當(dāng)前的節(jié)點(diǎn)
• 4.鏈表的size+1；

    @Override
    public void add(T e) {
        Node<T> l = last;
        Node<T> newNode = new Node<>(l, e, null); // 新增的節(jié)點(diǎn)，尾部添加

        last = newNode;
        if (l==null){
            // 是第一個(gè)節(jié)點(diǎn)
            first = newNode;
            System.out.println("FirstNode --->"+first);
        }else {
            l.next = newNode;
            System.out.println("Add {"+e+"} ---->"+l);
        }
        size++;
    }

更一般的情況如下，插入一個(gè)元素

刪除元素

刪除頭部？尾部？中間

• 1.如果刪除的是頭部節(jié)點(diǎn)，則讓被刪除的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為first節(jié)點(diǎn)；
• 2.如果刪除的尾部節(jié)點(diǎn)，則讓被刪除的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為null；
• 3.如果刪除的是中間的節(jié)點(diǎn)，讓該節(jié)點(diǎn)的前置節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)；

    @Override
    public void remove(int index) {
        // 找到要?jiǎng)h除的節(jié)點(diǎn)，前置節(jié)點(diǎn)，后續(xù)節(jié)點(diǎn)
        // 1.如果刪除的是頭部節(jié)點(diǎn)
        if (index==0){
            first = NodeByIndex(index+1);
            return;
        }
        // 2.如果不是頭部節(jié)點(diǎn)
        Node<T> tNode = NodeByIndex(index); // 當(dāng)前節(jié)點(diǎn)
        Node<T> prev = tNode.prev; // 當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
        Node<T> next = tNode.next; // 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        if (next==null){
            // 刪除的是尾部節(jié)點(diǎn)
            prev.next = null;
            return;
        }
        // 刪除的是中間的某個(gè)節(jié)點(diǎn)
        // 讓該節(jié)點(diǎn)的前置節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        prev.next = next;
        next.prev = prev;
        size--;
    }

修改元素

被修改的節(jié)點(diǎn)的節(jié)點(diǎn)關(guān)系不變，只需要把當(dāng)前節(jié)點(diǎn)的元素變?yōu)樽钚碌脑丶纯?/p>

代碼實(shí)現(xiàn)

查詢(xún)?cè)?/h3>

調(diào)用node方法即可

    @Override
    public T get(int index) {
        // 索引不能大于等于size
        if (index<0 || index>=size){
            throw new IndexOutOfBoundsException("LinkedList的索引越界");
        }
        return NodeByIndex(index).item;
    }

toString方法

完整代碼

List接口類(lèi)

package com.tianju.book.jpa.mlist;

/**
 * 手工打造ArrayList
 */
public interface MyList<T> {
    /**
     * 增加一個(gè)元素，涉及到容量的變化
     */
    void add(T t);

    /**
     * 根據(jù)索引刪除元素
     * @param index 要?jiǎng)h除元素的索引，超過(guò)索引？索引不存在？
     */
    void remove(int index);

    /**
     * 根據(jù)索引修改一個(gè)元素
     * @param index 要修改的索引
     * @param t 修改的值
     */
    void set(int index,T t);

    /**
     * 根據(jù)索引獲取元素
     * @param index 索引
     * @return 獲取的元素
     */
    T get(int index);

    int size();

    String toString();

}

LinkedList的實(shí)現(xiàn)

package com.tianju.book.jpa.myLinkList;

import com.tianju.book.jpa.mlist.MyList;

public class MyLinkedList<T> implements MyList<T> {

    int size = 0;

    Node<T> first; // 頭部節(jié)點(diǎn)

    Node<T> last; // 尾部節(jié)點(diǎn)


    /**
     * 內(nèi)部類(lèi)，節(jié)點(diǎn)；屬性，當(dāng)前節(jié)點(diǎn)，前置節(jié)點(diǎn)，后續(xù)節(jié)點(diǎn)
     * @param <T>
     */
    private static class Node<T> {
        T item; // 當(dāng)前的節(jié)點(diǎn)
        Node<T> next; // 下一個(gè)節(jié)點(diǎn)
        Node<T> prev; // 前置節(jié)點(diǎn)

        Node(Node<T> prev,T element,Node<T> next) {
            this.item = element;
            this.prev = prev;
            this.next = next;
        }

        @Override
        public String toString() {
            String nextStr = null;
            if (next!=null){
                nextStr = next.item.toString();
            }
            String prevStr = null;
            if (prev!=null){
                prevStr = prev.item.toString();
            }

            return "Node{" +
                    " prev=" + prevStr +
                    "，item=" + item +
                    ", next=" + nextStr +
                    '}';
        }
    }


    @Override
    public void add(T e) {
        Node<T> l = last;
        Node<T> newNode = new Node<>(l, e, null); // 新增的節(jié)點(diǎn)，尾部添加

        last = newNode;
        if (l==null){
            // 是第一個(gè)節(jié)點(diǎn)
            first = newNode;
            System.out.println("FirstNode --->"+first);
        }else {
            l.next = newNode;
            System.out.println("Add {"+e+"} ---->"+l);
        }
        size++;
    }

    public Node<T> NodeByIndex(int index){
        Node<T> x = first; // 從頭部開(kāi)始找
        for (int i = 0; i<index;i++){
            x = x.next;
        }
        return x;
    }

    @Override
    public void remove(int index) {
        // 找到要?jiǎng)h除的節(jié)點(diǎn)，前置節(jié)點(diǎn)，后續(xù)節(jié)點(diǎn)
        // 1.如果刪除的是頭部節(jié)點(diǎn)
        if (index==0){
            first = NodeByIndex(index+1);
            return;
        }
        // 2.如果不是頭部節(jié)點(diǎn)
        Node<T> tNode = NodeByIndex(index); // 當(dāng)前節(jié)點(diǎn)
        Node<T> prev = tNode.prev; // 當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
        Node<T> next = tNode.next; // 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        if (next==null){
            // 刪除的是尾部節(jié)點(diǎn)
            prev.next = null;
            return;
        }
        // 刪除的是中間的某個(gè)節(jié)點(diǎn)
        // 讓該節(jié)點(diǎn)的前置節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        prev.next = next;
        next.prev = prev;
        size--;
    }

    @Override
    public void set(int index, T element) {
        // 索引不能大于等于size
        if (index<0 || index>=size){
            throw new IndexOutOfBoundsException("LinkedList的索引越界");
        }
        Node<T> tNode = NodeByIndex(index); // 當(dāng)前節(jié)點(diǎn)
        T oldVal = tNode.item; // 獲取舊的元素
        tNode.item = element; // 把當(dāng)前節(jié)點(diǎn)的元素設(shè)置成新的
//        System.out.println(oldVal);
    }

    @Override
    public T get(int index) {
        // 索引不能大于等于size
        if (index<0 || index>=size){
            throw new IndexOutOfBoundsException("LinkedList的索引越界");
        }
        return NodeByIndex(index).item;
    }

    @Override
    public int size() {
        return size;
    }

    /**
     * 為了實(shí)現(xiàn)toString方法
     */

    String str = "null-->";

    // 通過(guò)第一個(gè)節(jié)點(diǎn)遞歸調(diào)用，獲得LinkedList的鏈
    private String recursion(Node<T> first){

        if (!str.contains(first.item.toString())){
            str = str + first.item;
        }
        if (first.next==null){
            return str + "-->null";
        }
        str = str + "-->" +  first.next.item.toString();
        first = first.next;
        return recursion(first);
    }


    // 在每次調(diào)用后把str歸位；
    private void backStr(){
        str = "null-->";
    }

    @Override
    public String toString() {
        String recursion = recursion(first);
        backStr();
        return "MyLinkedList{ " + recursion +" }";
    }
}

測(cè)試類(lèi)

package com.tianju.book.jpa.myLinkList;

import org.hibernate.event.spi.SaveOrUpdateEvent;

import java.util.List;

public class MyLinkedListTest1 {
    public static void main(String[] args) {
        MyLinkedList<String> list = new MyLinkedList<>();
        list.add("PET1");
        list.add("PET2");
        list.add("PET3");
        System.out.println("**********");
        System.out.println(list);

        list.add("PET4");
        System.out.println(list);
        System.out.println(list.size());

//        System.out.println(list.get(4));
//        list.remove(0);
//        System.out.println("刪除頭部節(jié)點(diǎn)");
//        System.out.println(list);
//
//        System.out.println("刪除尾部節(jié)點(diǎn)");
//        list.remove(3-1);
//        System.out.println(list);

        System.out.println("刪除中間的節(jié)點(diǎn)");
        list.remove(2);
        System.out.println(list);

        System.out.println("進(jìn)行set");
        list.set(0, "SHI1");
        System.out.println(list);

    }
}

總結(jié)

1.linkedList的節(jié)點(diǎn)，當(dāng)前，上一個(gè)，下一個(gè)的思想；
2.根據(jù)index找node的方法，根據(jù)index確定從頭部還是尾部；
3.linkedlist的增刪改查的實(shí)現(xiàn)，本質(zhì)是改變節(jié)點(diǎn)的信息；
4.遞歸方法實(shí)現(xiàn)自定義鏈表的toString方法；

到了這里，關(guān)于Java進(jìn)階（7）——手動(dòng)實(shí)現(xiàn)LinkedList & 內(nèi)部node類(lèi)的實(shí)現(xiàn) & 增刪改查的實(shí)現(xiàn) & toString方法 & 源碼的初步理解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！