Java实现静态链表(没有自动扩容,StaticList类代码不够优雅)

发布于 2021-07-18  67 次阅读


对着大话数据结构敲(把C转换成Java),感觉这本书里有错,虽然我没有运行,

问题不大,扩展了思路,挺好。

StaticList类代码如下:

package com.apesblog.StaticList;

import java.nio.channels.Channels;
import java.util.Iterator;

import javax.management.RuntimeErrorException;

import org.omg.CosNaming.NamingContextExt;

public class StaticList<T> implements Iterable<T> {

    private class ArrayNode<T> {
        private T data;
        private int cur;

        public ArrayNode(T data, int cur) {
            this.data = data;
            this.cur = cur;
        }

        public ArrayNode() {
        }
    }

    private ArrayNode[] eles;

    public StaticList(int capacity) {
        eles = new ArrayNode[capacity];
        for (int i = 0; i < capacity; i++) {
            eles[i] = new ArrayNode(null, i + 1);
        }
        eles[capacity - 1].cur = 0;
    }

    public void add(T t) {
        if (eles[eles.length - 1].cur == 0) {
            eles[eles.length - 1].cur = eles[0].cur;
        } else {
            for (int i = eles[eles.length - 1].cur; i < eles.length;) {
                if (eles[i].cur == 0) {
                    eles[i].cur = eles[0].cur;
                    break;
                }
                i = eles[i].cur;
            }
        }
        int x = eles[0].cur;
        if (x != eles.length - 1) {
            eles[x].data = t;
            eles[0].cur = eles[x].cur;
            eles[x].cur = 0;

        } else {
            throw new RuntimeException("静态数组已满");
        }
    }

    public void insert(int i, T t) {
        int next = eles.length - 1;
        int j = eles[eles[0].cur].cur;
        if (eles[0].cur != eles.length - 1) {
            eles[eles[0].cur].data = t;
            for (int k = 1; k < i; k++) {
                next = eles[next].cur;
            }
            eles[eles[0].cur].cur = eles[next].cur;
            eles[next].cur = eles[0].cur;
            eles[0].cur = j;

        } else {
            throw new RuntimeException("静态数组已满");
        }
    }

    public void delete(int i) {
        int next = eles.length - 1;
        for (int k = 1; k < i; k++) {
            next = eles[next].cur;
        }
        int j = eles[next].cur;
        eles[next].cur = eles[j].cur;
        eles[j].cur = eles[0].cur;
        eles[0].cur = j;
    }

    public T get(int i) {
        int next = eles.length - 1;
        for (int index = 1; index <= i; index++) {
            next = eles[next].cur;
        }
        return (T) eles[next].data;
    }

    @Override
    public Iterator<T> iterator() {

        return new Iterator() {
            int next = eles.length - 1;

            @Override
            public boolean hasNext() {

                return eles[next].cur != 0;
            }

            @Override
            public Object next() {
                next = eles[next].cur;
                return eles[next].data;
            }

        };
    }

}

测试类如下:

package com.apesblog.StaticList;

public class Test {

    public static void main(String[] args) {
        StaticList<String> s = new StaticList<>(5);
        s.add("1");
        s.add("3");
        StringBuilder str = new StringBuilder(300);
        str.append("遍历:");
        for (String i : s) {
            str.append(i + " ");
        }
        System.out.println(str);

        s.insert(2, "2");
        str.delete(0, str.length());
        str.append("插入:");
        for (String i : s) {
            str.append(i + " ");
        }
        System.out.println(str);

        s.delete(1);
        str.delete(0, str.length());
        str.append("删除:");
        for (String i : s) {
            str.append(i + " ");
        }
        System.out.println(str);

        s.insert(1, "1");
        str.delete(0, str.length());
        str.append("插入:");
        for (String i : s) {
            str.append(i + " ");
        }
        System.out.println(str);
        System.out.println("查询:" + s.get(2));

        // 5个位置去头去尾只能放3个元素
        s.add("4");

    }

}

因为没有写自动扩容(懒),需要的读者可以根据Java实现线性表的顺序存储结构(ArrayList)这篇文章来自行编写;