目錄

試題1：實(shí)現(xiàn)一個(gè)單鏈表，并實(shí)現(xiàn)以下功能：

試題2：實(shí)現(xiàn)一個(gè)雙鏈表，并實(shí)現(xiàn)以下功能

思路總結(jié)：

什么情況下可能涉及到用數(shù)組實(shí)現(xiàn)鏈表呢？

? ? ? 在學(xué)習(xí)時(shí)了解到了可以用數(shù)組模擬鏈表，使其兼顧數(shù)據(jù)查找快，鏈表新增和刪除快的缺點(diǎn)，找來一些試題實(shí)現(xiàn)了下，如下：

試題1：實(shí)現(xiàn)一個(gè)單鏈表，并實(shí)現(xiàn)以下功能：

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

import org.apache.commons.lang3.StringUtils;

import java.util.Scanner;

public class ArrayLinkedList {
    public static final int N = 100000;

    private int head; // head
    private int idx; // 存儲(chǔ)新元素的索引下標(biāo)
    private int[] e; // 存放數(shù)據(jù)的數(shù)組；
    private int[] ne; // 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的地址(數(shù)組下標(biāo))。比如使用頭插法,單向鏈表,e[5] = 5,e[5]的下一個(gè)節(jié)點(diǎn)的坐標(biāo)是ne[5],下一個(gè)節(jié)點(diǎn)是e[ne[5]]

    public ArrayLinkedList() {
        e = new int[N];
        ne = new int[N];
        head = -1;
        idx = 0;
    }

    public void insertToHead(int val) {
        e[idx] = val;
        ne[idx] = head; // head的值是頭結(jié)點(diǎn)指向的下一個(gè)元素的下標(biāo)值
        head = idx++;
    }

    /**
     * 將val插入到索引k后面
     *
     * @param k
     * @param val
     */
    public void insert(int k, int val) {
        e[idx] = val;
        ne[idx] = ne[k];
        ne[k] = idx++;
    }

    /**
     * 刪除k節(jié)點(diǎn)后面的節(jié)點(diǎn)(只刪一個(gè))
     *
     * @param k
     */
    public void remove(int k) {
        if (k + 1 == 0) {
            head = ne[head];
        } else {
            ne[k] = ne[ne[k]];
        }

    }

    public static void main(String[] args) {
        System.out.println("請(qǐng)輸入:");
        Scanner scanner = new Scanner(System.in);
        ArrayLinkedList arrayLinkedList = new ArrayLinkedList();
        int head = arrayLinkedList.head;
        int[] e = arrayLinkedList.e;
        int[] ne = arrayLinkedList.ne;
        while (scanner.hasNextLine()) {
            String inputString = scanner.nextLine();
            if (StringUtils.isBlank(inputString)) {
                break;
            }
            String[] inputArr = inputString.split(" ");
            String f = inputArr[0];
            int s = Integer.valueOf(inputArr[1]);
            switch (f) {
                case "H":
                    arrayLinkedList.insertToHead(s);
                    break;
                case "D":
                    arrayLinkedList.remove(s - 1); // 第k個(gè)插入的數(shù)，idx是k-1
                    break;
                case "I":
                    int val = Integer.valueOf(inputArr[2]);
                    arrayLinkedList.insert(s - 1, val);
                    break;
            }
        }

        for (int i = head; i != -1; i = ne[i]) {
            System.out.print(e[i] + " ");
        }
        scanner.close();
    }
}

試題2：實(shí)現(xiàn)一個(gè)雙鏈表，并實(shí)現(xiàn)以下功能

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

import org.apache.commons.lang3.StringUtils;

import java.util.Scanner;

/**
 * 支持的操作：
 * 1、在最左側(cè)插入一個(gè)數(shù)；
 * 2、在最右側(cè)插入一個(gè)數(shù)；
 * 3、將第k個(gè)插入的數(shù)刪除；
 * 4、在第k個(gè)插入的數(shù)左側(cè)插入一個(gè)數(shù)；
 * 5、在第k個(gè)插入的數(shù)右側(cè)插入一個(gè)數(shù)
 */
public class TwoWayLinkedList2 {
    public static final int N = 100000;
    // 存放數(shù)組的數(shù)據(jù)
    private int[] e;
    // 存放左指針下標(biāo)數(shù)組
    private int[] l;
    // 存放右指針地址數(shù)組
    private int[] r;
    // 數(shù)組待存儲(chǔ)下標(biāo)
    private int idx;
    // e[0]表示鏈表頭；e[1]表示鏈表尾
    // 向左側(cè)插入，就是插入到上一個(gè)節(jié)點(diǎn)的右側(cè)。所以插入的邏輯都抽象成插入到具體節(jié)點(diǎn)的右側(cè)

    // 構(gòu)造方法
    public TwoWayLinkedList2() {
        e = new int[N];
        r = new int[N];
        l = new int[N];
        r[0] = 1;
        l[1] = 0;
        idx = 2;

    }

