锻炼下大脑－java 实现静态链表

雨翔河

首页列表关于

锻炼下大脑－java 实现静态链表

2015-01-19 08:57

>    大二之后就没怎么碰过算法,都忘记的差不多了。试着用java来实现下链表，因为java没有指针概念的缘故，用数组的下标来代替指针，这样一个静态链表就出来了。

这是一个静态双向不循环链表：

```

public class Test {

public static void main(String[] args) {
        L l = new L();
        l.init();
        l.insert(123);
        l.insert(456);
        l.insert(789);
        l.insert(222);
        int removeIndex = l.insert(333);
        l.show();
        l.removeNode(removeIndex);
        l.show();
        System.exit(0);
    }
}

/**
 * 静态链表
 */
class L {
    private static final int MAX = 100;  //链表的最大容量
    private Node node[] = new Node[MAX];
    private int head;  //头指针,头指针区域可存储数据也可以不存储数据,只用来做向导,我这里是存储了数据.

class Node {
        public int next = -1;  //指针指向的后一个节点
        public int pre = -1;  //指针指向的前一个节点
        public long value = -1;  //节点的值
    }

/**
     * 初始化链表空间,其实这个可以在实例化类的时候完成的.
     */
    public void init() {
        head = 0;
        for (int i = 0; i < MAX; i++) {
            node[i] = new Node();
            node[i].next = -1;  //为了简单的实现下,假设空值为-1
            node[i].pre = -1;
            node[i].value = -1;
        }
    }

/**
     * 分配节点空间,类似于c里的malloc
     *
     * @return int
     */
    public int malloc() {
        for (int i = 0; i < MAX; i++) {
            if (node[i].pre < 0 && node[i].next < 0 && node[i].value < 0) {
                return i;
            }
        }
        System.out.println("malloc fail ,full");
        return -1;
    }

/**
     * 移除节点
     *
     * @param indexNode indexNode
     */
    public void removeNode(int indexNode) {
        if (indexNode < 0) {
            System.out.println("removeNode indexNode is error");
            return;
        }
        int preNode = node[indexNode].pre;
        int nextNode = node[indexNode].next;
        node[indexNode].pre = -1;
        node[indexNode].next = -1;
        node[indexNode].value = -1;
        if (nextNode >= 0) {
            node[nextNode].pre = preNode;
        }
        //头节点被移除
        if (preNode < 0) {
            head = nextNode;
        } else {
            node[preNode].next = nextNode;
        }
    }

/**
     * 插入节点
     *
     * @param v v
     */
    public int insert(long v) {
        int index = head;
        while (node[index].next >= 0) {
            index = node[index].next;
        }
        int insertNodeIndex = malloc();
        if (insertNodeIndex < 0) {
            System.out.println("malloc error,please check malloc function.");
            return -1;
        }
        node[insertNodeIndex].value = v;
        if (insertNodeIndex == head) {
            node[insertNodeIndex].pre = -1;
        } else {
            node[index].next = insertNodeIndex;
            node[insertNodeIndex].pre = index;
        }
        return insertNodeIndex;
    }

/**
     * 测试下显示这个链表
     */
    public void show() {
        int index = head;
        System.out.println("show l:-------------------------");
        while (node[index].next >= 0) {
            System.out.println(node[index].value);
            index = node[index].next;
        }
        System.out.println(node[index].value);
        System.out.println("show l end:-----------------------");

System.out.println("test show l start:_______________");
        while (node[index].pre >= 0) {
            System.out.println(node[index].value);
            index = node[index].pre;
        }
        System.out.println(node[index].value);
        System.out.println("test show l end:_______________");
    }

}

```

类型：工作标签：静态链表,java