【算法】Java-使用数组模拟单向链表，双向链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】Java-使用数组模拟单向链表，双向链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

试题1：实现一个单链表，并实现以下功能：

试题2：实现一个双链表，并实现以下功能

思路总结：

什么情况下可能涉及到用数组实现链表呢？

在学习时了解到了可以用数组模拟链表，使其兼顾数据查找快，链表新增和删除快的缺点，找来一些试题实现了下，如下：

试题1：实现一个单链表，并实现以下功能：

【算法】Java-使用数组模拟单向链表，双向链表,算法,算法,java,链表

Java代码实现：

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; // 存储新元素的索引下标
    private int[] e; // 存放数据的数组；
    private int[] ne; // 当前节点的下一个节点的地址(数组下标)。比如使用头插法,单向链表,e[5] = 5,e[5]的下一个节点的坐标是ne[5],下一个节点是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的值是头结点指向的下一个元素的下标值
        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节点后面的节点(只删一个)
     *
     * @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("请输入:");
        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个插入的数，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：实现一个双链表，并实现以下功能

【算法】Java-使用数组模拟单向链表，双向链表,算法,算法,java,链表 Java代码实现：

import org.apache.commons.lang3.StringUtils;

import java.util.Scanner;

/**
 * 支持的操作：
 * 1、在最左侧插入一个数；
 * 2、在最右侧插入一个数；
 * 3、将第k个插入的数删除；
 * 4、在第k个插入的数左侧插入一个数；
 * 5、在第k个插入的数右侧插入一个数
 */
public class TwoWayLinkedList2 {
    public static final int N = 100000;
    // 存放数组的数据
    private int[] e;
    // 存放左指针下标数组
    private int[] l;
    // 存放右指针地址数组
    private int[] r;
    // 数组待存储下标
    private int idx;
    // e[0]表示链表头；e[1]表示链表尾
    // 向左侧插入，就是插入到上一个节点的右侧。所以插入的逻辑都抽象成插入到具体节点的右侧

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

    }

    /**
     * 将节点插入到e[k]节点右侧
     *
     * @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("请输入:");
        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个插入的数，idx是k+1,因为我们用了0和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();
    }
}

思路总结：

数组实现链表，一个数组用于存放数据，一个数组存放"指针"，这里的指针用数组下标代替。如果是双向链表，要用两个数组存放指针。同时要注意首节点和尾结点的记录方法。在实现双链表时，我曾用两个变量表示首尾节点，对比起来，没有用e[0],e[1]表示简洁，而且非常容易搞混。占用第0位和第1位保存链表头和尾时要注意初始的idx=2，第k个插入的元素的索引下标是k+1。大家可以使用更多方法实现，过程虽然曲折，但一顿操作下来，对链表的操作会非常的熟练。