    /**
     * 將節(jié)點(diǎn)插入到e[k]節(jié)點(diǎn)右側(cè)
     *
     * @param k
     * @param val
     */
    public void add(int k, int val) {
        e[idx] = val;
        l[idx] = k;
        r[idx] = r[k];
        l[r[k]] = idx;
        r[k] = idx;
        idx++;
    }

    /**
     * 刪除e[k]
     *
     * @param k
     */
    public void remove(int k) {
        r[l[k]] = r[k];
        l[r[k]] = l[k];
    }

    public static void main(String[] args) {
        System.out.println("請(qǐng)輸入:");
        Scanner scanner = new Scanner(System.in);
        TwoWayLinkedList2 linkedList = new TwoWayLinkedList2();
        int[] e = linkedList.e;
        int[] l = linkedList.l;
        int[] r = linkedList.r;
        while (scanner.hasNextLine()) {
            String inputString = scanner.nextLine();
            if (StringUtils.isBlank(inputString)) {
                break;
            }
            String[] inputArr = inputString.split(" ");
            String f = inputArr[0];
            Integer s = Integer.valueOf(inputArr[1]);

            switch (f) {
                case "L":
                    linkedList.add(0, s);
                    break;
                case "R":
                    linkedList.add(l[1], s);
                    break;
                case "D":
                    linkedList.remove(s + 1); // 第k個(gè)插入的數(shù)，idx是k+1,因?yàn)槲覀冇昧?和1表示鏈表頭和鏈表尾
                    break;
                case "IL":
                    linkedList.add(l[s + 1], Integer.valueOf(inputArr[2]));
                    break;
                case "IR":
                    linkedList.add(s + 1, Integer.valueOf(inputArr[2]));
                    break;
            }
        }

        // 遍歷輸出
        for (int i = r[0]; i != 1; i = r[i]) {
            System.out.printf("" + e[i]);
        }
        scanner.close();
    }
}

思路總結(jié)：

? ? ? ?數(shù)組實(shí)現(xiàn)鏈表，一個(gè)數(shù)組用于存放數(shù)據(jù)，一個(gè)數(shù)組存放"指針"，這里的指針用數(shù)組下標(biāo)代替。如果是雙向鏈表，要用兩個(gè)數(shù)組存放指針。同時(shí)要注意首節(jié)點(diǎn)和尾結(jié)點(diǎn)的記錄方法。在實(shí)現(xiàn)雙鏈表時(shí)，我曾用兩個(gè)變量表示首尾節(jié)點(diǎn)，對(duì)比起來，沒有用e[0],e[1]表示簡(jiǎn)潔，而且非常容易搞混。占用第0位和第1位保存鏈表頭和尾時(shí)要注意初始的idx=2，第k個(gè)插入的元素的索引下標(biāo)是k+1。大家可以使用更多方法實(shí)現(xiàn)，過程雖然曲折，但一頓操作下來，對(duì)鏈表的操作會(huì)非常的熟練。

什么情況下可能涉及到用數(shù)組實(shí)現(xiàn)鏈表呢？

? ? ? ??在沒有操作系統(tǒng)和內(nèi)存管理的情況下。

1. 鏈表的實(shí)現(xiàn)需要?jiǎng)討B(tài)內(nèi)存分配和釋放,這需要操作系統(tǒng)提供的堆內(nèi)存管理。沒有 OS 的動(dòng)態(tài)內(nèi)存管理,就無法真正實(shí)現(xiàn)鏈表節(jié)點(diǎn)的創(chuàng)建和銷毀。

2. 鏈表通過指針鏈接節(jié)點(diǎn),需要操作系統(tǒng)提供的指針和地址引用機(jī)制。沒有 OS,就無法真正用指針建立節(jié)點(diǎn)之間的鏈接關(guān)系。

3. 數(shù)組可以預(yù)先分配一塊內(nèi)存,這個(gè)內(nèi)存塊可以視為堆內(nèi)存,用下標(biāo)代替指針,通過數(shù)組操作就可以模擬出指針操作。

4. 數(shù)組是一塊連續(xù)的內(nèi)存,空間固定,不需要?jiǎng)討B(tài)擴(kuò)展,所以定義數(shù)組后直接就可以使用,不依賴動(dòng)態(tài)內(nèi)存管理。

5. 數(shù)組中的每個(gè)元素是連續(xù)存儲(chǔ)的,通過下標(biāo)可以直接訪問,不需要指針來進(jìn)行尋址?？梢阅M指針的移動(dòng),改變指針的指向來實(shí)現(xiàn)鏈表的操作。

? ? ? ? 這里我們從算法分析和學(xué)習(xí)的角度來看這個(gè)問題，但不適合實(shí)際項(xiàng)目,只能處理規(guī)模較小的數(shù)據(jù)。要實(shí)現(xiàn)一個(gè)真正的可擴(kuò)展鏈表,還需在操作系統(tǒng)上進(jìn)行動(dòng)態(tài)內(nèi)存管理。文章來源地址http://www.zghlxwxcb.cn/news/detail-707390.html

到了這里，關(guān)于【算法】Java-使用數(shù)組模擬單向鏈表，雙向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！